離散與快速傅立葉變換

連續傅立葉變換要求對一個你處處都知道的函數在所有時間上做積分——但計算機只持有一串有限的樣本。離散傅立葉變換（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 完全相同——它不犧牲任何精度，只換取時間。