Discrete Fourier transform

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

The discrete Fourier transform is a transformation widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal. It can be computed quickly using the algorithm known as Fast Fourier Transform.

Definition

Formally, the discrete Fourier transform is a function F : Cn -> Cn (where C denotes the set of complex numbers. The unicode symbol ℱ is also used to represent the Fourier transform function). The n complex numbers x0, ...., xn-1 are transformed into the n complex numbers f0, ..., fn-1 according to the formula

              n-1         
   fj  =  1/n  ∑  xk e-2πijk/n     j = 0,...,n-1
              k=0

where e is the base of the natural logarithm, i is the imaginary unit and π is Pi.

Note that in some treatments the factor 1/n and sometimes also the minus sign in the exponent are omitted. With minor adjustments, all that is said below is also valid for these variations.

Properties

The transform can be interpreted as the multiplication of the vector (x0, ...., xn-1) by an n-by-n matrix; therefore, the discrete Fourier transform is a linear operator. The matrix is invertible and the inverse transformation, which allows to recover the xk from the fj, is given by

         n-1
   xk  =  ∑  fj e2πikj/n      k = 0,...,n-1
         j=0

There is precisely one function p(t) of the form

   p(t)  =  a0 + a1eit + a2e2it + ... + an-1e(n-1)it

with the property p(2πk/n) = xk for k = 0,...,n-1. This function is called the trigonometric interpolation polynomial for the xk, and its coefficients are given by the Fourier transformation: aj = fj for j = 0,...,n-1.

If x0, ...., xn-1 are real numbers, as they often are in the applications, then fj = fn-j*, where the star denotes complex conjugation. Hence, the full information in this case is already contained in the first half of the sequence f0,...,fn-1. Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

The cyclic convolution x*y of the two vectors x = (xj) and y = (yk) is the vector x*y with components

              n-1 
    (x*y)k  =  ∑  xjyk-j     k = 0,...,n-1
              j=0

(where we continue y cyclically so that y-j = yn-j for j = 1,...,n-1. The discrete Fourier transform turns cyclic convolutions into component-wise multiplication:

    F(x*y)j  =  F(x)j F(y)j    j = 0,...,n-1

Applications

All the applications depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, the Fast Fourier Transform.

1) Suppose a signal x(t) is to be analyzed. Here, t stands for time, which varies over the interval [0,T], and, in the case of a sound signal, x(t) is the air pressure at time t. The signal is sampled at n equidistant points to get the n real numbers x0 = x(0), x1 = x(h), x2 = x(2h), ..., xn-1 = x((n-1)h), where h = T/n and n is even. Then the discrete Fourier transform f0,...,fn-1 is computed and the numbers fn/2 + 1,...,fn-1 are discarded. Then f0 approximates the average value of the signal over the interval, and for every j = 1,...,n/2, the argument (see complex number) arg(fj) represents the phase and the modulus |fj| represents one half of the amplitude of the component of the signal having frequency j/T (see wave).

The reason behind this interpretation is that the fj are approximations to the coefficients occurring in the Fourier series expansion of x(t).


2) Several lossy image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be irrelevant noice, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients.

3) The fastest known algorithms for the multiplication of large integers or polynomials are based on the discrete Fourier transform: the sequences of digits or coefficients are interpreted as vectors whose convolution needs to be computed; in order to do this, they are first Fourier transformed, then component-wise multiplied, and transformed back.