CSCI 2227, Introduction to Scientific Computation
Prof. Alvarez

The Discrete Fourier Transform (DFT)

The DFT is a tool used for representing numerical sequence data. The DFT represents a sequence (s₀...s_N-1) as another sequence (s^₀...s^_N-1). The terms of the new sequence may be interpreted as the components of the original sequence at various "frequencies". This page summarizes some key issues surrounding the definition and computation of the DFT.

Review of complex exponentials

Let i denote the square root of -1. This number i may be thought of as the point (0,1) in the Cartesian coordinate plane. Every complex number is a linear combination (with real coefficients) of i and of the number 1; the latter may also be viewed as the point (1,0). This makes the complex numbers correspond exactly to the points in the Cartesian plane. For example, the point (-5,2) represents the complex number -5*1 + 2*i.

If theta is any real number, the exponential e^{i theta} is a complex number that lies on the unit circle centered at the origin of the Cartesian plane. The point e^{i theta} lies at an angle of theta (radians) relative to the positive x axis. For example, the value e^{i π/2} corresponds to a point on the unit circle located at an angle of π/2 radians relative to the positive x axis. This means that the point is located one unit from the origin along the positive y axis. In other words, the value of e^{i π/2} is just i, the square root of -1.

Because of the above, the x and y coordinates of the point that represents the complex exponential e^{i theta} may be computed using cosine and sine projections onto the coordinate axes:

e^{i theta} = cos(theta) + i*sin(theta)

The Fourier basis functions

The DFT relies on a family of basis functions. A given sequence is represented as a linear combination of these functions. Each basis function is associated with a fixed frequency between 0 and N-1.

The Fourier basis function with frequency f is a function of "time" t. Time here is just the integer subindex used to distinguish among the terms of a sequence. Thus, s₃ is the "value of the s sequence at time 3", for example.

The value at time t of the Fourier basis function with frequency f is:

e^{i 2π/N f t}

The terms in the exponent are understood to be multiplied together. Using the cosine and sine formulas for the x and y components of a complex exponential, it's easy to see why this function is referred to as having frequency f. As a function of time t, each of the components (x and y) carries out f full oscillations as t increases from 0 to N-1.

Computing the Fourier coefficients

The basic operation in Fourier analysis is to represent a given sequence s₀,...s_N-1 as a weighted combination of the Fourier basis functions:

s_t = Σ _f=0...N-1 s^_f e^{i 2π/N f t}

Note that this equation states the equality of two functions of time. The values of the two sides of the equation must be equal for every value of the time variable t.

A fundamental identity

Suppose that diff is an integer. Then the value of the following sum:

Σ _p=0...N-1 e^{i 2π/N diff p}

equals N if diff is 0, and it equals 0 if diff s non-zero. To see that this is true, argue by cases. If diff is 0, then each of the N terms in the sum is 1 (because the exponent is 0), so the sum is N. If diff is a non-zero integer, then the terms of the sum are points on the unit circle that are uniformly distributed on the circle at a constant spacing of 2π/N radians; the vector sum of the set of points exactly cancels out to 0.

With the fundamental identity in hand, it's straightforward to figure out how to compute the Fourier coefficients s^_f from the original sequence s_t for t=0...N-1. First assume that the sequence may indeed be written in the desired form for suitable (unknown) values of the coefficients:

s_t = Σ _f=0...N-1 of s^_f e^{i 2π/N f t}

Multiply both sides of the equation by e^{- i 2π/N f0 t}, where f0 is a fixed frequency between 0 and N-1. This produces:

s_t e^{-i 2π/N f0 t} = Σ _f=0...N-1 s^_f e^{i 2π/N (f-f0) t}

Now sum both sides over all values of t between 0 and N-1. This yields:

Σ_t=0...N-1 s_t e^{-i 2π/N f0 t} = Σ_t=0...N-1 Σ_f=0...N-1 s^_f e^{i 2π/N (f-f0) t}

Change the order of the summations on the right-hand side:

Σ_t=0...N-1 s_t e^{-i 2π/N f0 t} = Σ_f=0...N-1 Σ_t=0...N-1 s^_f e^{i 2π/N (f-f0) t}

By the fundamental identity, the right-hand side of the above equation may be seen to equal exactly N times the coefficent s^_f0 corresponding to the frequency f0.

The DFT Formulas

Summarizing the above, we conclude that the Fourier coefficients s^_f of a sequence s_t for t=0...N-1 may be computed as follows:

s^_f = (1/N) Σ_t=0...N-1 s_t e^{-i 2π/N f t}

Similarly, one may see that the original sequence may be obtained from its Fourier coefficients as follows:

s_t = Σ_f=0...N-1 s^_f e^{i 2π/N f t}

The latter equation may be taken as the definition of the DFT of the original sequence. A normalizing factor of 1/sqrt(N) is sometimes used here; in that case, a factor of 1/sqrt(N) will also appear in the formula for the inverse DFT given as the former of the two equations shown here, instead of the factor 1/N as shown. One reason for introducing this factor is the result described below.

Parseval's Theorem

This important result states that the "energy" of the DFT of a sequence is identical to the energy of the original sequence:

Σ_f=0...N-1 |s^_f|² = Σ_t=0...N-1 |s_t|²

The vertical bars | | here denote the modulus of the enclosed complex number (just the absolute value if the number is real). Parseval's theorem holds only if the sum that defines the DFT is normalized by using a multiplicative factor of 1/sqrt(N). To see the truth of Parseval's theorem, the Fundamental Identity stated above is used.

Shift Identity

One often needs the DFT of a sequence obtained by shifting the elements of a given sequence a certain number of positions. For instance, one could be interested in computing the DFT of the sequence s_t-2, where s_t is a sequence whose DFT is already known. The following identity shows that the DFT of the shifted sequence is obtained by multiplying the DFT of the original sequence by a numerical factor that depends on the shift amount.

Let s2 be obtained from s by shifting s by the amount delta. That is, s2_t = s_t+delta (the indices are to be interpreted modulo N, so that N+2 really means 2, for example)). Then the following equality holds:

s2^_f = (1/N) Σ_t=0...N-1 s_t+delta e^{-i 2π/N f t} = (1/N) Σ_t=0...N-1 s_t e^{-i 2π/N f (t-delta)} = e^{i 2π/N f delta} s^_f

CSCI 2227, Introduction to Scientific Computation Prof. Alvarez