Discrete Fourier Transform

The continuous Fourier transform is defined as

			(1)
			(2)

Now consider generalization to the case of a discrete function, by letting , where , with , ..., . Writing this out gives the discrete Fourier transform as

(3)

The inverse transform is then

(4)

Discrete Fourier transforms (DFTs) are extremely useful because they reveal periodicities in input data as well as the relative strengths of any periodic components. There are however a few subtleties in the interpretation of discrete Fourier transforms. In general, the discrete Fourier transform of a real sequence of numbers will be a sequence of complex numbers of the same length. In particular, if are real, then and are related by

(5)

for , 1, ..., , where denotes the complex conjugate. This means that the component is always real for real data.

As a result of the above relation, a periodic function will contain transformed peaks in not one, but two places. This happens because the periods of the input data become split into "positive" and "negative" frequency complex components.

The fast Fourier transform is a particularly efficient algorithm for performing discrete Fourier transforms of samples containing certain numbers of points.

There are two main types of errors that may affect discrete Fourier transforms: aliasing and leakage.

The plots above show the real part (red), imaginary part (blue), and complex modulus (green) of the discrete Fourier transforms of the functions (left figure) and (right figure) sampled 50 times over two periods. In the left figure, the symmetrical spikes on the left and right side are the "positive" and "negative" frequency components of the single sine wave. Similarly, in the right figure, there are two pairs of spikes, with the larger green spikes corresponding to the lower-frequency stronger component and the smaller green spikes corresponding to the higher-frequency weaker component. A suitably scaled plot of the complex modulus of a discrete Fourier transform is commonly known as a power spectrum.

The Wolfram Language implements the discrete Fourier transform for a list of complex numbers as Fourier[list].

The discrete Fourier transform is a special case of the Z-transform.

The discrete Fourier transform can be computed efficiently using a fast Fourier transform.

Adding an additional factor of in the exponent of the discrete Fourier transform gives the so-called (linear) fractional Fourier transform.

The discrete Fourier transform can also be generalized to two and more dimensions. For example, the plot above shows the complex modulus of the 2-dimensional discrete Fourier transform of the function .