FFT Algorithms

The Fast Fourier Transform (FFT) is not a different transform from the DFT. It is an efficient algorithm that computes the same DFT result but with dramatically fewer arithmetic operations. By exploiting symmetry and periodicity of the twiddle factors, FFT reduces DFT complexity from O(N^2) to O(N log2 N), which is the single most important algorithmic advancement in signal processing history.

For GATE aspirants, FFT questions focus on the Radix-2 DIT and DIF butterfly structures, the number of stages and butterflies, the bit-reversal permutation, and computation counts. These are standard numerical problems that appear repeatedly in GATE DSP sections.

Core Concept Explanation

The key insight behind FFT is that the DFT of an N-point sequence can be split into two DFTs of N/2 points each, one using the even-indexed samples and one using the odd-indexed samples. This is the divide and conquer strategy. After computing both half-length DFTs, they are combined using a simple butterfly operation involving one complex multiplication and two complex additions. Applying this split recursively for log2(N) stages gives the complete FFT.

The Radix-2 Decimation in Time (DIT) algorithm separates the input sequence x[n] into even and odd samples before computing the DFT. The input must be in bit-reversed order for the natural output order to emerge. Bit reversal means reversing the binary representation of each index. For N=8, index 3 (011 in binary) becomes 6 (110 in binary) after bit reversal.

The Radix-2 Decimation in Frequency (DIF) algorithm works in the opposite direction. The input is in natural order and the output emerges in bit-reversed order. DIF splits the DFT computation by grouping the first N/2 and second N/2 output samples at each stage. Both DIT and DIF give identical results and have identical computational complexity.

Mathematical Expression

For Radix-2 DIT, the N-point DFT is split as: X[k] = X_even[k] + W_N^k X_odd[k] and X[k+N/2] = X_even[k] - W_N^k X_odd[k], where X_even[k] is the N/2-point DFT of even-indexed samples and X_odd[k] is the N/2-point DFT of odd-indexed samples.

This butterfly equation is the core of the FFT. Written compactly with a = X_even[k] and b = W_N^k X_odd[k]: output_top = a + b, output_bottom = a - b. The factor W_N^k is the twiddle factor for stage k. Note that only one multiplication is needed (to compute W_N^k times X_odd[k]) and then two additions yield both outputs.

The total number of complex multiplications in an N-point Radix-2 FFT is (N/2) log2(N) and the total complex additions are N log2(N). There are log2(N) stages with N/2 butterflies per stage. For N = 8: 3 stages, 4 butterflies per stage, 12 multiplications total.

Practical Understanding

The FFT is in-place computable: each butterfly overwrites its two input values with its two output values, so no additional memory is needed beyond the N-point array. This is critical for embedded systems and real-time processors with limited memory. The entire N-point FFT completes within the same memory used for the input.

In real hardware, FFT processors are designed with multiple butterfly units running in parallel. A modern DSP chip can compute a 1024-point FFT in microseconds. This speed makes real-time spectrum analysis, OFDM modulation in 4G/5G, radar signal processing, and image compression with DCT all practically feasible.

Given:
N = 8 point Radix-2 FFT
Compute: number of stages, butterflies per stage, total butterflies,
total complex multiplications, total complex additions.
Compare with direct DFT.

Why this formula applies:
Radix-2 FFT structure: log2(N) stages, N/2 butterflies per stage.
Each butterfly: 1 complex mult + 2 complex adds.

Formula:
Stages = log2(N)
Butterflies per stage = N/2
Total butterflies = (N/2) * log2(N)
Total complex mults = (N/2) * log2(N)
Total complex adds = N * log2(N)

Substitution for N=8:
log2(8) = 3
N/2 = 4

Calculation:
Stages = 3
Butterflies per stage = 4
Total butterflies = 4 * 3 = 12
Total complex mults = 12
Total complex adds = 8 * 3 = 24

Direct DFT for N=8:
Complex mults = N^2 = 64
Complex adds = N(N-1) = 56

Final Answer:
FFT: 12 mults vs DFT: 64 mults  (5.3x reduction for N=8)
At N=1024: FFT 5120 mults vs DFT 1,048,576 mults (204x reduction)
Speedup grows as N/log2(N) with increasing N.

Exam Tip: For GATE, memorize that Radix-2 FFT of N points has log2(N) stages, N/2 butterflies per stage, and (N/2)log2(N) complex multiplications. For N=8: 12 mults, for N=16: 32 mults, for N=32: 80 mults.

Quick Revision

• FFT computes DFT using O(N log2 N) operations. Direct DFT needs O(N^2). Both give identical output.
• Radix-2 requires N to be a power of 2. Number of stages = log2(N). Butterflies per stage = N/2.
• Total complex multiplications = (N/2) log2(N). Total complex additions = N log2(N).
• DIT: bit-reverse the input, natural order output. DIF: natural order input, bit-reverse the output.
• Butterfly: top_out = a + W_N^r * b, bottom_out = a - W_N^r * b. One mult, two adds per butterfly.
• In-place computation: output of each butterfly overwrites its inputs. No extra memory needed.
• Exam trap: For N=8, log2(8)=3 stages and 4 butterflies each gives 12 total, NOT 24. Do not double-count stages.