Fast Fourier Transform: FFT Algorithms, Properties & Applications

Key Concepts and Definitions

Discrete Fourier Transform (DFT) Recap

The Discrete Fourier Transform (DFT) converts a finite-length discrete-time signal $x[n]$ of length $N$ into its frequency-domain representation $X[k]$: $$X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{-j\frac{2\pi }{N}kn},k=0,1,\dots ,N-1$$

• Computational Complexity: Direct computation requires $N^2$ complex multiplications and additions, which is inefficient for large $N$.

Fast Fourier Transform (FFT)

The FFT is an algorithm to compute the DFT efficiently by exploiting symmetry and periodicity of the complex exponential (twiddle factors). It reduces the complexity to $O(N\log N)$.

FFT Algorithms

1. Decimation-in-Time (DIT) Radix-2 FFT

The Radix-2 FFT splits the input sequence into even-indexed and odd-indexed subsequences, recursively computes their DFTs, and combines them using twiddle factors.

How it Works

1. Divide: Split $x[n]$ into $x_{\text{even}}[n]$ and $x_{\text{odd}}[n]$.
2. Conquer: Recursively compute $X_{\text{even}}[k]$ and $X_{\text{odd}}[k]$.
3. Combine: Use the butterfly operation to merge results: $$X[k]=X_{\text{even}}[k]+W_N^k{X}_{\text{odd}}[k]$$ $$X[k+N/2]=X_{\text{even}}[k]-W_N^k{X}_{\text{odd}}[k]$$ where $W_N^k=e^{-j\frac{2\pi }{N}k}$ is the twiddle factor.

Visual: Radix-2 FFT Butterfly Diagram

flowchart LR
    A["x[0]"] -->|"+"| B["X_even[0]"]
    A -->|"-"| C["X_odd[0]"]
    D["x[1]"] -->|"+"| E["X_even[0]"]
    D -->|"-"| F["X_odd[0]"]
    B -->|"W_N^0"| G["X[0]"]
    C -->|"W_N^0"| H["X[N/2]"]
    E -->|"W_N^0"| G
    F -->|"W_N^0"| H

Worked Example: 8-Point Radix-2 FFT

Compute the FFT of $x[n]=[1,2,3,4,5,6,7,8]$.

1. First Stage (Split into even/odd):
   • $x_{\text{even}}=[1,3,5,7]$
   • $x_{\text{odd}}=[2,4,6,8]$
2. Recursive Computation: Repeat until base case (2-point DFT).
3. Combine with Twiddle Factors:
   • Use $W_8^k=e^{-j\frac{\pi }{4}k}$ for $k=0,1,2,3$.

Final Output: $$X[k]=[28,-4+j4\sqrt{2},-4,-4-j4\sqrt{2},0,4+j4\sqrt{2},4,4-j4\sqrt{2}]$$

2. Decimation-in-Frequency (DIF) Radix-2 FFT

The DIF FFT splits the output sequence into even and odd frequencies, then combines results.

Key Difference from DIT

• DIF computes the DFT of the output first, while DIT computes the DFT of the input.
• The butterfly structure is inverted compared to DIT.

Visual: DIF Butterfly Structure

flowchart LR
    A["X[0]"] -->|"+"| B["X_even[0]"]
    A -->|"-"| C["X_odd[0]"]
    D["X[1]"] -->|"+"| E["X_even[0]"]
    D -->|"-"| F["X_odd[0]"]
    B -->|"W_N^0"| G["x[0]"]
    C -->|"W_N^0"| H["x[N/2]"]
    E -->|"W_N^0"| G
    F -->|"W_N^0"| H

3. Radix-4 and Split-Radix FFT

• Radix-4 FFT: Further reduces computation by splitting into 4 subsequences (requires $N$ divisible by 4).
• Split-Radix FFT: Combines Radix-2 and Radix-4 for better efficiency (used in MATLAB’s fft function).

Advantages of Radix-4/Split-Radix

Properties of FFT

1. Symmetry: $X[N-k]=X^{\ast }[k]$ (for real inputs).
2. Linearity: FFT of $ax[n]+by[n]=aX[k]+bY[k]$.
3. Circular Convolution: FFT converts linear convolution into pointwise multiplication in frequency domain.
4. Overlap-Add/Overlap-Save: Techniques for efficient convolution using FFT.

Visual: Circular vs. Linear Convolution

flowchart LR
    A["Linear Convolution"] -->|"x[n] * h[n]"| B["y[n] = sum(x[m]h[n-m])"]
    C["Circular Convolution"] -->|"FFT(x) * FFT(h)"| D["IFFT(X[k]H[k])"]

Applications of FFT

In the Real World

1. eSewa (Nepal):

   • Uses FFT for spectral analysis in fraud detection (e.g., identifying unusual transaction patterns in frequency domain).
   • Example: Detecting periodic anomalies in payment timestamps via FFT.

2. Ncell (Nepal):

   • Employs FFT in OFDM (Orthogonal Frequency-Division Multiplexing) for 4G/5G signal modulation.
   • Worked Example: A 1024-point FFT processes a 10 MHz bandwidth signal into 1024 subcarriers for efficient data transmission.

3. YouTube (Global):

   • Uses FFT for audio compression (e.g., MP3 encoding via perceptual noise shaping).
   • Example: FFT identifies frequencies below human hearing threshold (20 Hz–20 kHz) for removal.

Exam Tip

1. Derive the FFT Recurrence: Know how to split $N$-point DFT into smaller DFTs (e.g., Radix-2).
2. Twiddle Factors: Memorize $W_N^k=e^{-j\frac{2\pi }{N}k}$ and its properties (e.g., $W_N^{k+N/2}=-W_N^k$).
3. Efficiency Comparison: Compare Radix-2, Radix-4, and Split-Radix in terms of multiplications.
4. Applications: Link FFT to filter design, spectral analysis, and compression (e.g., MP3, JPEG).
5. Common Pitfalls:
   • Forgetting zero-padding affects frequency resolution but not spectral content.
   • Misapplying circular convolution (use overlap-add/save for linear convolution).

Summary Table: FFT Algorithms

Real Picture: FFT Hardware Acceleration

Real Picture: FFT in MATLAB

Real Picture: FFT Chip (Texas Instruments TMS320C6748)

Worked Example: Traffic Noise Analysis (Nepal)

Scenario: Analyze traffic noise in Kathmandu using FFT to identify dominant frequencies.

1. Signal Acquisition: Record noise levels at 44.1 kHz for 1 second ($N=44100$ samples).
2. FFT Computation: Use 8192-point FFT (zero-padded) for frequency resolution of $\Delta f=44100/8192\approx 5.37$ Hz.
3. Result Interpretation:
   • Peaks at 50 Hz (engine hum), 100 Hz (tires), and 500 Hz (horns).
   • Action: Propose noise barriers tuned to these frequencies.

Key Formulas to Remember

1. DFT Definition: $$X[k]=\sum _{n=0}^{N-1}x[n]W_N^{kn},W_N=e^{-j\frac{2\pi }{N}}$$
2. FFT Recurrence (Radix-2 DIT): $$X[k]=X_{\text{even}}[k]+W_N^k{X}_{\text{odd}}[k]$$ $$X[k+N/2]=X_{\text{even}}[k]-W_N^k{X}_{\text{odd}}[k]$$
3. Circular Convolution Theorem: $$\text{FFT}(x[n]\ast h[n])=X[k]\cdot H[k]$$
4. Parseval’s Theorem (Energy Conservation): $$\sum _{n=0}^{N-1}|x[n]{|}^2=\frac{1}{N}\sum _{k=0}^{N-1}|X[k]{|}^2$$