The publication of the Cooley-Tukey fast Fourier transform (FFT) algorithm in 1965 has opened a new area in digital signal processing by reducing the order of complexity of some crucial computational tasks like Fourier transform and convultion from N 2 to N log 2 , where N is the problem size. The development of the major algorithms (Cooley-Tukey and split-radix FFT, prime factor algorithm and Winograd fast Fourier transform) is reviewed. Then, an attempt is made to indicate the state of the art on the subject, showin the standing of researh, open problems and implementations | Duhamel P. Vetterli M. Fast Fourier Transforms A Tutorial Review and a State of the Art Digital Signal Processing Handbook Ed. Vijay K. Madisetti and Douglas B. Williams Boca Raton CRC Press LLC 1999 1999 by CRC Press LLC 7 Fast Fourier Transforms A Tutorial Review and a State of the Art1 Introduction A Historical Perspective From Gauss to the Cooley-Tukey FFT Development of the Twiddle Factor FFT FFTs Without Twiddle Factors MultiDimensional DFTs State of the Art Motivation or why dividing is also conquering FFTs with Twiddle Factors The Cooley-Tukey Mapping Radix-2 and Radix-4 Algorithms Split-Radix Algorithm Remarks on FFTs with Twiddle Factors FFTs Based on Costless Mono- to Multidimensional Mapping Basic Tools Prime Factor Algorithms 95 Winograd s Fourier Transform Algorithm WFTA 56 Other Members of This Class 38 Remarks on FFTs Without Twiddle Factors State of the Art Multiplicative Complexity Additive Complexity Structural Considerations Inverse FFT In-Place Computation Regularity Parallelism Quantization Noise Particular Cases and Related Transforms DFT Algorithms for Real Data DFT Pruning Related Transforms Multidimensional Transforms Row-Column Algorithms Vector-Radix Algorithms Nested P Duhamel Algorithms Polynomial Transform Discussion X . J X .LX XC XX X IvyX ENST Paris Implementation Issues General Purpose Computers Digital Signal Processors Vec- M. Vetterli tor and Multi-Processors VLSI EPFL Lausanne Conclusion and University of California Acknowledgments Berkeley References The publication of the Cooley-Tukey fast Fourier transform FFT algorithm in 1965 has opened a new area in digital signal processing by reducing the order of complexity of 1 Reprinted from Signal Processing 19 259-299 1990 with kind permission from Elsevier Science-NL Sara Burgerhartstraat 25 1055 KV Amsterdam The Netherlands. 1999 by CRC Press LLC some crucial computational tasks such as Fourier transform and convolution from N2 to N
