Discrete Fourier Transform
The discrete Fourier transform (DFT) is a multidisciplinary formula that relates the spectrum of a function or signal described by a finite sequence of
function values. Among its many applications, the DFT is used for audio and image processing, for solving partial differential equations, and for facilitating
convolution and polynomial multplication.
For a function
the discrete Fourier transform of is defined by
The calculation of this sum takes computational steps, making the computation of the Fourier coefficients an
order computation, that is computationally cumbersome for large N. For example, a 720p image frame f requires on the order 239
computational steps to find all of its Fourier coefficients, F[n].
Thus, in the early days of computing, the usefulness of formula (1) was minimal. However, in 1965 James Cooley (a mathematician for IBM) and John Tukey (a mathematician at Princeton and Bell labs) wrote a paper
describing what would become known as the fast Fourier transform (FFT) algorithm, that reduced the computational cost to the order of Nlog(N) steps.
While it soon became well-known that the algorithm existed in different forms and applications dating back to Gauss, the Cooley-Tukey paper brought
Fourier analysis to the forefront of scientific computing.
Since the Cooley-Tukey paper, there have been variations and improvements to the FFT algorithm, including the fastest Fourier transform
in the west (FFTW) and the sparse Fourier transform. The publications section of this site is partitioned into a history section,
as well as listing references for these variations and improvements. The software section contains links to several open source
implementations of these algorithms.
An image of an MRI, and a representation of the modulus of its Fourier transform.
1. [E.O. Brigham, and R.E. Morrow, The fast Fourier transform, Spectrum, IEEE 4.12 (1967), 63-70.]↩