Fast Fourier Transform

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for points from to , where lg is the base-2 logarithm.

FFTs were first discussed by Cooley and Tukey (1965), although Gauss had actually described the critical factorization step as early as 1805 (Bergland 1969, Strang 1993). A discrete Fourier transform can be computed using an FFT by means of the Danielson-Lanczos lemma if the number of points is a power of two. If the number of points is not a power of two, a transform can be performed on sets of points corresponding to the prime factors of which is slightly degraded in speed. An efficient real Fourier transform algorithm or a fast Hartley transform (Bracewell 1999) gives a further increase in speed by approximately a factor of two. Base-4 and base-8 fast Fourier transforms use optimized code, and can be 20-30% faster than base-2 fast Fourier transforms. prime factorization is slow when the factors are large, but discrete Fourier transforms can be made fast for , 3, 4, 5, 7, 8, 11, 13, and 16 using the Winograd transform algorithm (Press et al. 1992, pp. 412-413, Arndt).

Fast Fourier transform algorithms generally fall into two classes: decimation in time, and decimation in frequency. The Cooley-Tukey FFT algorithm first rearranges the input elements in bit-reversed order, then builds the output transform (decimation in time). The basic idea is to break up a transform of length into two transforms of length using the identity

sometimes called the Danielson-Lanczos lemma. The easiest way to visualize this procedure is perhaps via the Fourier matrix.

The Sande-Tukey algorithm (Stoer and Bulirsch 1980) first transforms, then rearranges the output values (decimation in frequency).

Wolfram Web Resources