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

Step 0 — The one word we must define first: $ω_{N}$

WHAT. We will lean on one object again and again, so let us build it before anything else. Take a circle of radius $1$ centred at the origin. Mark $N$ equally spaced dots on it, starting at the point $(1, 0)$ and going clockwise. Call the first dot after the start $ω_{N}$ (read "omega-sub-N").

WHY clockwise? Because the DFT uses $e^{- 2 π i / N}$ — the minus sign is a clockwise turn. We will see exactly where that minus comes from later; for now just accept the dots go clockwise.

PICTURE. In the figure, the amber dot is $ω_{N}$ . Walking $k$ dots around lands you on $ω_{N}^{k}$ (multiplying by $ω_{N}$ is "turn one more step"). After $N$ dots you are home: $ω_{N}^{N} = 1$ . These are the $N$-th roots of unity.

$ω_{N} = one clockwise step of 36 0^{\circ} / N e^{- 2 π i / N}, dot number k ω_{N}^{k}, back to start ω_{N}^{N} = 1$

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

Step 1 — A "pure wave" on $N$ points is a dot spinning by fixed steps

WHAT. Fix a frequency $k$ (a whole number). Build a list of $N$ points by starting at the dot $ω_{N}^{0} = 1$ and, at each new sample $n$ , jumping $k$ dots clockwise. Sample $n$ sits at $ω_{N}^{nk}$ . Collect those $N$ points into one object and call it $e^{(k)}$ .

$e_{n}^{(k)} = ω_{N}^{nk}, which sample n, which frequency k, total dots jumped nk$

WHY. This list is the discrete cousin of $cos$ and $sin$ : its horizontal shadow traces a cosine, its vertical shadow a sine. Frequency $k$ = "how many dots we jump per sample" = how fast the wave wiggles. These lists are our building blocks — the basis vectors of the parent note.

PICTURE. For $N = 8$ , $k = 1$ steps one dot per sample (slow spin, slow wiggle); $k = 2$ steps two dots per sample (faster). Same circle, different stride. In the figure, follow the cyan curve ( $k = 1$ ) — one gentle hump — versus the amber curve ( $k = 2$ ) — twice as many wiggles across the same $8$ samples.

Step 2 — The DFT asks "how much of each wave is in my data?"

WHAT. Given data $x_{0}, \dots, x_{N - 1}$ , the DFT coefficient $X_{k}$ measures how strongly wave $k$ appears in the data. We compute it by lining each sample up against wave $k$ and adding:

$X_{k} = \sum_{n = 0}^{N - 1} data sample x_{n} \cdot wave k at sample n ω_{N}^{nk}$

Definition Inner product and why a conjugate appears

To "match" two lists of complex numbers $a$ and $b$ we use the inner product $⟨ a, b ⟩ = \sum_{n} a_{n} \overline{b_{n}}$ , where $\overline{b_{n}}$ is the complex conjugate (flip the sign of the imaginary part, i.e. reflect the dot across the horizontal axis). The conjugate is essential: it makes $⟨ a, a ⟩ = \sum_{n} ∣ a_{n} ∣^{2}$ a real, non-negative "length-squared". Projecting the data onto wave $k$ means computing $⟨ x, e^{(k)} ⟩ = \sum_{n} x_{n} \overline{e_{n}^{(k)}} = \sum_{n} x_{n} \overline{ω_{N}^{nk}} = \sum_{n} x_{n} ω_{N}^{nk}$ — and because $\overline{ω_{N}^{nk}} = ω_{N}^{- nk}$ ... wait: $ω_{N} = e^{- 2 π i / N}$ , so $\overline{ω_{N}^{nk}} = e^{+ 2 π ink / N}$ . Writing the forward DFT with the un-conjugated weight $ω_{N}^{nk} = e^{- 2 π ink / N}$ is exactly the projection onto the conjugated basis. That conjugation is where the minus sign in $ω_{N}$ comes from.

WHY the multiply-and-add? This is a projection onto an orthogonal basis. Because the waves are orthogonal (parent Step 2, a Geometric Series argument: $⟨ e^{(k)}, e^{(j)} ⟩ = N δ_{k j}$ ), matching the data against wave $k$ picks out exactly wave $k$ 's share and cancels every other wave to zero. No solving equations — just a weighted sum.

PICTURE. Think of $N$ tuning forks, one per frequency; $X_{k}$ is how loud fork $k$ rings. The figure stacks the $N \times N$ grid of weights $ω_{N}^{nk}$ — colour = the angle of each weight. Read it like this: the top row ( $k = 0$ ) is a single flat colour — every weight is $1$ , so $X_{0}$ is just the plain sum. Walk down one row ( $k$ grows) and the colours cycle faster across the row: row $k$ sweeps through $k$ full colour-cycles as $n$ runs $0 \to N - 1$ . The whole grid has $N \times N$ coloured cells — that is literally the $N^{2}$ multiplies the FFT will avoid.

Step 3 — Split the sum: even samples, odd samples

WHAT. Assume $N$ is even. Sort the samples by index parity: the even-indexed ones $x_{0}, x_{2}, x_{4}, \dots$ and the odd-indexed ones $x_{1}, x_{3}, x_{5}, \dots$ . Split the one big sum into two:

$X_{k} = even samples m = 0 \sum N /2 - 1 x_{2 m} ω_{N}^{2 mk} + odd samples m = 0 \sum N /2 - 1 x_{2 m + 1} ω_{N}^{(2 m + 1) k}$

WHY split by parity? Because — and this is the whole magic — the even part will turn out to be a smaller DFT, and so will the odd part. This is a divide-and-conquer move: solve two half-size copies of the same problem.

PICTURE. The figure combs the data into two shorter rows: the cyan bars are the "even comb" ( $x_{0}, x_{2}, x_{4}, x_{6}$ ), the amber bars the "odd comb" ( $x_{1}, x_{3}, x_{5}, x_{7}$ ). Notice each comb has exactly $N /2$ teeth — the two half-size problems.

Step 4 — Pull out one twiddle factor from the odd part

WHAT. In the odd sum, the exponent is $(2 m + 1) k = 2 mk + k$ . Since $ω_{N}^{2 mk + k} = ω_{N}^{k} \cdot ω_{N}^{2 mk}$ , the factor $ω_{N}^{k}$ does not depend on $m$ , so it slides outside the sum:

$X_{k} = \sum_{m} x_{2 m} ω_{N}^{2 mk} + the "twiddle", pulled out front ω_{N}^{k} \sum_{m} x_{2 m + 1} ω_{N}^{2 mk}$

WHY pull it out? Because once it is gone, both remaining inner sums have the identical weight $ω_{N}^{2 mk}$ . Identical structure = we can reuse one sub-routine for both. The lone leftover $ω_{N}^{k}$ is called the twiddle factor — a single rotation applied per output.

PICTURE. In the figure the two cyan boxes are the even and odd sums; they now carry the same weight $ω_{N}^{2 mk}$ . The amber dot between them is the twiddle $ω_{N}^{k}$ — the one rotation pulled out front, sitting in front of the odd box.

Step 5 — The key identity: $ω_{N}^{2} = ω_{N /2}$

WHAT. Look at the shared weight $ω_{N}^{2 mk}$ . Group the square: $ω_{N}^{2 mk} = (ω_{N}^{2})^{mk}$ . Now compute $ω_{N}^{2}$ :

$ω_{N}^{2} = (e^{- 2 π i / N})^{2} = e^{- 2 π i / (N /2)} = ω_{N /2}$

WHY does this finish the reduction? $ω_{N /2}$ is the twiddle for a half-size grid. So each inner sum, $\sum_{m} x_{2 m} ω_{N /2}^{mk} = E_{k} and \sum_{m} x_{2 m + 1} ω_{N /2}^{mk} = O_{k},$ is literally an $N /2$ -point DFT — $E_{k}$ of the even samples, $O_{k}$ of the odd samples. We have turned one size- $N$ problem into two size- $N /2$ problems.

PICTURE. In the figure the faint white dots are the big $N = 8$ circle; the amber dots are the half-size $N /2 = 4$ circle. Stepping around the big circle at double stride (squaring) lands exactly on the amber dots — squaring = skipping every other dot = dropping onto a smaller circle.

$X_{k} = DFT_{N /2} of evens E_{k} + twiddle ω_{N}^{k} DFT_{N /2} of odds O_{k}$

Step 6 — The free second half: one sign flip gives two outputs

WHAT. We have $X_{k} = E_{k} + ω_{N}^{k} O_{k}$ for $k = 0, \dots, \frac{N}{2} - 1$ . But $E_{k}$ and $O_{k}$ are half-size DFTs, so they only naturally produce $N /2$ values — how do we get outputs $X_{N /2}, \dots, X_{N - 1}$ ? Ask what happens at $k + \frac{N}{2}$ . Two facts:

$E_{k}$ and $O_{k}$ repeat with period $N /2$ (a DFT of length $N /2$ wraps around): $E_{k + N /2} = E_{k}$ , same for $O$ .
The twiddle flips sign: $ω_{N}^{k + N /2} = ω_{N}^{N /2} ω_{N}^{k} = (- 1) ω_{N}^{k}$ , because $ω_{N}^{N /2}$ is the dot exactly half a lap around $= - 1$ .

WHY this is the payoff. Put those together:

$X_{k} = E_{k} + ω_{N}^{k} O_{k} X_{k + N /2} = E_{k} - ω_{N}^{k} O_{k}$

The two outputs share the same multiply $ω_{N}^{k} O_{k}$ — one costs a $+$ , the other a $-$ . Two results, one multiplication. This is the butterfly.

PICTURE. In the figure, the two cyan inputs $E_{k}, O_{k}$ enter on the left; the amber node in the middle is the single multiply $ω_{N}^{k} O_{k}$ ; the crossing lines carry it up (add → top output $X_{k}$ ) and down (subtract → bottom output $X_{k + N /2}$ ). Those crossing wings are why it is called a butterfly.

Step 7 — Edge & degenerate cases (never leave the reader stranded)

WHAT / WHY / PICTURE, four corners you will hit:

$N = 1$ (base case). A single sample has nothing to combine: $X_{0} = x_{0}$ . The recursion stops here — this is the "size-1 circle", one lonely dot. Every FFT bottoms out at these.
$N$ odd / not a power of 2. The even–odd split needs $N$ even; radix-2 needs $N = 2^{m}$ . For other $N$ you pad with zeros to the next power of two, or use mixed-radix / Bluestein. The picture: you cannot comb an odd row into two equal combs.
$k = 0$ (DC term). Every twiddle is $ω_{N}^{0} = 1$ : $X_{0} = \sum_{n} x_{n}$ , just the plain sum (the average $\times N$ ). The "wave" of frequency $0$ is a flat line — no wiggle at all.
$k = N /2$ (Nyquist). The fastest resolvable wave: it alternates $+ 1, - 1, + 1, - 1$ . Here $ω_{N}^{N /2} = - 1$ , so $X_{N /2} = \sum_{n} (- 1)^{n} x_{n}$ . Beyond $k = N /2$ , indices alias to negative frequencies (parent's last mistake). See Sampling & Aliasing (Nyquist).

PICTURE. The figure overlays the two extreme waves: the cyan flat line is the DC wave ( $k = 0$ , no wiggle); the amber zig-zag is the Nyquist wave ( $k = N /2$ , fastest possible alternation). Every real frequency lives between these two.

The one-picture summary

Everything above collapses into a single diagram for $N = 4$ : two length-2 DFTs (each a single butterfly) feed one layer of twiddles into two output butterflies. Trace $x = (1, 2, 3, 4)$ through it and you get $X = (10, - 2 + 2 i, - 2, - 2 - 2 i)$ — the same answer as the brute-force $N^{2}$ sum, at a fraction of the cost. Read it left to right: the four inputs enter on the left; the first pair of crossings (cyan/amber) produces the half-DFT values $E_{0}, E_{1}, O_{0}, O_{1}$ in the middle; the second pair of crossings applies the twiddles and add/subtract to give the four outputs $X_{0}, \dots, X_{3}$ on the right.

Recall Feynman retelling (plain words, no symbols)

Picture a wheel with $N$ equally spaced pegs. A "wave" is a marker hopping a fixed number of pegs each tick — hop a lot for a fast wave, hop a little for a slow one. The DFT asks, for every possible hop-size, "how much of this wave is hiding in my data?" — by laying the data against that wave and adding up.

Doing that for every wave against every sample is a giant $N \times N$ grid of little multiplies — slow. The FFT's trick: split your data into the even-numbered and odd-numbered samples. Because of one clean fact — hopping double-fast on the big wheel is the same as hopping normally on a wheel with half the pegs — each half becomes the same kind of problem, but half the size. Solve those two smaller problems, then stitch: for each pair you spin the odd answer once (the "twiddle"), then add it to get one output and subtract it to get another. Two answers, one spin. That paired add/subtract is the butterfly.

Keep halving — even/odd, even/odd — until each piece is a single number that answers itself. About $lo g_{2} N$ layers of halving, each layer touching all $N$ numbers once. That is why $N^{2}$ becomes $N lo g N$ , and why your phone can do a Fourier transform on a photo before you finish blinking.

Recall Quick self-check

What single identity turns each half-sum into a smaller DFT? ::: $ω_{N}^{2} = ω_{N /2}$ — squaring the twiddle drops you onto the half-size circle. Why does $X_{k + N /2}$ cost almost nothing extra? ::: $ω_{N}^{k + N /2} = - ω_{N}^{k}$ , so only the sign of the shared product flips. What are the two outputs of one butterfly? ::: $E_{k} + ω_{N}^{k} O_{k}$ and $E_{k} - ω_{N}^{k} O_{k}$ . Where does the recursion stop? ::: At $N = 1$ , where $X_{0} = x_{0}$ .