Title :
A High-Speed Algorithm for the Computer Generation of Fourier Transforms
fDate :
4/1/1968 12:00:00 AM
Abstract :
Abstract—An efficient algorithm is presented for performing the Fourier transformation operation on a digital computer. This algorithm completes the transform calculation with Nlog2N complex additions (complex additions include complex subtractions) and ½N [log2(N)-2]+1 complex multiplications. This is a considerable savings over a brute-force method of N2complex additions and multiplications, especially when considering the use of digital machines whose MULTIPLY time is much longer than ADD time.
Keywords :
Index terms—Fast Fourier transform algorithm, Fourier transforms, spectral analysis.; Equations; Fourier series; Fourier transforms; NASA; Spectral analysis; Index terms—Fast Fourier transform algorithm, Fourier transforms, spectral analysis.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1968.229396