Fast Fourier Transform (FFT) Algorithms

The term fast Fourier transform (FFT) refers to an efficient implementation of the discrete Fourier transform (DFT) for highly composite^A.1 transform lengths . When computing the DFT as a set of inner products of length each, the computational complexity is . When is an integer power of 2, a Cooley-Tukey FFT algorithm delivers complexity , where denotes the log-base-2 of , and means ``on the order of ''. Such FFT algorithms were evidently first used by Gauss in 1805 [28] and rediscovered in the 1960s by Cooley and Tukey [14].

In this appendix, a brief introduction is given for various FFT algorithms. A tutorial review (1990) is given in [20]. Additionally, there are some excellent FFT ``home pages'':

• http://en.wikipedia.org/wiki/Category:FFT_algorithms
• http://faculty.prairiestate.edu/skifowit/fft/

Pointers to FFT software are given in §A.7.

---

Subsections

• Mixed-Radix Cooley-Tukey FFT
  • Decimation in Time
  • Radix 2 FFT
    • Radix 2 FFT Complexity is N Log N
  
  
• Prime Factor Algorithm (PFA)
• Rader's FFT Algorithm for Prime Lengths
• Bluestein's FFT Algorithm
• Fast Transforms in Audio DSP
• Related Transforms
  • The Discrete Cosine Transform (DCT)
  • Number Theoretic Transform
  
  
• FFT Software

---

Order a Hardcopy of Mathematics of the DFT

Previous: Recommended Further Reading
Next: Mixed-Radix Cooley-Tukey FFT

---

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.