The Discrete Fourier Transform and the FFT

The DTFT is a function of a continuous frequency variable — not directly computable. The DFT samples it at finitely many frequencies, turning spectral analysis into a finite linear-algebra problem, at the cost of needing to understand what that sampling does to the underlying signal (implicit periodic extension, spectral leakage, resolution). The FFT is what makes the DFT computationally practical (an $O(N\log N)$ divide-and-conquer algorithm instead of $O(N^2)$), which in turn makes DFT-based (“fast”) convolution — via zero-padding to avoid circular wraparound — the standard way to implement convolution in practice.

Outline (TODO — flesh out each)

• The discrete Fourier transform (DFT) — definition, relation to the DTFT and z-transform
• DFT spectral analysis — leakage, windowing, resolution
• DFT applications
• The fast Fourier transform (FFT)
• Convolution using the DFT — circular vs. linear convolution, zero-padding