A Fast Fourier Transform Algorithm for Real-Valued Series A new procedure is presented for calculating the complex, discrete Fourier transform of real-valued time series. This procedure is described for an example where the number of points in the series is an integral power of two. This algorithm preserves the order and symmetry of the Cooley-Turkey fast Fourier transform algorithm while effecting the two-to-one reduction in computation and storage which can be achieved when the series is real. Also discussed are hardware and software implementations of the algorithm which perform only (N/4) log2 (N/2) complex multiply and add operations, and which require only N real storage locations in analyzing each N-point record. CACM October, 1968 Bergland, G. D. fast Fourier transform, time series analysis, digital filtering, spectral analysis, real-time spectrum analyzers, Fourier analysis, discrete Fourier transform, digital spectrum analysis, Fourier analysis algorithm, Fourier synthesis algorithm 3.80 3.81 4.9 5.49 6.22 CA681008 JB February 21, 1978 3:23 PM 1668 4 1679 1669 4 1679 1679 4 1679 1728 4 1679 2859 4 1679 1525 5 1679 1679 5 1679 1679 5 1679 1679 5 1679 2354 5 1679 1418 6 1679 1521 6 1679 1597 6 1679 1679 6 1679 2350 6 1679 2355 6 1679