Numerical analysis: A fast Fourier transform algorithm for real-valued series
GD Bergland - Communications of the ACM, 1968 - dl.acm.org
GD Bergland
Communications of the ACM, 1968•dl.acm.orgA 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-Tukey 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) …
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-Tukey 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) …
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-Tukey 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.