TOPICS
Search

Discrete Fourier Transform


The continuous Fourier transform is defined as

f(nu)=F_t[f(t)](nu)
(1)
=int_(-infty)^inftyf(t)e^(-2piinut)dt.
(2)

Now consider generalization to the case of a discrete function, f(t)->f(t_k) by letting f_k=f(t_k), where t_k=kDelta, with k=0, ..., N-1. Writing this out gives the discrete Fourier transform F_n=F_k[{f_k}_(k=0)^(N-1)](n) as

 F_n=sum_(k=0)^(N-1)f_ke^(-2piink/N).
(3)

The inverse transform f_k=F_n^(-1)[{F_n}_(n=0)^(N-1)](k) is then

 f_k=1/Nsum_(n=0)^(N-1)F_ne^(2piikn/N).
(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 f_k are real, then F_(N-n) and F_n are related by

 F_(N-n)=F^__n,
(5)

for n=0, 1, ..., N-1, where z^_ denotes the complex conjugate. This means that the component F_0 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.

DiscreteFourierTransform

The plots above show the real part (red), imaginary part (blue), and complex modulus (green) of the discrete Fourier transforms of the functions f(x)=sinx (left figure) and f(x)=sinx+sin(3x)/2 (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 sinx 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 l 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 b in the exponent of the discrete Fourier transform gives the so-called (linear) fractional Fourier transform.

DiscreteFourierTransform2D

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 sin(x+y).


See also

Aliasing, Fast Fourier Transform, Fourier Transform, Fractional Fourier Transform, Hartley Transform, Leakage, Power Spectrum, Winograd Transform, Z-Transform

Explore with Wolfram|Alpha

References

Arfken, G. "Discrete Orthogonality--Discrete Fourier Transform." §14.6 in Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 787-792, 1985.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Fourier Transform of Discretely Sampled Data." §12.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 494-498, 1989.Roberts, S. Lecture 7-The Discrete Fourier Transform. pp. 82-96. http://www.robots.ox.ac.uk/~sjrob/Teaching/SP/l7.pdf.

Referenced on Wolfram|Alpha

Discrete Fourier Transform

Cite this as:

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

Subject classifications