Fast Fourier Transform -- from Wolfram MathWorld

Calculus and Analysis > Integral Transforms > Fourier Transforms >

Interactive Entries > Interactive Demonstrations >

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. If the function to be transformed is not harmonically related to the sampling frequency, the response of an FFT looks like a sinc function (although the integrated power is still correct). Aliasing (leakage) can be reduced by apodization using a tapering function. However, aliasing reduction is at the expense of broadening the spectral response.

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

sum_(n=0)^(N-1)a_ne^(-2piink/N)=sum_(n=0)^(N/2-1)a_(2n)e^(-2pii(2n)k/N)
+sum_(n=0)^(N/2-1)a_(2n+1)e^(-2pii(2n+1)k/N)
=sum_(n=0)^(N/2-1)a_n^(even)e^(-2piink/(N/2))
+e^(-2piik/N)sum_(n=0)^(N/2-1)a_n^(odd)e^(-2piink/(N/2)),

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).

REFERENCES:

Arndt, J. "FFT Code and Related Stuff." http://www.jjj.de/fxt/.

Bell Laboratories. "Netlib FFTPack." http://netlib.bell-labs.com/netlib/fftpack/.

Bergland, G. D. "A Guided Tour of the Fast Fourier Transform." IEEE Spectrum 6, 41-52, July 1969.

Blahut, R. E. Fast Algorithms for Digital Signal Processing. New York: Addison-Wesley, 1984.

Bracewell, R. The Fourier Transform and Its Applications, 3rd ed. New York: McGraw-Hill, 1999.

Brigham, E. O. The Fast Fourier Transform and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.

Chu, E. and George, A. Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. Boca Raton, FL: CRC Press, 2000.

Cooley, J. W. and Tukey, O. W. "An Algorithm for the Machine Calculation of Complex Fourier Series." Math. Comput. 19, 297-301, 1965.

Crandall, R.; Jones, E.; Klivington, J.; and Kramer, D. "Gigaelement FFTs on Apple G5 Clusters." 27 Aug 04. http://images.apple.com/acg/pdf/20040827_GigaFFT.pdf.

Duhamel, P. and Vetterli, M. "Fast Fourier Transforms: A Tutorial Review." Signal Processing 19, 259-299, 1990.

Lipson, J. D. Elements of Algebra and Algebraic Computing. Reading, MA: Addison-Wesley, 1981.

Nussbaumer, H. J. Fast Fourier Transform and Convolution Algorithms, 2nd ed. New York: Springer-Verlag, 1982.

Papoulis, A. The Fourier Integral and its Applications. New York: McGraw-Hill, 1962.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Fast Fourier Transform." Ch. 12 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 490-529, 1992.

Ramirez, R. W. The FFT: Fundamentals and Concepts. Englewood Cliffs, NJ: Prentice-Hall, 1985.

Stoer, J. and Bulirsch, R. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980.

Strang, G. "Wavelet Transforms Versus Fourier Transforms." Bull. Amer. Math. Soc. 28, 288-305, 1993.

Van Loan, C. Computational Frameworks for the Fast Fourier Transform. Philadelphia, PA: SIAM, 1992.

Walker, J. S. Fast Fourier Transform, 2nd ed. Boca Raton, FL: CRC Press, 1996.

CITE THIS AS:

Weisstein, Eric W. "Fast Fourier Transform." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/FastFourierTransform.html