The Cooley–Tukey algorithm recursively breaks down a Discrete Fourier Transform (DFT)
of size N into two smaller DFTs of size N/2.
Key Concepts:
-
Bit-Reversal:
Notice the inputs on the left x[n]. They are not in order (0, 1, 2...).
They are bit-reversed to allow in-place computation.
-
Stages:
There are exactly log2(N) stages of computation.
-
The Butterfly (✖):
Two inputs combine to create two outputs.
Top Output: A + W · B
Bottom Output: A − W · B
-
Twiddle Factor:
The complex exponential multiplier
WNk applied to the bottom branch.
Interactive Mode:
Hover your mouse over any node to trace its dependency path backward.