离散傅里叶变换
概述
离散傅里叶变换（DFT）将有限长度的离散信号从时域变换到频域，公式为 $X[k] = \sum_{n=0}^{N-1} x[n] e^{-i2\pi kn/N}$。DFT 是数字信号处理的核心工具，但直接计算需 $O(N^2)$ 复杂度。1965年库利-图基算法（FFT，快速傅里叶变换）将复杂度降至 $O(N\log N)$，是20世纪最重要的算法发现之一，使 DFT 在实际中广泛可用。
关键内容
- 定义：$N$ 点 DFT 将序列 $x[0], \ldots, x[N-1]$ 映射到复数序列 $X[0], \ldots, X[N-1]$，其中 $X[k]$ 代表频率 $k/N$ 的分量幅度
- 逆变换（IDFT）：$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{i2\pi kn/N}$
- FFT（快速傅里叶变换）：库利-图基分治算法（1965），利用 $N = 2^m$ 时的对称性，$O(N^2) \to O(N\log N)$
- 应用：音频/图像压缩（JPEG、MP3）、频谱分析、卷积（时域卷积=频域乘法）、多项式乘法