A High-Speed Algorithm for the Computer Generation of Fourier Transforms
- 1 April 1968
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-17 (4) , 373-375
- https://doi.org/10.1109/tc.1968.229396
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
This publication has 4 references indexed in Scilit:
- Fast Fourier-Transform Technique and Its Application to Fourier Spectroscopy*Journal of the Optical Society of America, 1966
- Fast Fourier TransformsPublished by Association for Computing Machinery (ACM) ,1966
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- The Interaction Algorithm and Practical Fourier AnalysisJournal of the Royal Statistical Society Series B: Statistical Methodology, 1958