Discrete Fourier Transforms

A common operation in analyzing various kinds of data is to find the discrete Fourier transform (or spectrum) of a list of values. The idea is typically to pick out components of the data with particular frequencies or ranges of frequencies.

Discrete Fourier transforms.

Here is some data, corresponding to a square pulse:

{-1,-1,-1,-1,1,1,1,1}

Here is the discrete Fourier transform of the data. It involves complex numbers:

Fourier[%]

Here is the inverse discrete Fourier transform:

InverseFourier[%]

(RefLink[Fourier, paclet:ref/Fourier]) works whether or not your list of data has a length which is a power of two:

Fourier[{1,-1,1}]

This generates a list of 200 elements containing a periodic signal with random noise added:

data=Table[N[Sin[30 2 Pi n/200]+(RandomReal[]-1/2)],{n,200}];

The data looks fairly random if you plot it directly:

ListLinePlot[data]

The discrete Fourier transform, however, shows a strong peak at 30+1, and a symmetric peak at 201-30, reflecting the frequency component of the original signal near 30/200:

ListLinePlot[Abs[Fourier[data]],PlotRange->All]

In the Wolfram Language, the discrete Fourier transform (Subscript[v, s]) of a list (Subscript[u, r]) of length n is by default defined to be (1/(Sqrt[n]))(∑_(r=1)^n)(Subscript[u, r])(e^(2πi(r-1)(s-1)/n)). Notice that the zero frequency term appears at position 1 in the resulting list.

The inverse discrete Fourier transform (Subscript[u, r]) of a list (Subscript[v, s]) of length n is by default defined to be (1/(Sqrt[n]))(∑_(s=1)^n)(Subscript[v, s])(e^(-2πi(r-1)(s-1)/n)).

In different scientific and technical fields different conventions are often used for defining discrete Fourier transforms. The option (RefLink[FourierParameters, paclet:ref/FourierParameters]) allows you to choose any of these conventions you want.

Typical settings for (RefLink[FourierParameters, paclet:ref/FourierParameters]) with various conventions.

Two-dimensional discrete Fourier transform.

The Wolfram Language can find discrete Fourier transforms for data in any number of dimensions. In n dimensions, the data is specified by a list nested n levels deep. Two-dimensional discrete Fourier transforms are often used in image processing.

One issue with the usual discrete Fourier transform for real data is that the result is complex-valued. There are variants of real discrete Fourier transforms that have real results. The Wolfram Language has commands for computing the discrete cosine transform and the discrete sine transform.

Discrete real Fourier transforms.

Here is some data corresponding to a square pulse:

pulse={-1,-1,-1,-1,-1,1,1,1,1,1}

Here is the Fourier discrete cosine transform of the data:

FourierDCT[pulse]

Here is the Fourier discrete sine transform of the data:

FourierDST[pulse]

There are four types each of Fourier discrete sine and cosine transforms typically in use, denoted by number or sometimes roman numeral as in "DCTII" for the discrete cosine transform of type 2.

Discrete real Fourier transforms of different types.

The default is type 2 for both (RefLink[FourierDCT, paclet:ref/FourierDCT]) and (RefLink[FourierDST, paclet:ref/FourierDST]).

The Wolfram Language does not need InverseFourierDCT or InverseFourierDST functions because (RefLink[FourierDCT, paclet:ref/FourierDCT]) and (RefLink[FourierDST, paclet:ref/FourierDST]) are their own inverses when used with the appropriate type. The inverse transforms for types 1, 2, 3, 4 are types 1, 3, 2, 4, respectively.

Check that the type 3 transform is the inverse of the type 2 transform:

FourierDCT[FourierDCT[pulse,2],3]

The discrete real transforms are convenient to use for data or image compression.

Here is data that might be like a front or an edge:

data=Table[ArcTan[x-100],{x,1.,200.}];
ListLinePlot[data]

The discrete cosine transform has most of the information in the first few modes:

dct=FourierDCT[data];
ListLinePlot[dct,PlotRange->All]

Reconstruct the front from only the first 20 modes (1/10 of the original data size). The oscillations are a consequence of the truncation and are known to show up in image processing applications as well:

tdata=FourierDCT[PadRight[Take[dct,20],200,0],3];
ListLinePlot[{data,tdata}]