Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm.

Related Topics:
Mathematics - Fourier transform - Signal processing - Signal - Partial differential equations - Convolution - Fast Fourier transform

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The sequence of n complex numbers x0, ..., xn−1 are transformed into the sequence of n complex numbers f0, ..., fn−1 by the DFT according to the formula:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:f_j = sum_{k=0}^{n-1} x_k e^{-rac{2 pi i}{n} j k} quad quad j = 0, dots, n-1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where e is the base of the natural logarithm, i is the imaginary unit (i^2=-1), and π is Pi. The transform is sometimes denoted by the symbol mathcal{F}, as in mathbf{f} = mathcal{F}(mathbf{x}) or mathcal{F} mathbf{x}.

Related Topics:
Base of the natural logarithm - Imaginary unit - Pi

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The inverse discrete Fourier transform (IDFT) is given by

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:x_k = rac{1}{n} sum_{j=0}^{n-1} f_j e^{rac{2pi i}{n} j k} quad quad k = 0,dots,n-1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/n) and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/n. A normalization of 1/sqrt{n} for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(The convention of a negative sign in the exponent is often convenient because it means that f_j is the amplitude of a "positive frequency" 2pi j/n. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In the following discussion the terms "sequence" and "vector" will be considered interchangeable.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~