Mathematics 174 – Applied Mathematics 2 Selected Solutions – Discussion 6 April 25, 2000

C) 2. Let h_{j} be the convolution sequence h = f ∗g. Then taking its DFT, and interchanging the summations, and splitting the exponential into a product of two factors, we have

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

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

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

For each value of ℓ, in the inner sum over j, m = j − ℓ also ranges over all classes mod N. Hence we can factor this as a product of two sums and rewrite the inner one above as follows:

\begin{matrix}= \frac{1}{2π} ( ∑_{ℓ=0}^{N−1} f_{ℓ}e^{2πi(ℓk)/N}) ( ∑_{m=0}^{N−1} g_{m}e^{2πi(mk)/N}) \\ = F_{k} · 2πG_{k} \end{matrix}

Hence the convolution formula holds.

D) 1. Everyone correctly saw that if the powers z_{ℓ}^{k} k = 0, …, N − 1 give all of the Nth roots of unity in C, then

(1)  \frac{1}{N} ∑_{k=0}^{N−1} z_{ℓ}^{k} = \{ \begin{matrix}1 & if ℓ ≡ 0 mod N \\ 0 & otherwise \end{matrix}

However, if N is composite, and gcd(ℓ, N) ≠ 1, then the powers z_{ℓ}^{k} will not yield all the Nth roots of unity.

For example, with N = 6, z_{2} = e^{4πi/6} = e^{2πi/3} satisfies z_{2}^{3} − 1 = 0 (hence also z_{2}^{6} − 1 = 0). But the powers of z_{2} will give only cube roots of unity, not all the 6th roots of unity. We will get each cube root of unity twice if we consider the powers z_{2}^{k}, k = 0, … 5.

In general, if gcd(ℓ, N) = m > 1, then the powers z_{ℓ}^{k} are all the (N/m)th roots of unity, and as k goes from 0 to N − 1, each (N/m)th root of unity is obtained exactly m times. The (N/m)th roots of unity are the roots of the equation z^{N/m} − 1 = 0, so their sum is also zero for the same reason as in the first case. This shows (1) holds in this case also.

D) 2. The Discrete Inverse Transform: Let F_{k} be the DFT of a sequence f_{j}. Then we work with the jth term in the inverse transform sequence, interchanging order of summation and combining the exponentials. (Note that if ℓ, j ∈ {0, 1, …, N − 1}, then the only time when ℓ − j ≡ 0 mod N as in the statement of part 1 is when ℓ = j.)

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

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

= \frac{1}{N} ∑_{ℓ=0}^{N−1} f_{ℓ} · \{ \begin{matrix}N & if ℓ = j \\ 0 & if ℓ ≠ j \end{matrix}

= \frac{1}{N} (f_{0} · 0 + ⋯ + f_{j−1} · 0 + f_{j} · N + f_{j+1} · 0 + ⋯ + f_{N−1} · 0)

= f_{j}

Hence the “DIFT undoes the DFT”.