离散与快速傅里叶变换

连续傅里叶变换要求对一个你处处都知道的函数在所有时间上做积分——但计算机只持有一串有限的样本。离散傅里叶变换（DFT）就是为那串有限列表打造的变换版本：它接收 N 个采样值，返回 N 个数，即 N 个离散频率的振幅。快速傅里叶变换（FFT）不是另一种变换，而是一个把 DFT 算得极快的巧妙算法——正是它把傅里叶分析装进了每一部手机、示波器和 MP3 编码器里。

DFT 把积分换成有限求和：X[m] = 从 n = 0 到 N minus 1 的 x[n] e^{-2 pi i m n / N} 之和。直接计算时，每个输出要 N 次乘法、共 N 个输出，所以代价像 N^2 那样增长——对一百万个样本就是一万亿次运算，不切实际。FFT（经典者是 Cooley-Tukey 算法）利用了那些指数因子之间深刻的对称与重复：它把求和拆成偶数下标和奇数下标两部分，各自变换一半，再合并，并递归地这样做。这种分治把代价降到大约 N log N。对一百万个样本，那大约是两千万次运算而非一万亿——是即时与无望之间的区别。

这一个加速是有史以来最有影响力的算法之一。它让实时频谱分析、数字滤波（通过卷积定理，FFT 把昂贵的卷积变成廉价的逐点乘法再变回去）、音频与图像压缩、医学成像和大数快速相乘统统成了家常便饭。要厘清两个诚实的注意点：DFT 隐含地假定采样信号是周期的，所以一个在窗口里没有走完整数个周期的信号会受到频谱泄漏（能量抹到相邻频点）的困扰，加窗函数可以缓解它；而 FFT 算出的数与 DFT 完全相同——它不牺牲任何精度，只换取时间。