Discrete Fourier Transform & FFT
Discrete Fourier Transform & FFT
The Discrete Fourier Transform (DFT) $X[k]=\sum_{n=0}^{N-1}x[n]e^{-2\pi ikn/N}$ transforms a finite sequence of $N$ samples to $N$ complex frequency coefficients. Naively computed in $O(N^2)$ operations, the Fast Fourier Transform (FFT) computes the DFT in $O(N\log N)$ using the divide-and-conquer Cooley-Tukey algorithm. The FFT is one of the most important algorithms in computing, enabling real-time signal processing, image analysis, and large polynomial multiplication.
DFT & IDFT
For $x[0],\ldots,x[N-1]\in\mathbb{C}$, the DFT is $X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn}$ where $W_N=e^{-2\pi i/N}$ (primitive $N$-th root of unity). The Inverse DFT: $x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-kn}$. Properties: linearity; shift $x[n-m]\leftrightarrow W_N^{-km}X[k]$; circular convolution $x\circledast y\leftrightarrow X[k]Y[k]$; Parseval $\sum|x[n]|^2=\frac{1}{N}\sum|X[k]|^2$. The DFT matrix $F$ has $F_{kn}=W_N^{kn}/\sqrt{N}$ and is unitary: $F^*F=I$.
Cooley-Tukey FFT Algorithm
For $N=2^m$, split DFT into even/odd samples: $X[k]=\sum_{n\text{ even}}x[n]W_N^{kn}+\sum_{n\text{ odd}}x[n]W_N^{kn}=\text{DFT}_{N/2}(x_{\text{even}})[k]+W_N^k\text{DFT}_{N/2}(x_{\text{odd}})[k]$. Recursion depth $\log_2 N$; each level $O(N)$: total $O(N\log N)$. The 'butterfly' operation at each level: $(a,b)\to(a+W_N^k b,a-W_N^k b)$. For $N=2^{10}=1024$: FFT uses $\approx 5000$ multiplications vs $10^6$ for DFT.
Example 1
Compute the DFT of $x=[1,1,1,1]$ ($N=4$).
Solution: $W_4=e^{-i\pi/2}=-i$. $X[k]=\sum_{n=0}^3 x[n]W_4^{kn}=\sum_{n=0}^3(-i)^{kn}$. $X[0]=1+1+1+1=4$; $X[1]=1+(-i)+(-1)+(i)=0$; $X[2]=1+(-1)+1+(-1)=0$; $X[3]=1+(i)+(-1)+(-i)=0$. So $X=[4,0,0,0]$ — a constant sequence has a DC component only.
Example 2
Apply FFT to multiply polynomials $p(x)=1+2x+x^2$ and $q(x)=1+x$ efficiently.
Solution: Coefficients: $p=[1,2,1,0]$, $q=[1,1,0,0]$ (zero-padded to length $N=4\geq 3+2-1$). Compute DFTs: $P=\text{DFT}(p)$, $Q=\text{DFT}(q)$. Pointwise multiply: $R[k]=P[k]Q[k]$. Inverse DFT gives coefficients of $r=pq$. Direct: $(1+2x+x^2)(1+x)=1+3x+3x^2+x^3$. This approach scales to $O(N\log N)$ for large polynomials, crucial in cryptography (NTT) and big integer multiplication.
Practice
- Prove the DFT matrix is unitary (i.e., $F^*F=I$) using the orthogonality of roots of unity.
- Show that circular convolution in time $\leftrightarrow$ pointwise multiplication in DFT domain.
- Explain spectral leakage and windowing: what happens to the DFT of $\cos(2\pi f_0 n/N)$ when $f_0$ is not an integer?
- Describe how the 2D DFT is used in image compression (JPEG) and compare to the DCT.
Show Answer Key
1. $F^*F$: $(F^*F)_{jk}=\frac{1}{N}\sum_{m=0}^{N-1}e^{-2\pi imj/N}e^{2\pi imk/N}=\frac{1}{N}\sum_m e^{2\pi im(k-j)/N}$. When $j=k$: sum $=N$, entry $=1$. When $j\neq k$: geometric series $=0$. So $F^*F=I$.
2. Circular convolution $(x\circledast y)_n=\sum_k x_k y_{n-k\bmod N}$. DFT: $\widehat{x\circledast y}_m=\sum_n(\sum_k x_k y_{n-k})\omega^{-mn}=\hat{x}_m\hat{y}_m$ by substitution $l=n-k$.
3. When $f_0$ is not integer, the signal's frequency falls between DFT bins. Energy leaks into all bins (spectral leakage). Windowing (Hann, Hamming, etc.) tapers the signal at endpoints, reducing side-lobe leakage at the cost of wider main-lobe width.
4. JPEG divides the image into $8\times8$ blocks, applies the 2D DCT (real-valued, no phase), quantizes coefficients, and entropy-codes. DCT concentrates energy in low-frequency coefficients, enabling high compression. It is closely related to the DFT of a symmetrically extended signal.