FFT Algorithm

Introduction

The Fast Fourier Transform (FFT) is not a new transform — it computes the exact same DFT. What makes it revolutionary is HOW it computes it. The direct computation of an $N$-point DFT requires $O(N^2)$ complex multiplications. The FFT exploits symmetry and periodicity of the twiddle factors $W_N^{kn}$ to reduce this to $O(N\log_2 N)$ — a dramatic speedup. For a 1024-point transform, that is roughly 100× fewer operations. For a million points, it is 50,000× fewer.

Published by Cooley and Tukey in 1965 (though the basic idea was known to Gauss around 1805), the FFT is considered one of the most important algorithms of the 20th century. It made real-time spectral analysis, efficient digital filtering, OFDM communication, and countless other applications practical. For B.Tech students, understanding the FFT means understanding how billions of devices perform frequency analysis efficiently.

The Computational Problem

The DFT of an $N$-point sequence requires: $$X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}, \quad k = 0, 1, \ldots, N-1$$

Direct computation: Each of the $N$ output values $X[k]$ requires $N$ complex multiplications and $N-1$ complex additions. Total: $N^2$ multiplications and $N(N-1)$ additions.

For $N = 1024$: Direct DFT needs ~1 million multiplications. FFT needs ~5,000. That is a 200× improvement.

Key Properties Exploited

The FFT exploits two properties of the twiddle factor $W_N = e^{-j2\pi/N}$:

Periodicity: $W_N^{k+N} = W_N^k$ (the factor repeats every $N$ steps)

Symmetry: $W_N^{k+N/2} = -W_N^k$ (half-period shift negates the factor)

These properties mean that many computations in the DFT are redundant — the FFT eliminates these redundancies.

Decimation-in-Time (DIT) Algorithm

The most common FFT variant (Cooley-Tukey DIT, radix-2) works by splitting the $N$-point DFT into two $N/2$-point DFTs:

Separate $x[n]$ into even-indexed and odd-indexed samples: $$X[k] = \sum_{r=0}^{N/2-1} x[2r]W_{N/2}^{kr} + W_N^k \sum_{r=0}^{N/2-1} x[2r+1]W_{N/2}^{kr}$$

Let $G[k]$ = DFT of even-indexed samples, $H[k]$ = DFT of odd-indexed samples:

$$X[k] = G[k] + W_N^k H[k], \quad k = 0, 1, \ldots, N/2-1$$ $$X[k+N/2] = G[k] - W_N^k H[k], \quad k = 0, 1, \ldots, N/2-1$$

The second equation uses $W_N^{k+N/2} = -W_N^k$.

This process is applied recursively: each $N/2$-point DFT is split into two $N/4$-point DFTs, and so on, until we reach 2-point DFTs (trivial: $X[0] = x[0]+x[1]$, $X[1] = x[0]-x[1]$).

The Butterfly Operation

The core computational unit is the "butterfly":

$$A' = A + W_N^k \cdot B$$ $$B' = A - W_N^k \cdot B$$

This takes two inputs ($A$, $B$), multiplies one by a twiddle factor, and produces two outputs using one addition and one subtraction. The name comes from the shape when drawn as a signal flow graph.

Each stage of the FFT consists of $N/2$ butterfly operations. With $\log_2 N$ stages total:

Total multiplications: $\frac{N}{2}\log_2 N$

Total additions: $N\log_2 N$

Complexity Comparison

Decimation-in-Frequency (DIF)

An alternative approach splits the output (frequency) rather than the input (time):

$$X[2k] = \sum_{n=0}^{N/2-1}(x[n] + x[n+N/2])W_{N/2}^{kn}$$ $$X[2k+1] = \sum_{n=0}^{N/2-1}(x[n] - x[n+N/2])W_N^n W_{N/2}^{kn}$$

DIF applies twiddle factors before combining; DIT applies them between sub-DFTs. Both have the same computational complexity.

Bit-Reversal Permutation

In the DIT FFT, inputs must be in bit-reversed order (or outputs will be). For example, with $N=8$:

In-Place Computation

The butterfly structure allows the FFT to be computed in-place — output values overwrite input values in the same memory locations. This means only $N$ complex storage locations are needed (no extra arrays), which is important for embedded systems with limited memory.

Practical Considerations

Non-power-of-2 lengths: Mixed-radix FFTs handle composite $N$ (e.g., $N = 12 = 4 \times 3$). Zero-padding to the next power of 2 is also common.

Real-valued input: For real $x[n]$, the output satisfies $X[N-k] = X^*[k]$, so only half the output is unique. Specialized real-FFT algorithms exploit this for 2× savings.

Split-radix: Combines radix-2 and radix-4 operations for slightly fewer multiplications ($\sim 4N\log_2 N / 9$).

Applications of the FFT

• Spectral analysis: Real-time frequency display (audio spectrum analyzers, oscilloscopes)
• Fast convolution: $O(N\log N)$ filtering via multiply-in-frequency-domain
• OFDM modulation/demodulation: WiFi, 4G, 5G all use FFT/IFFT
• Image processing: 2D FFT for frequency-domain filtering
• Correlation: Fast cross-correlation for radar, sonar, and pattern matching
• Polynomial multiplication: Multiply degree-$N$ polynomials in $O(N\log N)$

Key Takeaways

• The FFT computes the exact DFT but in $O(N\log_2 N)$ instead of $O(N^2)$ operations
• Cooley-Tukey DIT: recursively splits even/odd samples, combines with butterfly operations
• Each butterfly: 1 complex multiply + 2 complex adds, using the twiddle factor $W_N^k$
• For $N = 1024$: FFT is ~200× faster than direct DFT — enabling real-time processing
• In-place computation requires only $N$ complex memory locations
• The FFT makes spectral analysis, fast convolution, and OFDM communication practical
• One of the most important algorithms in computing history