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
[31] and rediscovered in the 1960s by Cooley and Tukey
[17].

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

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

- Mixed-Radix Cooley-Tukey FFT

- Prime Factor Algorithm (PFA)
- Rader's FFT Algorithm for Prime Lengths
- Bluestein's FFT Algorithm
- Fast Transforms in Audio DSP
- Related Transforms

- FFT Software

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University