How it works
The radix-2 Decimation-In-Time (DIT) FFT splits x[n] into even-indexed and odd-indexed sub-sequences recursively until 2-point DFTs remain. Each stage performs butterfly operations: two inputs A and B combine as A + W·B and A − W·B, requiring one complex multiplication and two additions. An N = 8 FFT has log₂(8) = 3 stages with N/2 = 4 butterflies per stage, totalling 12 butterflies. The input sequence must be bit-reversed before computation in DIT-FFT — for N = 8, index 3 (011₂) maps to position 6 (110₂). Decimation-In-Frequency (DIF) FFT reverses this: normal-order input, bit-reversed output.
Key points to remember
Radix-2 FFT requires N to be a power of 2; for arbitrary N, zero-padding to the next power of 2 is the standard approach. Computational complexity drops from O(N²) to O(N log₂ N) — for N = 1024, that is a 100× speedup. Each butterfly stage requires exactly N/2 complex multiplications and N additions. Radix-4 FFT reduces complex multiplications further by processing 4-point DFTs at each stage and is preferred on processors with fast multiply-accumulate units. The FFT output is identical to the DFT — it is an algorithm, not a different transform.
Exam tip
The examiner always asks you to draw the complete 8-point DIT-FFT butterfly diagram with bit-reversed inputs — practice this diagram until you can reproduce all three stages, twiddle factors, and signal flow arrows without looking at a reference.