thumb|An example FFT algorithm structure, using a decomposition into half-size FFTs

thumb|A discrete Fourier analysis of a sum of cosine waves at 10, 20, 30, 40, and 50 Hz

thumb|Time-based representation (above) and frequency-based representation (below) of the same signal, where the lower representation can be obtained from the upper one by Fourier transformation

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT), or its inverse (IDFT), of a sequence. A Fourier transform converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa.

The DFT is obtained by decomposing a sequence of values into components of different frequencies. and it was included in Top 10 Algorithms of 20th Century by the IEEE magazine Computing in Science & Engineering.

James Cooley and John Tukey independently rediscovered these earlier algorithms

The FFT's importance derives from the fact that it has made working in the frequency domain equally computationally feasible as working in the temporal or spatial domain. Some of the important applications of the FFT include: The efficiency of the FFT allows for high-speed data transmission by dividing a wideband signal into multiple closely spaced orthogonal subcarriers. This technology is essential for reducing interference and optimizing power consumption in mobile devices. These transforms allow for localized frequency analysis by capturing both frequency and time-based information.

Research areas

; Big FFTs: With the explosion of big data in fields such as astronomy, the need for 512K FFTs has arisen for certain interferometry calculations. The data collected by projects such as WMAP and LIGO require FFTs of tens of billions of points. As this size does not fit into main memory, so-called out-of-core FFTs are an active area of research.

Language reference

See also

FFT-related algorithms:

  • Bit-reversal permutation
  • Goertzel algorithm – computes individual terms of the discrete Fourier transform

FFT implementations:

  • FFTW – a free software library developed by Matteo Frigo and Steven G. Johnson at MIT
  • FFTReal – a highly optimized clean and concise implementation with support for scalar or a SIMD vector in C++ class by Dmitry Boldyrev hosted at GITHUB https://github.com/mewza/realfft/
  • ALGLIB – a dual/GPL-licensed C++ and C# library (also supporting other languages), with real/complex FFT implementation
  • FFTPACK – another Fortran FFT library (public domain)
  • Architecture-specific:
  • Arm Performance Libraries
  • Intel Integrated Performance Primitives
  • Intel Math Kernel Library
  • Many more implementations are available, for CPUs and GPUs, such as PocketFFT for C++

Other links:

  • Butterfly diagram – a diagram used to describe FFTs
  • Fast Algorithms for Multidimensional Signals
  • Fast Fourier Transform Telescope
  • Fast Walsh–Hadamard transform
  • Generalized distributive law
  • Least-squares spectral analysis
  • Multidimensional discrete convolution
  • Multidimensional transform
  • Odlyzko–Schönhage algorithm applies the FFT to finite Dirichlet series
  • Schönhage–Strassen algorithm – asymptotically fast multiplication algorithm for large integers
  • Spectral music (involves application of DFT analysis to musical composition)
  • Spectrum analyzer – any of several devices that perform spectrum analysis, often via a DFT
  • Time series

References

Further reading

  • (NB. Contains extensive bibliography.)
  • (Chap.9 and other chapters)
  • Fast Fourier Transform for Polynomial Multiplication fast Fourier algorithm
  • Fast Fourier transform — FFT FFT programming in C++ the Cooley–Tukey algorithm
  • Online documentation, links, book, and code
  • Sri Welaratna, "Thirty years of FFT analyzers ", Sound and Vibration (January 1997, 30th anniversary issue) a historical review of hardware FFT devices
  • ALGLIB FFT Code a dual/GPL-licensed multilanguage (VBA, C++, Pascal, etc.) numerical analysis and data processing library
  • SFFT: Sparse Fast Fourier Transform MIT's <!-- sparse --> sparse (sub-linear time) FFT algorithm, sFFT, and implementation
  • VB6 FFT a VB6 optimized library implementation with source code
  • Interactive FFT Tutorial a visual interactive intro to Fourier transforms and FFT methods
  • Introduction to Fourier analysis of time series tutorial how to use of the Fourier transform in time series analysis