Computations in FFT

The Fast Fourier Transform reduces the computational burden of the Discrete Fourier Transform dramatically. Understanding how these savings arise, and how the butterfly diagram encodes them, is essential for both GATE and practical DSP implementation.

Why FFT Exists: The Computation Problem

Computing an N-point DFT directly requires N complex multiplications for each output sample, and there are N output samples. The total cost is therefore N squared complex multiplications and N(N-1) complex additions. For N = 1024, this means over one million complex multiplications, which is expensive in both hardware and time.

The FFT exploits two properties of the twiddle factor W_N^k to collapse this cost significantly. The first is the periodicity property: W_N^(k+N) = W_N^k. The second is the symmetry property: W_N^(k+N/2) = -W_N^k. These two properties together mean many computations are redundant in the direct DFT, and the FFT eliminates that redundancy by recursively splitting the DFT.

Mathematical Expression

The Cooley-Tukey radix-2 algorithm splits an N-point DFT into two N/2-point DFTs. If x[n] is the input, define the even-indexed subsequence x_e[n] = x[2n] and the odd-indexed subsequence x_o[n] = x[2n+1], both of length N/2. The DFT X[k] is then expressed as:

X[k] = X_e[k] + W_N^k * X_o[k] and X[k + N/2] = X_e[k] - W_N^k * X_o[k]

This is the butterfly equation. Each butterfly involves one complex multiplication (the twiddle factor W_N^k) and two complex additions. Applying this recursion log2(N) times gives the complete FFT. Total complex multiplications become (N/2) * log2(N), which is a massive reduction from N^2.

Bit Reversal and Stage Count

The decimation-in-time FFT requires the input to be arranged in bit-reversed order before the butterfly computations begin. Bit reversal means reversing the binary representation of each index. For N=8, index 3 in binary is 011, reversed to 110 which is 6. So input x[3] moves to position 6 in the input array. This permutation is a necessary preprocessing step when implementing the DIT-FFT in-place.

The total number of stages in a radix-2 FFT is log2(N). Each stage contains N/2 butterflies. Therefore the total butterfly count is (N/2) * log2(N). Each butterfly performs exactly one complex multiplication and two complex additions. For N=8: 4 butterflies per stage, 3 stages, total 12 butterflies.

Computational Savings

The comparison between DFT and FFT complexity is a standard GATE topic. For a direct DFT, complex multiplications = N^2 and complex additions = N(N-1). For a radix-2 FFT, complex multiplications = (N/2) * log2(N) and complex additions = N * log2(N). The savings become dramatic as N grows. At N=1024, the direct DFT needs 1,048,576 multiplications while the FFT needs only 5,120.

Numerical Example

Given:
N = 64 (number of DFT points)

Why this formula applies:
Radix-2 FFT reduces N^2 DFT operations to (N/2)log2(N) multiplications

Formula:
Complex multiplications (DFT) = N^2
Complex multiplications (FFT) = (N/2) * log2(N)
Number of stages = log2(N)

Substitution:
DFT: 64^2 = 4096 multiplications
FFT: (64/2) * log2(64) = 32 * 6 = 192 multiplications
Stages: log2(64) = 6
Butterflies per stage: N/2 = 32

Calculation:
Savings = 4096 / 192 = 21.3x fewer multiplications

Final Answer:
FFT requires 192 complex multiplications vs 4096 for DFT.
Speedup factor = 21.3. Total butterflies = 32 * 6 = 192.

Exam Tip: GATE frequently asks to compute the number of complex multiplications in FFT. Always use (N/2)*log2(N) for multiplications and N*log2(N) for additions. For N=8: 12 multiplications, 24 additions. Do not confuse with N^2 which is the direct DFT cost.

In-Place Computation and Memory

The butterfly operation is designed to be in-place, meaning the two output values of a butterfly overwrite the two input memory locations. This keeps memory usage at exactly N complex locations throughout all stages. In-place computation is why the radix-2 FFT is so hardware-friendly and why it maps well to fixed-size processor architectures.

Quick Revision

• Direct DFT: N^2 complex multiplications and N(N-1) additions.
• Radix-2 FFT: (N/2)*log2(N) multiplications and N*log2(N) additions.
• Number of stages in radix-2 FFT = log2(N). Each stage has N/2 butterflies.
• DIT-FFT requires bit-reversal of input indices before processing.
• Butterfly equation: X[k] = A + W*B and X[k+N/2] = A - W*B.
• Twiddle factor symmetry: W_N^(k+N/2) = -W_N^k is the key identity.
• FFT is in-place: output overwrites input in the same N-point memory array.