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
.
Such FFT algorithms were evidently first used by Gauss in 1805
[29] and rediscovered in the 1960s by Cooley and Tukey
[14].

Pointers to FFT software are given in
§A.7.^{A.2}

- 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]

Copyright ©

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

[Automatic-links disclaimer]