Encyclopedia > Discrete Fourier transform

  Article Content

Discrete Fourier transform

The discrete Fourier transform (DFT) 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 a Fast Fourier Transform algorithm.

Table of contents

Definition

Formally, the discrete Fourier transform is a linear, invertible 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

<math>f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2 \pi i}{n} j k}
\quad \quad
 j = 0, \dots, n-1 </math>

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

Note that the normalization factor multiplying the sum (here unity) and the sign of the exponent are merely conventions, and differ in some treatments. All of the following discussion applies regardless of the convention, with at most minor adjustments. The only important thing is that the forward and inverse transforms have opposite-sign exponents, and that the product of their normalization factors be 1/n.

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 one to recover the xk from the fj, is given by

<math>x_k = \frac{1}{n} \sum_{j=0}^{n-1} f_j e^{\frac{2\pi i}{n} k j}
\quad \quad k = 0,\dots,n-1 </math>

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

<math> p(t) = a_0 + a_1 e^{it} + a_2 e^{2it} + \dots + a_{n-1} e^{(n-1)it} </math>
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 (roughly) of the sequence f0,...,fn-1. In this case, the "DC" element f0 is purely real, and for even n the "Nyquist" element fn/2 is also real, so there are exactly n non-redundant real numbers in the first half + Nyquist element of the complex output f. 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

<math> (\mathbf{x*y})_k = \sum_{j=0}^{n-1} x_j y_{k-j}
\quad \quad k = 0,\dots,n-1 </math>

(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).

Generalized DFT

It is possible to shift the transform sampling in time and/or frequency domain by some real shifts a and b, respectively. This is sometimes known as a generalized DFT and has analogous properties to the ordinary DFT:

<math>f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2 \pi i}{n} (j+b) (k+a)}
\quad \quad
 j = 0, \dots, n-1 </math>

Most often, shifts of 1/2 (half a sample) are used. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, a=1/2 produces a signal that is anti-periodic in frequency domain (fj+n=-fj) and vice-versa for b=1/2. Thus, the specific case of a=b=1/2 is known as an odd-time odd-frequency discrete Fourier transform (or O2 DFT). Such shifted transforms are most often used for symmetric data, to represent different boundary symmetries, and for real-symmetric data they correspond to different forms of the discrete cosine and sine transforms.

  
Applications

The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, the Fast Fourier Transform.

(i) 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 (they are redundant for real signals). Then f0/n 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|/n 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). In general, the problem of using the DFT of discrete samples to approximate the Fourier transform of an infinite, continuous signal is called spectral estimation, and involves many more details than are described here. (For example, one often wants to "window" the data in order to reduce the distortion caused by the periodic boundary conditions implicit in the DFT.)

(ii) The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, 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 unnoticable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the discrete cosine transform.)

(iii) Discrete Fourier transforms, especially in multidimensions, are often used to solve partial differential equations. The reason is that it expands the signal in complex exponentials eikx, which are eigenfunctions of differentiation: d/dx eikx = ik eikx. Thus, in the Fourier representation, a linear differential equation is transformed into an ordinary algebraic equation, easily solved. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

(iv) 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.


References

  • E. O. Brigham, The Fast Fourier Transform and Its Applications (Prentice-Hall, Englewood Cliffs, NJ, 1988).
  • A. V. Oppenheim, R. W. Schafer, and J. R. Buck, Discrete-Time Signal Processing (Prentice-Hall, 1999).



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Dicots

... 6 families     Juglandales[?] - 3 families     Leitneriales[?] - 1 family     Myricales[?] - 1 family     Urticales - 6 ...