Fourier analysis — DFT, FFT algorithm (Cooley-Tukey): Exercises

Throughout, the same two symbols recur. Let me pin them down in plain words before anything else:

Figure — Fourier analysis — DFT, FFT algorithm (Cooley-Tukey)

Level 1 — Recognition

Problem 1.1

State the value of $ω_{8}^{0}$ , $ω_{8}^{4}$ , and $ω_{8}^{8}$ without computing any exponential, using only "where does the clockwise rotation land?"

Recall Solution 1.1

Picture the clock in the figure above with $8$ tick marks. Each step is one-eighth of a turn.

$ω_{8}^{0}$ : zero steps taken, still at the start $\Rightarrow 1$ .
$ω_{8}^{4}$ : four steps = half a full turn = the point directly opposite $1$ $\Rightarrow - 1$ .
$ω_{8}^{8}$ : eight steps = one full turn, back home $\Rightarrow 1$ . What we used: $ω_{N}^{N} = 1$ and "half a turn is $- 1$ ." No calculator, just geometry of the circle.

Problem 1.2

In the DFT formula $X_{k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{nk}$ , which index is the input position and which is the output frequency? What does $X_{0}$ always equal in words?

Recall Solution 1.2

$n$ = input position (which sample), it is the thing being summed over.
$k$ = output frequency (which coefficient you are building).
$X_{0} = \sum_{n} x_{n} ω_{N}^{0} = \sum_{n} x_{n} \cdot 1 = \sum_{n} x_{n}$ : the plain sum of all samples (the "DC term", equal to $N \times$ the average). At frequency zero the wave never rotates, so every sample counts with weight $1$ .

Level 2 — Application

Problem 2.1

Compute the DFT of $x = (1, 0, 0, 0)$ (a single spike at position $0$ ), $N = 4$ .

Recall Solution 2.1

Only $x_{0} = 1$ is nonzero, so every sum collapses to its $n = 0$ term: $X_{k} = \sum_{n = 0}^{3} x_{n} ω_{4}^{nk} = x_{0} ω_{4}^{0} = 1 for every k .$ Result: $X = (1, 1, 1, 1)$ . What it means: a perfectly sharp spike in time is perfectly flat in frequency — it contains every frequency equally. This is the discrete cousin of "a delta contains all frequencies."

Problem 2.2

Compute the DFT of the constant signal $x = (1, 1, 1, 1)$ , $N = 4$ .

Recall Solution 2.2

$X_{k} = \sum_{n = 0}^{3} 1 \cdot ω_{4}^{nk} = 1 + ω_{4}^{k} + ω_{4}^{2 k} + ω_{4}^{3 k} .$ This is a Geometric Series with ratio $r = ω_{4}^{k}$ .

$k = 0$ : ratio $= 1$ , all four terms are $1$ , sum $= 4$ .
$k = 1, 2, 3$ : $r \neq = 1$ but $r^{4} = ω_{4}^{4 k} = 1$ , so $\frac{r ^{4} - 1}{r - 1} = \frac{0}{r - 1} = 0$ .

Result: $X = (4, 0, 0, 0)$ . What it means: a constant is pure frequency $0$ — the exact mirror image of Problem 2.1. Flat in time $\Rightarrow$ single spike in frequency.

Problem 2.3

Compute the full $N = 4$ DFT of $x = (2, 0, - 2, 0)$ directly.

Recall Solution 2.3

Recall $ω_{4}^{0} = 1, ω_{4}^{1} = - i, ω_{4}^{2} = - 1, ω_{4}^{3} = i$ . Only $x_{0} = 2, x_{2} = - 2$ survive. $X_{k} = 2 ω_{4}^{0} + (- 2) ω_{4}^{2 k} = 2 - 2 ω_{4}^{2 k} = 2 - 2 (- 1)^{k} .$

$k = 0$ : $2 - 2 (1) = 0$ .
$k = 1$ : $2 - 2 (- 1) = 4$ .
$k = 2$ : $2 - 2 (1) = 0$ .
$k = 3$ : $2 - 2 (- 1) = 4$ .

Result: $X = (0, 4, 0, 4)$ . The two nonzero spikes at $k = 1$ and $k = 3 = N - 1$ are the frequency $\pm 1$ pair of a discrete cosine-like wave.

Level 3 — Analysis

Problem 3.1

Prove that for real input $x_{n}$ , the DFT satisfies $X_{N - k} = \overline{X_{k}}$ (the bar means complex conjugate). Then say why this halves the work of storing a real signal's spectrum.

Recall Solution 3.1

Start from the definition at frequency $N - k$ : $X_{N - k} = \sum_{n = 0}^{N - 1} x_{n} ω_{N}^{n (N - k)} = \sum_{n} x_{n} ω_{N}^{n N} ω_{N}^{- nk} .$ Use $ω_{N}^{n N} = (ω_{N}^{N})^{n} = 1^{n} = 1$ (full turns do nothing): $X_{N - k} = \sum_{n} x_{n} ω_{N}^{- nk} .$ Now the conjugate. Because $x_{n}$ is real, $\overline{x_{n}} = x_{n}$ , and $\overline{ω_{N}^{nk}} = ω_{N}^{- nk}$ (conjugating flips the rotation direction). So $\overline{X_{k}} = \overline{\sum_{n} x_{n} ω_{N}^{nk}} = \sum_{n} x_{n} ω_{N}^{- nk} = X_{N - k} . ■$ Why it saves work: the upper half of the spectrum is just the conjugate mirror of the lower half. Store $k = 0, \dots, N /2$ and you know the rest for free — real audio spectra are kept this way.

Problem 3.2

Verify the orthogonality claim of the parent note numerically for $N = 4$ : show $⟨ e^{(1)}, e^{(3)} ⟩ = 0$ , where $e_{n}^{(k)} = e^{2 π ik n / N}$ . Explain which line of the argument makes it vanish.

Recall Solution 3.2

$⟨ e^{(1)}, e^{(3)} ⟩ = \sum_{n = 0}^{3} e^{2 π i (1) n /4} \overline{e^{2 π i (3) n /4}} = \sum_{n = 0}^{3} e^{2 π i (1 - 3) n /4} = \sum_{n = 0}^{3} (e^{- π i})^{n} = \sum_{n = 0}^{3} (- 1)^{n} .$ That is $1 - 1 + 1 - 1 = 0$ . The vanishing line: the ratio $r = e^{- π i} = - 1$ is not $1$ , yet $r^{4} = 1$ , so the Geometric Series sum $\frac{r ^{4} - 1}{r - 1} = \frac{0}{- 2} = 0$ . Orthogonality is nothing but this geometric-series cancellation — the wave completes whole turns and averages to zero.

Level 4 — Synthesis

Problem 4.1

Compute the $N = 8$ FFT of $x = (0, 1, 0, 1, 0, 1, 0, 1)$ using one Cooley–Tukey split (even/odd), and interpret the result. Twiddles you may need: $ω_{8}^{k} = e^{- iπ k /4}$ .

Recall Solution 4.1

Split into even and odd positions.

Even part $x_{0, 2, 4, 6} = (0, 0, 0, 0)$ .
Odd part $x_{1, 3, 5, 7} = (1, 1, 1, 1)$ .

Length-4 DFT of the even part is all zeros: $E_{k} = 0$ for all $k$ . Length-4 DFT of the odd part $(1, 1, 1, 1)$ is (by Problem 2.2 logic, now $N = 4$ ): $O = (4, 0, 0, 0)$ , i.e. $O_{0} = 4, O_{1} = O_{2} = O_{3} = 0$ .

Butterfly recombine $X_{k} = E_{k} + ω_{8}^{k} O_{k}$ and $X_{k + 4} = E_{k} - ω_{8}^{k} O_{k}$ for $k = 0, 1, 2, 3$ :

$k = 0$ : $X_{0} = 0 + ω_{8}^{0} \cdot 4 = 4$ ; $X_{4} = 0 - 4 = - 4$ .
$k = 1, 2, 3$ : $O_{k} = 0$ , so $X_{k} = 0$ and $X_{k + 4} = 0$ .

Result: $X = (4, 0, 0, 0, - 4, 0, 0, 0)$ . Interpretation: the signal $(0, 1, 0, 1, \dots)$ is "constant $\frac{1}{2}$ " plus "the fastest wave $(+ \frac{1}{2}, - \frac{1}{2}, \dots)$ ." Those show as the DC spike at $k = 0$ (value $4$ ) and the Nyquist spike at $k = N /2 = 4$ (value $- 4$ ) — see Nyquist. Every other frequency is exactly absent.

Problem 4.2

Using the recurrence $T (N) = 2 T (N /2) + c N$ , count the exact number of complex multiplications (twiddle multiplies) a radix-2 FFT performs for $N = 8$ , and compare to the naïve DFT's $N^{2}$ .

Recall Solution 4.2

Count per level. At each of the $lo g_{2} 8 = 3$ levels there are $N /2 = 4$ butterflies, and each butterfly uses one twiddle multiply $ω_{N}^{k} O_{k}$ . So the FFT multiply count is $\frac{N}{2} lo g_{2} N = \frac{8}{2} \cdot 3 = 12 complex multiplies.$ (Some of those are trivial multiplies by $ω^{0} = 1$ ; even counting them we get $12$ .) Naïve DFT: $N^{2} = 64$ complex multiplies. Ratio: $64/12 \approx 5.3 \times$ fewer, already at the tiny size $N = 8$ . At $N = 2^{20}$ the same formula gives the parent note's $\approx 5 \times 1 0^{4}$ speedup.

Level 5 — Mastery

Problem 5.1

Two length-4 sequences $a = (1, 2, 0, 0)$ and $b = (1, 1, 0, 0)$ are treated as coefficients of polynomials, and you want their circular convolution $c = a ⊛ b$ (length 4). Use the Convolution Theorem: transform, multiply pointwise, inverse-transform. Then verify by direct convolution.

Recall Solution 5.1

Circular convolution definition: $c_{m} = \sum_{n = 0}^{3} a_{n} b_{(m - n) mod 4}$ .

Route via the DFT (the theorem: convolution in time = pointwise product in frequency). First $A = DFT (a)$ with $ω_{4}^{k} \in {1, - i, - 1, i}$ : $A_{k} = 1 + 2 ω_{4}^{k} \Rightarrow A = (3, 1 - 2 i, - 1, 1 + 2 i) .$ Then $B = DFT (b) = 1 + ω_{4}^{k}$ : $B = (2, 1 - i, 0, 1 + i) .$ Pointwise product $C_{k} = A_{k} B_{k}$ :

$C_{0} = 3 \cdot 2 = 6$ .
$C_{1} = (1 - 2 i) (1 - i) = 1 - i - 2 i + 2 i^{2} = - 1 - 3 i$ .
$C_{2} = (- 1) (0) = 0$ .
$C_{3} = \overline{C_{1}} = - 1 + 3 i$ (real inputs $\Rightarrow$ conjugate symmetry, Problem 3.1).

Inverse DFT $c_{m} = \frac{1}{4} \sum_{k} C_{k} ω_{4}^{- mk}$ , with $ω_{4}^{- 1} = i$ :

$c_{0} = \frac{1}{4} (6 + (- 1 - 3 i) + 0 + (- 1 + 3 i)) = \frac{1}{4} (4) = 1$ .
$c_{1} = \frac{1}{4} (6 + (- 1 - 3 i) i + 0 + (- 1 + 3 i) (- i)) = \frac{1}{4} (6 + (- i + 3) + (i + 3)) = \frac{1}{4} (12) = 3$ .
$c_{2} = \frac{1}{4} (6 + (- 1 - 3 i) (- 1) + 0 + (- 1 + 3 i) (- 1)) = \frac{1}{4} (6 + 1 + 3 i + 1 - 3 i) = \frac{1}{4} (8) = 2.$
$c_{3} = \frac{1}{4} (6 + (- 1 - 3 i) (- i) + 0 + (- 1 + 3 i) (i)) = \frac{1}{4} (6 + (i - 3) + (- i - 3)) = \frac{1}{4} (0) = 0.$

So $c = (1, 3, 2, 0)$ . Direct check (polynomial multiply then wrap mod 4): $(1 + 2 x) (1 + x) = 1 + 3 x + 2 x^{2}$ , coefficients $(1, 3, 2, 0)$ — nothing wraps, so it matches. ✓ What we proved: multiplying in the frequency domain is the same as convolving in time. This is why the FFT makes polynomial and integer multiplication fast.

Problem 5.2

A DFT convention question with a numeric consequence. Physicist Alice uses the forward DFT with a $1/ N$ factor out front and no factor on the inverse; the parent note uses the opposite. For $x = (1, 2, 3, 4)$ , compute Alice's $X_{0}^{Alice}$ and confirm it equals $\frac{1}{N}$ times the parent's $X_{0}$ .

Recall Solution 5.2

Parent's $X_{0} = \sum_{n} x_{n} = 1 + 2 + 3 + 4 = 10$ . Alice's forward transform carries $\frac{1}{N} = \frac{1}{4}$ : $X_{0}^{Alice} = \frac{1}{4} \cdot 10 = 2.5$ . Indeed $2.5 = \frac{1}{4} \cdot 10$ . ✓ Why it matters: the factor $N = ⟨ e^{(k)}, e^{(k)} ⟩$ (squared norm of a basis vector, from Linear Algebra — Orthogonal Bases) has to live somewhere. Whether it sits on the forward map, the inverse, or splits as $1/ N$ on each is pure convention — but you must know which one your library uses or your amplitudes are off by a factor of $N$ .

Recap

Recall Self-test checklist

Which time-domain signal has a totally flat spectrum? ::: A single spike $(1, 0, \dots, 0)$ — its DFT is all $1$ s. Which spectrum comes from a constant signal? ::: A single spike at $k = 0$ : $(N, 0, \dots, 0)$ . Real-input symmetry of the spectrum? ::: $X_{N - k} = \overline{X_{k}}$ . Butterfly count of multiplies for a radix-2 FFT? ::: $\frac{N}{2} lo g_{2} N$ . How do you turn convolution into fast arithmetic? ::: Transform both, multiply pointwise, inverse-transform (Convolution Theorem). To get linear (not circular) convolution from the DFT, what must you do? ::: Zero-pad to length $\geq de g a + de g b + 1$ so no wraparound occurs.