V. Fast Fourier Transform (FFT)
Motivation and Computational Complexity
-
Direct DFT Computation: Requires $$\displaystyle N^2 $$ complex multiplications and $N(N-1)$ additions for an $N$-point DFT.
-
FFT Objective: Exploit symmetry and periodicity of twiddle factors $$\displaystyle W_N^k = e^{-j\frac{2\pi}{N}k} $$ to reduce complexity.
-
Computational Complexity:
-
Direct DFT: $$\displaystyle \mathcal{O}(N^2) $$
-
Radix-2 FFT: $$\displaystyle \mathcal{O}(N \log_2 N) $$
-
-
Efficiency Gain: For $$\displaystyle N=1024 $$, direct DFT ~1M operations vs. FFT ~10k operations.
[!TIP] Exam Focus: Always state the complexity reduction and reason (symmetry/periodicity of $$\displaystyle W_N $$).
Decimation in Time (DIT) FFT
Core Idea: Decompose input sequence into even and odd indexed samples recursively.
Radix-2 DIT Algorithm Steps:
-
Bit-Reversal Permutation: Reorder input samples $x[n]$ to $x[\text{bit-reversed}(n)]$.
-
Log₂N Stages: Each stage has $N/2$ butterfly computations.
-
Butterfly Computation (for $M$-point DFT):
$$ \begin{aligned} A &= x_{\text{even}} + W_N^k x_{\text{odd}} \\ B &= x_{\text{even}} - W_N^k x_{\text{odd}} \end{aligned} $$
where $k$ depends on stage and butterfly index.
Signal Flow Graph (N=8):
Example: N=8, $$\displaystyle x[n] = \{1,1,1,0,0,0,0,0\} $$
Step 1: Bit-reversal permutation
-
Original indices: 0,1,2,3,4,5,6,7
-
Binary: 000,001,010,011,100,101,110,111
-
Bit-reversed: 000,100,010,110,001,101,011,111 → indices: 0,4,2,6,1,5,3,7
-
Reordered sequence: $\{1,0,1,0,1,0,1,0\}$
Step 2: Stage-wise butterfly computation
-
Stage 1 (N=8, spacing=4): $$\displaystyle W_8^0 = 1 $$
-
Stage 2 (N=4, spacing=2): $$\displaystyle W_4^0=1, W_4^1=-j $$
-
Stage 3 (N=2, spacing=1): $$\displaystyle W_2^0=1 $$
Final DFT: $$\displaystyle X[k] = \{4, 1-j1, 0, 1+j1, 0, 1+j1, 0, 1-j1\} $$
[!TIP] Common Pitfall: Forgetting bit-reversal in DIT. Input must be reordered before first butterfly stage.
Decimation in Frequency (DIF) FFT
Core Idea: Decompose output DFT into even and odd frequency bins. Input remains in natural order.
Radix-2 DIF Algorithm Steps:
-
Natural Order Input: No initial reordering.
-
Log₂N Stages: Each stage computes:
$$ \begin{aligned} A &= x[n] + x[n+N/2] \\ B &= \left(x[n] - x[n+N/2]\right) W_N^k \end{aligned} $$
where $$\displaystyle k = n \cdot (N/\text{stage size}) $$.
- Bit-Reversal at Output: Final output is in bit-reversed order.
Signal Flow Graph (N=8):
Example: N=8, $$\displaystyle x[n] = \{1,-1,1,-1,0,0,0,0\} $$
Stage 1 (N=8):
-
Pair (0,4): $$\displaystyle A=1+0=1 $$, $$\displaystyle B=(1-0)W_8^0=1 $$
-
Pair (1,5): $$\displaystyle A=-1+0=-1 $$, $$\displaystyle B=(-1-0)W_8^0=-1 $$
-
... continue for all 4 pairs.
Stage 2 (N=4) and Stage 3 (N=2) follow similarly.
Final Output (before bit-reversal): $$\displaystyle X_{\text{br}}[k] $$. Apply bit-reversal to get $X[k]$.
[!TIP] Key Difference from DIT: DIF applies twiddle factors after subtraction, DIT applies before subtraction.
FFT for Composite N (Mixed-Radix Cooley-Tukey)
General Form: $$\displaystyle N = N_1 \times N_2 $$. Decompose into $$\displaystyle N_1 $$ subsequences of length $$\displaystyle N_2 $$ (or vice versa).
Steps for $$\displaystyle N = N_1 \times N_2 $$ (e.g., $$\displaystyle N=6=2\times3 $$):
-
Reshape input $x[n]$ into $$\displaystyle N_1 \times N_2 $$ matrix (row-major).
-
Compute $$\displaystyle N_2 $$-point DFT on each row (small FFTs).
-
Multiply by twiddle factors $$\displaystyle W_N^{n_1 k_2} $$.
-
Compute $$\displaystyle N_1 $$-point DFT on each column.
-
Transpose to get final result.
Example: $$\displaystyle N=6 $$, $$\displaystyle x[n]=\{1,2,3,4,5,6\} $$
- $$\displaystyle N_1=2 $$, $$\displaystyle N_2=3 $$. Reshape:
$$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} $$
-
Step 1: 3-point DFT on each row.
Row1 DFT: $\{6, -1.5-j0.866, -1.5+j0.866\}$
Row2 DFT: $\{15, -1.5-j0.866, -1.5+j0.866\}$
-
Step 2: Multiply by $$\displaystyle W_6^{n_1 k_2} $$ (twiddle matrix).
-
Step 3: 2-point DFT on each column.
-
Final: $X[k]$ computed after transposition.
[!TIP] Mixed-radix allows non-power-of-2 FFTs. Choose factors to minimize operations.
Inverse FFT
Method 1: Use forward FFT algorithm with conjugated twiddles and scaling:
$$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X^*[k] W_N^{-k} \quad \Rightarrow \quad \text{IFFT}(X) = \frac{1}{N} \left[\text{FFT}(X^*)\right]^* $$
Method 2: Directly modify butterfly: use $$\displaystyle W_N^{-k} $$ instead of $$\displaystyle W_N^k $$, then divide by $N$.
Complexity: Same as forward FFT, $\mathcal{O}(N \log N)$.
Comparison: DIT vs DIF FFT
| Feature | DIT | DIF |
|---|---|---|
| Input Order | Bit-reversed | Natural |
| Output Order | Natural | Bit-reversed |
| Twiddle Application | After butterfly combine | Before butterfly combine |
| Butterfly Structure | $$\displaystyle A = a + W b $$, $$\displaystyle B = a - W b $$ | $$\displaystyle A = a + b $$, $$\displaystyle B = (a - b) W $$ |
| Common Use | More common in literature | Often used in hardware |
Key Formulas & Definitions
-
DFT: $$\displaystyle X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn} $$, $$\displaystyle W_N = e^{-j\frac{2\pi}{N}} $$
-
Butterfly (DIT):
$$ \begin{bmatrix} A \\ B \end{bmatrix} = \begin{bmatrix} 1 & W_N^k \\ 1 & -W_N^k \end{bmatrix} \begin{bmatrix} x_{\text{even}} \\ x_{\text{odd}} \end{bmatrix} $$
- Butterfly (DIF):
$$ \begin{bmatrix} A \\ B \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ W_N^k & -W_N^k \end{bmatrix} \begin{bmatrix} x[n] \\ x[n+N/2] \end{bmatrix} $$
[!TIP] Always verify with small N (e.g., N=4) to understand butterfly operation and ordering.