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

The scenario matrix

Every DFT/FFT problem you will meet falls into one of these case classes. The columns say what makes the case special; the last column names the worked example that covers it.

Case class	What is tricky about it	Covered by
DC / constant input	all samples equal → one spike at $k = 0$ , zeros elsewhere	Ex 1
Single impulse (spike)	one sample nonzero → flat spectrum, every $∣ X_{k} ∣$ equal	Ex 2
Real cosine, on-grid	real input → two mirror spikes ( $k$ and $N - k$ )	Ex 3
General real vector, hand DFT	full computation, all quadrants of $ω_{N}$ used	Ex 4
Same vector via FFT butterflies	check algorithm = definition	Ex 5
Conjugate-symmetry shortcut	real input → compute half, mirror the rest	Ex 6
Degenerate: $N = 1$ and $N = 2$	base cases of the recursion; the "smallest DFTs"	Ex 7
Odd length $N = 3$	radix-2 fails — must use the raw sum	Ex 8
Word problem (real world)	sampling a tone, reading the bins in Hz	Ex 9
Exam twist: cost counting	count multiplies, prove the speedup number	Ex 10

The "signs / quadrants" the parent worried about (like in $arctan$ ) show up here as the four locations of $ω_{N}^{nk}$ on the unit circle: $+ 1$ (angle $0$ ), $- i$ (angle $- 90°$ ), $- 1$ (angle $180°$ ), $+ i$ (angle $+ 90°$ ). Every example below is really just landing on those four points and adding.

The figure below is our master map. The horizontal axis is the real part, the vertical axis the imaginary part, and the white circle is the unit circle (radius $1$ ). Each coloured arrow starts at the origin dot and points to one power of $ω_{4}$ : the yellow arrow to $ω_{4}^{0} = 1$ (pointing right, angle $0°$ ), the blue arrow to $ω_{4}^{1} = - i$ (straight down, angle $- 90°$ because of the minus sign), the pink arrow to $ω_{4}^{2} = - 1$ (pointing left, angle $180°$ ), and the second yellow arrow to $ω_{4}^{3} = i$ (straight up, angle $+ 90°$ ). Every DFT sum below is just adding arrows that land on these four spots.

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

Example 1 — DC / constant input

Worked example The flat signal

Take $N = 4$ and $x = (5, 5, 5, 5)$ — a signal that never changes. Compute all four $X_{k}$ .

Forecast: guess now. If a signal has no wiggle at all, how many frequencies should light up? Where?

Step 1. Write the sum $X_{k} = \sum_{n = 0}^{3} 5 \cdot ω_{4}^{nk} = 5 \sum_{n = 0}^{3} ω_{4}^{nk}$ . Why this step? $x_{n} = 5$ is constant, so it factors straight out of the sum. What is left is a pure sum of roots of unity.

Step 2. For $k = 0$ : every $ω_{4}^{0} = 1$ , so $X_{0} = 5 (1 + 1 + 1 + 1) = 20$ . Why this step? $k = 0$ means "how much zero-frequency (average) is here?" — it is always just $N \times$ the mean.

Step 3. For $k \neq = 0$ : $\sum_{n = 0}^{3} ω_{4}^{nk}$ is a full trip around the circle — a Geometric Series with ratio $r = ω_{4}^{k} \neq = 1$ but $r^{4} = 1$ , so the sum is $\frac{r ^{4} - 1}{r - 1} = 0$ . Why this step? This is the same orthogonality collapse from the parent note: equally spaced points on the circle cancel to zero. Geometrically, the next figure shows four arrows at $0°, 90°, 180°, 270°$ added tip-to-tail — they return to the origin.

Result: $X = (20, 0, 0, 0)$ .

Verify: invert it. $x_{n} = \frac{1}{4} \sum_{k} X_{k} ω_{4}^{- nk} = \frac{1}{4} (20) = 5$ for every $n$ — the flat signal returns. ✓ Sanity: only one nonzero bin, exactly as forecast for a signal with zero wiggle.

The four unit arrows below (one per term of the $k \neq = 0$ sum) chain head-to-tail and land back at the start dot — that is why the sum is exactly zero.

Example 2 — single impulse (the dual of Ex 1)

Worked example All the energy in one sample

$N = 4$ , $x = (1, 0, 0, 0)$ — a single "click". Compute the spectrum.

Forecast: Ex 1 was flat in time and a spike in frequency. This is a spike in time. Guess what the spectrum looks like.

Step 1. $X_{k} = \sum_{n = 0}^{3} x_{n} ω_{4}^{nk} = x_{0} ω_{4}^{0 \cdot k} = 1$ . Why this step? Only $x_{0}$ is nonzero, and its weight is $ω_{4}^{0} = 1$ for every $k$ . All other terms vanish because their sample is $0$ .

Step 2. So $X_{k} = 1$ for all $k$ . Why this step? A sharp click in time contains all frequencies equally — the exact mirror of the constant signal. This is the discrete cousin of "a delta function has a flat spectrum".

Result: $X = (1, 1, 1, 1)$ .

Verify: $∣ X_{k} ∣ = 1$ for all four bins (flat magnitude). Invert: $x_{n} = \frac{1}{4} \sum_{k} 1 \cdot ω_{4}^{- nk}$ . For $n = 0$ this is $\frac{1}{4} (4) = 1$ ; for $n \neq = 0$ the roots sum to $0$ (Ex 1 argument). So $x = (1, 0, 0, 0)$ returns. ✓

Example 3 — real cosine sampled exactly on the grid

Worked example A pure tone at bin 3

$N = 8$ , $x_{n} = cos (\frac{2 π \cdot 3 \cdot n}{8})$ , $n = 0, \dots, 7$ . Find which bins light up.

Forecast: a real cosine — how many spikes, and at which $k$ ?

Step 1. Use Euler: $cos θ = \frac{1}{2} (e^{i θ} + e^{- i θ})$ , so $x_{n} = \frac{1}{2} (e^{2 π i 3 n /8} + e^{- 2 π i 3 n /8})$ . Why this step? The DFT basis is made of complex exponentials, so rewriting the cosine as two exponentials lets us match it against the basis directly — no summing required.

Step 2. Compare with the inverse DFT $x_{n} = \frac{1}{N} \sum_{k} X_{k} e^{+ 2 π i k n / N}$ . Every term there is a positive-exponent exponential $e^{+ 2 π i k n /8}$ with amplitude $\frac{1}{N} X_{k} = \frac{1}{8} X_{k}$ . Why this step? The IDFT tells us exactly which shape each bin contributes: bin $k$ contributes $\frac{1}{8} X_{k} e^{+ 2 π i k n /8}$ . So to read off $X_{k}$ we just match our two exponentials to this template term by term.

Step 3. Match the two pieces of $x_{n}$ to IDFT terms.

$\frac{1}{2} e^{+ 2 π i 3 n /8}$ is the $k = 3$ template with $\frac{1}{8} X_{3} = \frac{1}{2} \Rightarrow X_{3} = 4$ .
$\frac{1}{2} e^{- 2 π i 3 n /8} = \frac{1}{2} e^{+ 2 π i (8 - 3) n /8} = \frac{1}{2} e^{+ 2 π i 5 n /8}$ is the $k = 5$ template with $\frac{1}{8} X_{5} = \frac{1}{2} \Rightarrow X_{5} = 4$ . Why this step? The negative frequency $- 3$ has no bin label of its own on an $8$ -point grid; it wraps to $8 - 3 = 5$ . So the second exponential lands in bin $5$ , giving the mirror spike. All other bins have amplitude $0$ because $x_{n}$ contains no other exponential.

Result: $X_{3} = X_{5} = 4$ , everything else $0$ . Two mirror spikes.

Verify: the bar chart below plots $∣ X_{k} ∣$ : two equal spikes at $k = 3$ (yellow) and $k = 5$ (pink), the dashed line marking Nyquist $N /2 = 4$ . Numerically the raw sum gives $X_{3} = 4$ and $X_{5} = \overline{X_{3}} = 4$ . ✓ Bin $5 = N - 3$ is the folded negative frequency.

Example 4 — general real vector, full hand DFT (all four quadrants)

Worked example

$N = 4$ , $x = (1, 2, 3, 4)$ Compute every $X_{k}$ from the raw definition, using each of the four positions of $ω_{4}$ .

Forecast: which $X_{k}$ will be real, and which pair will be complex conjugates?

Step 1. List the powers: $ω_{4} = - i$ , so $ω_{4}^{0} = 1$ (angle $0$ ), $ω_{4}^{1} = - i$ (angle $- 90°$ ), $ω_{4}^{2} = - 1$ (angle $180°$ ), $ω_{4}^{3} = i$ (angle $+ 90°$ ). Why this step? Every product below lands on one of these four spots; naming them first stops sign errors — this is our version of "check the quadrant".

Step 2. $X_{0} = 1 + 2 + 3 + 4 = 10$ . Why? $k = 0$ weights are all $1$ : the running total (mean $\times N$ ).

Step 3. $X_{1} = 1 + 2 (- i) + 3 (- 1) + 4 (i) = (1 - 3) + (- 2 + 4) i = - 2 + 2 i$ . Why? $k = 1$ steps through $1, - i, - 1, i$ — one full clockwise loop.

Step 4. $X_{2} = 1 + 2 (- 1) + 3 (1) + 4 (- 1) = 1 - 2 + 3 - 4 = - 2$ . Why? $k = 2$ gives $(- 1)^{n}$ : a pure alternating sum, always real.

Step 5. $X_{3} = 1 + 2 (i) + 3 (- 1) + 4 (- i) = (1 - 3) + (2 - 4) i = - 2 - 2 i$ . Why? $k = 3$ steps $1, i, - 1, - i$ — the counter-clockwise mirror of $k = 1$ , so we expect $\overline{X_{1}}$ .

Result: $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ .

Verify: $X_{0}$ and $X_{2}$ are real (as forecast: $k = 0$ and $k = N /2$ are always real for real input); $X_{3} = \overline{X_{1}}$ . Energy check (Parseval): $\sum ∣ x_{n} ∣^{2} = 1 + 4 + 9 + 16 = 30$ ; $\frac{1}{N} \sum ∣ X_{k} ∣^{2} = \frac{1}{4} (100 + 8 + 4 + 8) = \frac{120}{4} = 30$ . ✓

Example 5 — the same vector via FFT butterflies

Worked example Cooley–Tukey on

$x = (1, 2, 3, 4)$ Reproduce Ex 4 using the even/odd split, and count operations.

Forecast: the FFT must give the identical answer $(10, - 2 + 2 i, - 2, - 2 - 2 i)$ — but with fewer multiplies. How many fewer?

Step 1. Split: even-indexed $x_{0, 2} = (1, 3)$ , odd-indexed $x_{1, 3} = (2, 4)$ . Why this step? This is the core Cooley–Tukey move (Divide and Conquer Algorithms) — turn one size-4 DFT into two size-2 DFTs.

Step 2. Length-2 DFTs (here $ω_{2} = - 1$ , so DFT of $(a, b)$ is $(a + b, a - b)$ ): $E_{0} = 1 + 3 = 4, E_{1} = 1 - 3 = - 2$ ; $O_{0} = 2 + 4 = 6, O_{1} = 2 - 4 = - 2$ . Why this step? Size-2 is the base case — just a sum and a difference, no multiplies at all.

Step 3. Twiddles $ω_{4}^{0} = 1, ω_{4}^{1} = - i$ . Butterflies: $X_{0} = E_{0} + ω_{4}^{0} O_{0} = 4 + 6 = 10$ ; $X_{1} = E_{1} + ω_{4}^{1} O_{1} = - 2 + (- i) (- 2) = - 2 + 2 i$ ; $X_{2} = E_{0} - ω_{4}^{0} O_{0} = 4 - 6 = - 2$ ; $X_{3} = E_{1} - ω_{4}^{1} O_{1} = - 2 - 2 i$ . Why this step? Each pair $(X_{k}, X_{k + 2})$ shares the product $ω_{4}^{k} O_{k}$ — computed once, then added and subtracted (the free second half).

Result: $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ — identical to Ex 4. ✓

Verify: matches Ex 4 exactly. Now the honest op-count, multiplies and additions:

Naïve DFT: $N^{2} = 16$ complex multiplies and $N (N - 1) = 12$ complex additions.
This FFT: the two size-2 DFTs use $0$ multiplies (only $4$ add/subtracts total); the combine stage has $N /2 = 2$ twiddle multiplies (and one is by $ω_{4}^{0} = 1$ , so really $1$ nontrivial) plus $N = 4$ add/subtracts for the four butterfly outputs. So multiplies drop from $16$ to $2$ and additions from $12$ to $8$ . Even at tiny $N = 4$ both counts fall; the multiply saving is what compounds as $N$ grows (see Ex 10).

The butterfly figure below shows the two blue inputs $(E_{0}, O_{0})$ and $(E_{1}, O_{1})$ on the left, the yellow outputs $X_{0} \dots X_{3}$ on the right, and the pink edges are the ones carrying the twiddle multiply $ω_{4}^{k}$ .

Example 6 — conjugate-symmetry shortcut

Worked example Compute only half, mirror the rest

$N = 8$ , real input $x = (0, 1, 0, - 1, 0, 1, 0, - 1)$ . Use $X_{N - k} = \overline{X_{k}}$ to avoid half the work.

Forecast: for real input, how many independent complex bins are there really, out of 8?

Step 1. Recognise the signal in closed form. Test $x_{n} = sin (\frac{2 π \cdot 2 n}{8})$ : at $n = 1$ , $sin (π /2) = 1$ ✓; at $n = 2$ , $sin (π) = 0$ ✓; at $n = 3$ , $sin (3 π /2) = - 1$ ✓. So $x_{n} = sin (2 π \cdot 2 n /8)$ , a pure sine of frequency $2$ . Why this step? Naming the closed form lets us predict the spikes ( $k = 2$ and its mirror) before computing, and turns the sum into an Euler match like Ex 3.

Step 2. Write $sin θ = \frac{1}{2 i} (e^{i θ} - e^{- i θ})$ and match to the IDFT template $\frac{1}{8} X_{k} e^{+ 2 π i k n /8}$ (exactly as in Ex 3). The $+ 2$ exponential gives $\frac{1}{8} X_{2} = \frac{1}{2 i} \Rightarrow X_{2} = \frac{8}{2 i} = - 4 i$ ; the $- 2$ exponential wraps to bin $6$ with $\frac{1}{8} X_{6} = - \frac{1}{2 i} \Rightarrow X_{6} = + 4 i$ . All other bins $0$ . Why this step? Same trick as Ex 3, but sine's $\frac{1}{2 i}$ makes the coefficients imaginary and opposite in sign (sine is an odd function).

Step 3. Independent bins: $X_{0}, \dots, X_{4}$ (that's $\frac{N}{2} + 1 = 5$ ); the rest come free from $X_{8 - k} = \overline{X_{k}}$ . Why this step? Real input has conjugate symmetry, so we compute bins $0$ through $N /2$ and reflect the others without more work.

Result: $X = (0, 0, - 4 i, 0, 0, 0, 4 i, 0)$ .

Verify: $X_{6} = \overline{X_{2}} = \overline{- 4 i} = 4 i$ ✓. Parseval: $\sum ∣ x_{n} ∣^{2} = 4 \cdot 1 = 4$ ; $\frac{1}{8} \sum ∣ X_{k} ∣^{2} = \frac{1}{8} (16 + 16) = 4$ ✓. Forecast confirmed: only 5 independent bins.

Example 7 — degenerate base cases $N = 1$ and $N = 2$

Example 8 — odd length $N = 3$ (radix-2 forbidden)

Worked example When Cooley–Tukey can't split evenly

$N = 3$ , $x = (1, 1, 1)$ and then $x = (1, 2, 3)$ . Compute from the raw sum — you cannot halve an odd length.

Forecast: what happens to the even/odd trick when $N = 3$ ?

Step 1. $ω_{3} = e^{- 2 π i /3}$ . Its powers are $ω_{3}^{0} = 1$ , $ω_{3}^{1} = - \frac{1}{2} - \frac{3}{2} i$ , $ω_{3}^{2} = - \frac{1}{2} + \frac{3}{2} i$ . Why this step? $3$ is prime — radix-2 needs $N = 2^{m}$ , so we go back to the definition (or use Bluestein / mixed-radix, mentioned in the parent's mistakes). We list the three circle positions first, spaced $120°$ apart.

Step 2, case $(1, 1, 1)$ . $X_{0} = 1 + 1 + 1 = 3$ ; $X_{1} = 1 + ω_{3} + ω_{3}^{2} = 0$ ; $X_{2} = 1 + ω_{3}^{2} + ω_{3}^{4} = 1 + ω_{3}^{2} + ω_{3} = 0$ (since $ω_{3}^{4} = ω_{3}^{3} \cdot ω_{3} = ω_{3}$ ). Why this step? Constant signal → single DC spike, exactly Ex 1's logic at $N = 3$ : three equally spaced arrows sum to zero. Note $ω_{3}^{4} = ω_{3}$ because $ω_{3}^{3} = 1$ .

Step 3, case $(1, 2, 3)$ . First $X_{0} = 1 + 2 + 3 = 6$ (the sum, since all weights are $1$ ). Then $X_{1} = 1 \cdot ω_{3}^{0} + 2 \cdot ω_{3}^{1} + 3 \cdot ω_{3}^{2} = 1 + 2 (- \frac{1}{2} - \frac{3}{2} i) + 3 (- \frac{1}{2} + \frac{3}{2} i) .$ Real part: $1 - 1 - \frac{3}{2} = - \frac{3}{2}$ . Imaginary part: $- 3 i + \frac{3 3}{2} i = \frac{3}{2} i$ . So $X_{1} = - \frac{3}{2} + \frac{3}{2} i$ . Finally $X_{2} = \overline{X_{1}} = - \frac{3}{2} - \frac{3}{2} i$ . Why this step? We plug each sample into its circle position and add real and imaginary parts separately. $X_{0}$ is always the plain sum. $X_{2} = \overline{X_{1}}$ because the input is real, so conjugate symmetry $X_{N - k} = \overline{X_{k}}$ gives the last bin for free — the same shortcut as Ex 6, now at $N = 3$ .

Result: $(1, 1, 1) \to (3, 0, 0)$ ; $(1, 2, 3) \to (6, - \frac{3}{2} + \frac{3}{2} i, - \frac{3}{2} - \frac{3}{2} i)$ .

Verify $(1, 2, 3)$ : $∣ X_{1} ∣^{2} = \frac{9}{4} + \frac{3}{4} = 3$ . Parseval: $\sum ∣ x_{n} ∣^{2} = 1 + 4 + 9 = 14$ ; $\frac{1}{3} (36 + 3 + 3) = \frac{42}{3} = 14$ ✓.

Example 9 — real-world word problem

Worked example Reading a bin in hertz

You sample an audio signal at $f_{s} = 8000$ Hz and take $N = 1024$ samples. The FFT shows a big spike at bin $k = 128$ . What frequency (in Hz) is the tone?

Forecast: guess — is a spike at bin 128 out of 1024 a low, middle, or high note?

Step 1. Bin spacing $Δ f = \frac{f _{s}}{N} = \frac{8000}{1024} = 7.8125$ Hz. Why this step? The DFT splits the frequency axis $[0, f_{s})$ into $N$ equal bins; bin $k$ sits at $k \cdot Δ f$ . (This is Sampling & Aliasing (Nyquist) arithmetic.)

Step 2. Frequency $= k \cdot Δ f = 128 \times 7.8125 = 1000$ Hz. Why this step? Multiply bin index by spacing. Since $128 < N /2 = 512$ , this is a genuine positive frequency, not an alias.

Step 3. Sanity on range: the highest representable frequency is the Nyquist $f_{s} /2 = 4000$ Hz at bin $512$ . $1000$ Hz is well below it. Why this step? Confirms we are reading a real tone, not a folded-back alias.

Result: the tone is $1000$ Hz — a middle-register note, since bin $128$ is only a quarter of the way to Nyquist.

Verify: $128 \times \frac{8000}{1024} = \frac{1024000}{1024} = 1000$ Hz ✓. Units: (bins) $\times$ (Hz/bin) = Hz ✓.

Example 10 — exam twist: prove the speedup number

Worked example Count the multiplies

For $N = 1024 = 2^{10}$ , how many complex multiplies does the naïve DFT need vs the radix-2 FFT, and what is the speedup?

Forecast: the parent quoted speedup $N / lo g_{2} N$ . For $N = 1024$ , roughly what factor — tens, hundreds, thousands?

Step 1. Naïve: $N^{2} = 102 4^{2} = 1, 048, 576$ complex multiplies. Why this step? Each of $N$ outputs is a sum of $N$ products — the $O (N^{2})$ cost from the parent note.

Step 2. FFT: $\frac{N}{2} lo g_{2} N$ nontrivial twiddle multiplies $= \frac{1024}{2} \times 10 = 5120$ . Why this step? There are $lo g_{2} N = 10$ stages (Master Theorem on $T (N) = 2 T (N /2) + c N$ ), each with $N /2 = 512$ butterflies, one twiddle multiply each.

Step 3. Speedup $\frac{N ^{2}}{\frac{N}{2} lo g _{2} N} = \frac{2 N}{lo g _{2} N} = \frac{2 \times 1024}{10} = 204.8$ ; the parent's looser estimate $N / lo g_{2} N = 102.4$ . Why this step? Depending on whether you compare $N^{2}$ against $N lo g N$ or the tighter $\frac{N}{2} lo g N$ , the factor is roughly $100$ – $200 \times$ .

Result: naïve $\approx 1.05 \times 1 0^{6}$ , FFT $\approx 5120$ , speedup $\approx 200 \times$ .

Verify: $102 4^{2} /5120 = 204.8$ ✓. This is why real-time audio works: $5120$ multiplies at $8$ kHz is trivial for any chip; a million is not.

Recall

Recall Scenario check

Constant signal $(c, \dots, c)$ , $N$ points — spectrum? ::: $X_{0} = N c$ , all other $X_{k} = 0$ . Single impulse $(1, 0, \dots, 0)$ — spectrum? ::: Flat: $X_{k} = 1$ for all $k$ . Real cosine at integer freq $f$ , length $N$ — which bins? ::: $k = f$ and $k = N - f$ , each amplitude $N /2$ . Real sine at freq $f$ — bin values? ::: $X_{f} = - i N /2$ , $X_{N - f} = + i N /2$ (imaginary, opposite signs). Why can't radix-2 FFT handle $N = 3$ ? ::: $3$ is not a power of $2$ ; you cannot split into equal even/odd halves. Bin $k$ of an $N$ -point FFT sampled at $f_{s}$ sits at what frequency? ::: $k \cdot f_{s} / N$ Hz (for $k < N /2$ ). How many independent complex bins for a real length- $N$ input? ::: $N /2 + 1$ (bins $0$ through $N /2$ ); the rest are conjugates. Multiply count of a radix-2 FFT? ::: About $\frac{N}{2} lo g_{2} N$ twiddle multiplies.

See the Convolution Theorem for the payoff of all this speed: fast multiplication of polynomials and integers.