取樣與離散/快速傅立葉變換

從一條曲線到一串數字

本級到目前為止都活在連續函數的世界裡。你把[[fourier-transform-pair|傅立葉變換]]當作傅立葉級數在週期延伸到無窮時的極限來認識：一個對整個 x 的積分把信號 f(t) 變成它的頻譜 F(omega)，再一個積分又把它變回去。很美——但電腦算不了一個對全部時間的積分，因為它從未見過每一瞬間的 f(t)。它見到的是一段麥克風電壓、或一個感測器讀數，在時鐘的某一下被測量：t = 0，然後 t = T，再 t = 2T，依此類推。在任何數學開始之前，那條連續曲線就已經被替換成了一串有限的數字。

把每一下時鐘之間的間隔叫做取樣間隔 T_s，它的倒數 f_s = 1/T_s 叫做取樣率——每秒取樣多少個點。比如一張光碟以 f_s = 44100 赫茲取樣：每個聲道每秒四萬四千個數字。整篇導覽的核心問題問起來樸素得令人放鬆：當你只留下這些取樣點、把連續曲線扔掉時，你丟失了什麼嗎？兩個不同的信號會不會產出完全相同的一串數字？誠實、且起初令人吃驚的答案是：在一個乾淨的條件下你什麼也沒丟失——而當那個條件不成立時，你丟失的是某種具體而不可逆的東西。

取樣就是乘以一把梳子

要看清取樣對頻譜做了什麼，就得誠實地把它建模。只在時鐘刻度處測量 f(t)，等同於把 f(t) 乘以一排無限細的尖峰，每個 T_s 的整數倍處一根——這就是狄拉克梳，對所有整數 n 求和的 delta(t - n T_s)。回想本級前面：單個 delta 的傅立葉變換是一個平直的常數，而一列週期性 delta 串的變換本身又是一列週期性 delta 串——時間中的一把梳子變換成頻率中的一把梳子，齒距為 f_s。這一個事實就是取樣定理的全部引擎。

現在搬出兩篇前的卷積定理：在時間裡把兩個信號相乘，就在頻率裡把它們的變換*卷積*起來。我們在時間裡把 f 乘了一把梳子，於是在頻率裡，頻譜 F(omega) 就跟一把頻率梳子卷積——而任何東西跟一把梳子卷積，無非是在每一根齒上蓋下它的一份拷貝。這個畫面具體得讓人無法抗拒：原本的頻譜 F 沿頻率軸被一遍又一遍地蓋章，一份拷貝以 0 為中心、下一份在 f_s、再下一份在 2 f_s，兩個方向都如此。時間上的取樣使頻譜*週期化*。這一幅圖就把「取樣何時安全」的一切都告訴了你。

奈奎斯特率，與混疊之罪

假設原信號是帶限的：它的頻譜 F(omega) 在某個最高頻率 B 以上恰好為零——那之外沒有能量。那麼每一份被蓋下的 F 拷貝都是一座寬為 2B 的小島（從 -B 到 +B），而這些拷貝彼此相距 f_s。若 f_s 足夠大，這些島嶼之間留有空隙、清清爽爽地各自分開，原本的 F 仍原封不動地坐在正中央，可被完美還原：乘以一個只留下中央那座島的方窗、變換回去，你就精確地重建了 f(t)。沒有任何信息丟失。這就是奈奎斯特與香農的[[sampling-and-nyquist-criterion|取樣定理]]的核心。

多大才算足夠大？當間距 f_s 至少是最高頻率的兩倍時，島嶼恰好不再重疊：f_s >= 2B。這個門檻 2B 就是奈奎斯特率——能保住一個最高頻率為 B 的信號所需的最低取樣率。等價地說，給定取樣率 f_s，你能忠實捕捉的最高頻率是奈奎斯特頻率 f_s/2。光碟的 44100 赫茲正是這樣選的，好讓它的奈奎斯特頻率 22050 赫茲剛好高過人耳約 20000 赫茲的上限。那個因子 2 不是什麼安全餘量、也不是工程上的湊數；它直接從那兩份蓋下的拷貝恰好相觸的幾何關係裡掉出來。

門檻之下出錯的方式叫混疊，而它是真正不可逆的。若 f_s < 2B，島嶼挨得太近、它們的裙邊互相交疊；一份蓋下拷貝的高頻尾巴溢進了下一份的頻帶，而在交疊處的任一頻率上，頻譜如今是兩份貢獻之和，你再也分不開了。一個繞回來的高頻正戴著偽裝——它變成了某個低頻的*別名*。教科書裡的畫面就是老電影裡看似倒轉的車輪，或者一個 7000 赫茲的音以 8000 赫茲取樣後、不可分辨地變成了一個 1000 赫茲的音。一旦兩個頻率落到了同一批取樣點上，事後任何處理都無法把它們區分開，因為取樣點本身就是一模一樣的。

離散傅立葉變換：一個真能算出來的傅立葉變換

假設我們做對了，如今手裡有 N 個取樣點 x[0], x[1], ..., x[N-1]，取自一個時間窗口。連續變換對所有 t 積分；我們只能對手裡有的取樣點求和。於是把積分換成有限和、把連續頻率 omega 換成 N 個頻率的離散網格，你就得到了[[discrete-and-fast-fourier-transform|離散傅立葉變換]]，即 DFT：X[k] = 對 n 從 0 到 N-1 求和的 x[n] 乘以 e^{-i 2 pi k n / N}。這是那個分析積分的、字面上可計算的表親，指數裡帶著同一個負號——它憑正交性一次篩出一個頻率分量，正是你在複指數傅立葉級數裡見過的把戲，只不過現在是在一個有限網格上、而非一個週期上。

DFT 悄悄假定你的 N 個取樣點是某個週期信號的一個週期——它把你的窗口首尾相接地鋪滿整段時間。這個假定是有牙齒的。若真實信號沒有在窗口內走完整數個週期，這種鋪排就會在窗口末端與它重複的開頭相接處造出一個跳躍，而那個人為的不連續把每一條尖銳的譜線抹成附近若干頻點上的一片散布——頻譜洩漏，正是當年在傅立葉級數篇裡引發吉布斯現象的那些跳躍的離散回聲。標準的補救是在變換之前，用一個窗函數（漢寧、漢明及其同類）把取樣點在兩端平滑地收攏到零，以一點點模糊換取那道假邊緣的壓制。

快速傅立葉變換：它為何改變了一切

盯緊 DFT 這個和、數一數工作量。N 個輸出值 X[k] 中的每一個都是 N 個乘積之和，所以直接計算大約要花 N 乘 N 次乘加。對於一段 N 在 44000 上下的一秒音訊，單求一個頻譜就約二十億次運算——而 N^2 增長得如此殘暴，以至一小時的音訊會變得毫無希望。幾十年來，這份代價使 DFT 成了一個美麗卻大多貴到無法大規模使用的想法。拯救它的不是另一種變換，而是*算出同一批數字*的一種更快辦法：[[discrete-and-fast-fourier-transform|快速傅立葉變換]]，即 FFT。

FFT 的想法——由 Cooley 與 Tukey 在 1965 年發揚光大（後來發現高斯約在 1805 年就瞥見過）——是分而治之。把 N 個取樣點拆成偶數下標的一組與奇數下標的一組。一段簡短的推算表明，長度為 N 的完整 DFT 可以由 N/2 個偶點的 DFT 加上 N/2 個奇點的 DFT 拼裝而成，每一對用一個旋轉因子 e^{-i 2 pi k / N} 黏合——這一步叫蝶形運算。每一半再各自被拆成兩半，如此一路拆到底。因為你在大約以 2 為底的 log N 個層級上，每一層都把問題對半切，總工作量就從 N^2 坍縮成一個正比於 N log N 的數。

Cost of transforming N samples:

   direct DFT   ~  N * N         operations
   FFT          ~  N * log2(N)   operations

   N = 1,024          DFT ~ 1,000,000     FFT ~ 10,000     ( ~100x )
   N = 1,048,576      DFT ~ 1.1e12        FFT ~ 21,000,000 ( ~50,000x )

Idea (radix-2, Cooley-Tukey):
   X[k]   =  E[k]  +  w^k * O[k]
   X[k+N/2] = E[k] - w^k * O[k]        with  w = e^{-i 2 pi / N}
   where E = DFT of even-indexed samples,
         O = DFT of odd-indexed samples   (each of length N/2)
   recurse until length 1.

同樣的 X[k] 值，兩種代價。把偶點與奇點拆開並遞迴，使 N^2 變成 N log N——一種隨 N 增大而無止境增長的加速，這正是為什麼跑在現代信號處理底下的是 FFT，而非赤裸的 DFT。

別讓*快速*這個詞把你帶偏：FFT 算出的 X[k] 與 DFT 分毫不差、精度相同——它是一種演算法，不是一種近似。但代價的這一改變，才是讓整套理論得以過日子的關鍵。正是這個 N log N 的 FFT，讓你的手機能解碼音樂、畫出即時頻譜、運行降噪、壓縮照片、解調無線信號，而且全程只啜飲一點點電量。它還加速一些看似無關的事：因為一個域裡的相乘就是另一個域裡的卷積，一次 FFT、一次廉價的逐點相乘、再一次逆 FFT，就能把兩個長信號卷積起來——甚至把兩個巨大的整數相乘——遠快於課本上的笨辦法。當人們稱 FFT 是有史以來最重要的演算法之一時，他們指的就是這個。

把它串起來：從麥克風到頻譜

退後一步，整條流水線讀起來就是一個乾淨的故事，每一環都是你如今已經認識的工具。一個連續信號被一個類比濾波器帶限、以高於其奈奎斯特率的速率取樣使得各份頻譜拷貝不致重疊、被切成一個窗口並加錐以馴服洩漏、然後送進一個 FFT——它廉價而精確地交出連續傅立葉變換一直指向的那個離散頻譜。用逆 FFT 與一個重建濾波器把每一支箭頭反轉過來，你就一路走回聲音。前幾篇的連續理論是那個夢；這條鏈子，是一台真實機器如何在那個夢裡活著。

抗混疊。讓連續信號通過一個低通濾波器，去掉預定奈奎斯特頻率以上的一切，使取樣定理的帶限前提真正成立。
取樣。以速率 f_s >= 2B（高於奈奎斯特率）測量，把曲線變成一串 x[0..N-1]，且不丟失信息。
加窗。把這 N 個取樣點乘以一個平滑錐（漢寧、漢明），壓制窗口接縫處的假跳躍，從而減少頻譜洩漏。
變換。運行 FFT 以 N log N 的時間得到 X[0..N-1]；第 k 個頻點對應頻率 k 乘以 f_s / N，而對實信號而言只有到 N/2 為止的頻點攜帶新信息。
解讀（或反變換）。把幅度與相位讀作頻譜——或者對它們做處理後運行逆 FFT，再經一個重建濾波器，回到一個連續信號。

這就是整級一直在搭建、要通向的那座橋。連續的傅立葉變換告訴你頻率內容*意味著什麼*；取樣定理告訴你*何時*一串有限的數字能把它保住；DFT 使這個想法可計算；而 FFT 使它便宜到一天可以跑十億次。同一個家族——卷積定理、那把梳子、作為尖峰極限的狄拉克 delta——在每一步都反覆現身，這正是為什麼一門分析課能撐起一整門工程學科。手握這些，下一篇就推開通向這個變換更廣闊親屬的門，它們各自為某種幾何或某種對稱而調音——那是樸素傅立葉變換沒有為之而生的。