TOPICS

Fast Fourier Transform

The fast Fourier transform (FFT) is a discrete Fourier transform algorithm which reduces the number of computations needed for N points from 2N^2 to 2NlgN, 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 N is a power of two. If the number of points N is not a power of two, a transform can be performed on sets of points corresponding to the prime factors of N 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 N=2, 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 N into two transforms of length N/2 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).

See also

Aliasing, Danielson-Lanczos Lemma, Discrete Fourier Transform, Fourier Matrix, Fourier Transform, Fractional Fourier Transform, Hartley Transform, Leakage, Number Theoretic Transform, Winograd Transform

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Fast Fourier Transform

Cite this as:

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

Subject classifications