從抖動曲線到一張食譜
拿一面玻璃稜鏡對著白色陽光，牆上就攤開一道彩虹。那道光從來不是純粹意義上的「白」——它是所有顏色同時相加的總和，稜鏡只是按頻率把它們分了類。一段音訊取樣藏著一模一樣的祕密。當麥克風錄下一個和弦，導線上傳的只是一條歪歪扭扭的電壓、每個瞬間一個數字。埋在這條單一資料流裡的，是各自分開的音——261 Hz 的 C、329 Hz 的 E、392 Hz 的 G——全部疊加在一起。傅立葉轉換要做的就是當那面稜鏡：把歪曲線收進去，把食譜遞出來。
在第三階你認識了 z 轉換，它把一段離散時間訊號映射到整個複數 z 平面，讓你沿著單位圓走一圈就能讀出它的頻率行為。離散傅立葉轉換，也就是 DFT，正是當你不再走完整圈、而是只站在圓上 N 個等距點時得到的結果。這 N 個點就是你的頻率頻格（bin）。DFT 對每個頻格回答一個乾脆的問題：*我的訊號裡有多少這個精確頻率的成分，相位又是多少？*
DFT 到底在算什麼
整個概念其實一步就講完。要量出你的訊號裡含有多少頻格 *k* 的成分，你就拿訊號去和一個「參考波」比對，這個參考波在你那段 N 個取樣裡剛好走完 *k* 個完整週期。「比對」的意思是：把兩者逐點相乘，再把結果全部加起來。如果訊號和參考波同步起伏，乘積就會堆成一個大數字；如果兩者毫不相關，乘積就會散成正正負負、互相抵消到趨近於零。那個單一數字就是頻格 *k*。對 0 到 N−1 的每個 *k* 都做一遍，你就得到整張頻譜。
N-1
X[k] = Σ x[n] · e^(-j·2π·k·n/N) k = 0 … N-1
n=0
x[n] : the n-th input sample (real audio)
X[k] : a COMPLEX number for bin k
e^(-j·2π·k·n/N) : the reference wave —
a cos and a sin spinning at k cycles/block
magnitude |X[k]| = sqrt(Re^2 + Im^2) -> "how much"
phase ∠X[k] = atan2(Im, Re) -> "where in its cycle"輸出 `X[k]` 是複數，這是刻意的。一個實數訊號在每個頻率上帶著兩項事實——有多響（振幅）以及在時間上偏移了多少（相位）——而單一個實數裝不下這兩者。振幅 `|X[k]|` 是你通常會畫出來的；相位則告訴你時序，這對濾波器和訊號重建極為重要，但在單純的振幅頻譜上是看不見的。
讀懂振幅頻譜：哪個頻格對應幾 Hz
頻譜在你能說出每個峰底下對應的頻率之前都是沒用的。規則很短，你應該背起來。如果你以取樣率 Fs（每秒取樣數）取了 N 個樣本，那麼頻格 *k* 落在頻率 k · Fs / N 赫茲。相鄰頻格之間的間距——也就是你的頻率解析度——因此是 Fs / N。想要更細的解析度？就取更多樣本（更大的 N）或等更久；物理不給你免費的午餐。
Fs = 8000 Hz sample rate, N = 1024 samples bin spacing = Fs / N = 8000 / 1024 = 7.8125 Hz per bin bin 0 -> 0 Hz (DC, the average level) bin 1 -> 7.81 Hz bin 32 -> 250.0 Hz bin 64 -> 500.0 Hz bin 512 -> 4000.0 Hz = Fs/2 (Nyquist, the top bin) bin 513..1023 -> mirror image of bins 1..511
有兩個小怪癖總會絆倒初學者。第一，頻格 0 是直流（DC）——就是整塊的平均值——根本不是頻率。第二，對實數值訊號而言，頻譜是對稱的：N/2 以上的頻格是以下頻格的鏡像，不帶任何新資訊。那條位於頻格 N/2 的鏡射線剛好落在 Fs/2，也就是你學取樣時碰過的奈奎斯特頻率。實務上你只畫頻格 0 到 N/2，把鏡像丟掉。
FFT：N² 是怎麼變成 N log N 的
快速傅立葉轉換並不是另一種轉換——它算出來的 `X[k]` 和 DFT 一模一樣，到最後一個位元都相同。它只是抵達同一個答案的更快*路徑*，而那個妙招就是分而治之。把你的 N 個取樣分成偶數索引和奇數索引兩組。結果發現，每一半的 DFT 都能加點變化後重複利用，去組出完整結果。遞迴下去：把每一半再分一次、再一次，直到每塊只剩一個樣本。每一層分割都把全部 N 個樣本碰過一次，而層數只有 log₂N 層。每層 N 的工作量乘上 log₂N 層，就得到那個著名的 N log N。
Operation count: direct DFT vs radix-2 FFT
N N^2 N·log2(N) speed-up
----- ----------- ------------ ---------
64 4,096 384 ~11x
256 65,536 2,048 ~32x
1024 1,048,576 10,240 ~102x
4096 16,777,216 49,152 ~341x
65536 4.29e9 1,048,576 ~4096x
The bigger the block, the more lopsided the win.這可不是甚麼捨入誤差等級的改善——它是*做得到*和*做不到*之間的分界。一張 1024 點頻譜從一百萬次運算掉到一萬次，足足省了一百倍。這正是為什麼一顆 DSP 處理器或手機的音訊晶片能以影片更新率畫出即時頻譜分析儀，為什麼你的 Wi-Fi 無線電能即時解調 OFDM 載波，也是為什麼 MRI 掃描儀能從原始頻率資料重建出影像。當人們把 1965 年 Cooley 與 Tukey 的 FFT 論文視為開啟數位訊號處理時代的起點，他們指的就是這一次演算法上的躍進。
實例演算：兩個音、兩個峰
讓我們把抽象變具體。我們以 Fs = 8000 Hz 取樣，抓 N = 1024 個樣本——也就是 0.128 秒的聲音。訊號是兩個純正弦音的相加：一個響的在 250 Hz、振幅 1.0，一個較輕的在 1000 Hz、振幅 0.5。在示波器上這看起來像一條胖胖的波，上頭騎著較小的漣漪——挺好看，但它不會自報成分。把這塊餵進 FFT，答案就清清楚楚了。
- 找出 250 Hz 的頻格：k = f · N / Fs = 250 × 1024 / 8000 = 頻格 32，剛好落在一個頻格上。
- 找出 1000 Hz 的頻格：k = 1000 × 1024 / 8000 = 頻格 128，同樣剛好落在一個頻格上。
- 計算各頻格的振幅 `|X[k]|`。除了 32 和 128 之外的每個頻格基本上都是零；這兩個則立成尖銳的峰。
- 讀出相對高度：250 Hz 的峰是 1000 Hz 峰的兩倍高，正好對應輸入兩音 1.0 對 0.5 的振幅比。
|X[k]| magnitude spectrum (bins 0..160 shown)
mag
| * (bin 32 = 250 Hz, height ~512)
| |
| |
| | * (bin 128 = 1000 Hz, height ~256)
| | |
|________|______________|________________ bin (Hz)
0 16 32 48 ... 112 128 144 160
(125) (250) (1000)
Two clean tones in -> two clean peaks out.
Peak 1 is twice peak 2: amplitude 1.0 vs 0.5.留意這個例子為何如此乾淨：兩個音都被刻意選在*剛好*落在頻格中心，所以它們的能量全部聚在單一頻格，峰便成了完美的尖刺。現實世界的訊號可沒這麼客氣——一根 247 Hz 的吉他弦會落在頻格 31 和 32 之間、塗抹在兩格上。這個乾淨示範與雜亂現實之間的落差，正是下一階要正面迎戰的洩漏問題。
這在現實世界何處現身
一旦你能看見頻譜，就會開始到處看見它。音樂播放器視覺化裡跳動的長條，就是 FFT 的振幅，每組頻格一條，每秒重畫數十次。吉他調音器跑一次 FFT，回報最高峰的頻率。降噪耳機和語音助理把進來的音訊拆成頻譜，判斷哪些頻格是語音、哪些是嗡嗡聲，壓掉嗡聲，再轉回時間域。
在通訊裡 FFT 更是核心中的核心。每一條 Wi-Fi、4G/5G 和數位電視鏈路都用 OFDM，把資料塞進數百到數千個密集排列的子載波上——而接收端只用每個符元一次 FFT 就把這些子載波分開。一支現代手機光是為了維持連線，每秒就要跑數百萬次 FFT。除了音訊與無線電，FFT 還用來重建 MRI 與 CT 影像、在噴射引擎軸承裡找出振動特徵、以及在 JPEG 的近親轉換裡壓縮影像。依某些統計，它是計算史上被執行最多次的非平凡演算法。