Mathematics 174 – Applied Mathematics 2 Discussion 6 – The Discrete Fourier Transform April 13, 2000

Background

Let {f_{j}}_{j=0}^{N−1} be a (finite) sequence of complex numbers. The N-point discrete Fourier transform (DFT) of {f_{j}} is the sequence F_{k}, k ∈ Z, defined by

F_{k} = \frac{1}{2π} ∑_{j=0}^{N−1} f_{j} e^{\frac{2πi(jk)}{N}}

If the f_{j} are samples of an analog signal f on the interval [0, Ω]: f_{j} = f (\frac{jΩ}{N}), then the DFT sequence gives approximate values for samples of the Fourier transform of f as follows:

(1)  F_{k} ≐ \frac{N}{Ω} F[f] (\frac{2πk}{Ω} ) .

The complex numbers z_{ℓ} = e^{\frac{2πiℓ}{N}} are all Nth roots of unity: For all ℓ ∈ Z, they satisfy the polynomial equation z^{N} − 1 = 0. Since there are only N distinct roots of this equation in C, in fact z_{ℓ+N} = z_{ℓ} for all ℓ, and z_{0}, z_{1}, z_{2} = z_{1}^{2} … z_{N−1} = z_{1}^{N−1} are one complete set of distinct roots. (In abstract algebra terms, the set of Nth roots of unity is a cyclic subgroup of the multiplicative group of non-zero complex numbers, and z_{1} is a generator.)

Discussion Questions

A) Show that the N-point DFT of any sequence is periodic, with period N: F_{k+N} = F_{k} for all k ∈ Z.

B) If we look at equation (1) and think of F_{k} as giving a way to approximate F[f] (\frac{2πk}{Ω} ), then notice from question A that essentially the maximum frequency value for which we can approximate F[f] with the N-point DFT is ω = \frac{2πN}{Ω} . Actually “even less is true.” Namely, we really want to think of ω ∈ [\frac{−πN}{Ω} , \frac{πN}{Ω} ]. For signals like cos(ωx), the DFT is symmetric, so that we are really talking about 0 ≤ ω ≤ \frac{πN}{Ω} . Is this reasonable? Let’s take Ω = 1. Sketch the graph y = cos(12πx) on [0, 1]. Mark the points on the graph we would be getting by sampling with N = 12 and N = 4. Use what you see to answer the following questions:

1) Find a different signal that “matches” the samples from cos(12πx) at x = j/4 (the sampling points with N = 4). Is there one of the form cos(ωx) with ω < 12π?

2) Find a different signal that “matches” the samples from cos(12πx) at x = j/12 (the sampling points with N = 12). Is there one of the form cos(ωx) with ω < 12π?

The name for the phenomenon you see in parts 1 and 2 is aliasing. An alias of a signal is a different signal that has the same sampled values.

3) With Ω = 1, and N given, why is ω = \frac{πN}{Ω} = πN “special” here? And conversely, if Ω = 1 is given and you have a signal cos(ωx), how often should you sample (i.e. how big does N have to be) to make sure that there is no lower-frequency alias for your sampled values?

There is an extremely important generalization of this train of thought called the Shannon-Nyquist Sampling Theorem. The statement and proof will appear on this semester’s Final Problem Set.

C) If f_{j} and g_{j} are sequences indexed by j ∈ {0, 1, …, N − 1}, then we define their circular convolution to be the sequence h = f ∗ g where

(2)  h_{j} = ∑_{i=0}^{N−1} f_{i}g_{j−i}

where, when j − i falls outside the range {0, 1, …, N − 1}, we take the index modulo N. (Alternatively, we could think of making extended periodic sequences using f and g, then applying the convolution formula (2) to the periodic extensions.)

1) Compute the convolution of the 6-point sequences {f_{j}} = 3, 2, 1, 1, 2, 3 and {g_{j}} = −1, 1, −1, 1, −1, 1.

2) Show (in general) that if F_{k}, G_{k}, and H_{k} are the N-point DFT’s of f_{j}, g_{j}, and

h_{j} = (f ∗ g)_{j} respectively, then for all k,

H_{k} = 2πF_{k}G_{k}

(just like the convolution formula for the ordinary Fourier transform).

D) There is also a DFT version of the Fourier Inversion Formula. Here’s how it works. 1) Show that z_{ℓ} = e^{\frac{2πiℓ}{N}} satisfies:

1 + z_{ℓ} + z_{ℓ}^{2} + ⋯ + z_{ℓ}^{N−1} = \{ \begin{matrix}N & if ℓ ≡ 0 mod N \\ 0 & otherwise \end{matrix}

(Hint: If you have a polynomial

f(z) = a_{0} + a_{1}z + ⋯ + a_{m−1}z^{m−1} + z^{m},

with distinct roots z = z_{1}, …, z_{m} in C, what is the sum of the roots?)

2) If F_{k} is the N-point DFT of f_{j}, show that

f_{j} = \frac{2π}{N} ∑_{k=0}^{N−1} F_{k} e^{\frac{−2πi(kj)}{N}} .

(The right hand side is the “DIFT” of the sequence F_{k}.)

Assignment

Group write-ups due Tuesday, April 18, if possible