幫你的資料換一副眼鏡
假設你在等間隔的時刻量測了某樣東西 N 次——一段聲音、一天的氣溫、一排像素沿線的亮度。你手上有一串數字 x_0、x_1、...、x_{N-1}。這串清單是訊號的一種誠實描述：它在每個瞬間的值。離散傅立葉轉換（DFT）給你的是同一筆資料的第二種、同樣完整的描述，只是換了一種語言來寫：不是「訊號在每個時刻有多大」，而是「每個純粹重複的波各混進了多少」。沒有遺失任何東西，也沒有增加任何東西——這是一次換座標，就像把一個點用（東、北）來描述，而不是用（距離、方位角）。
為什麼要這麼麻煩？因為有些問題在某一種語言裡幾乎看不見，在另一種語言裡卻一目了然。一段錄音裡藏著的 60 赫茲交流哼聲，在時間清單裡只是一個微弱、糾纏的抖動，但在波的清單裡卻是一根又高又孤立的尖峰。同樣的想法讓快速卷積、音訊壓縮，以及本級結尾的譜方法成為可能。DFT 是通往這一切的門；本級其餘篇章，主要就是在講怎麼把這同一個轉換做得更快（FFT），以及怎麼拿它來幹活。
基本構件：單位根
我們用來調配的純波，就是複指數函數，值得花點時間溫和地認識它們。回想歐拉公式 e^(i*t) = cos(t) + i*sin(t)：一個點在複數平面的單位圓上繞行，cos 與 sin 是它投在兩條軸上的影子。一個複指數同時帶著一個餘弦和一個正弦，這正是為什麼「每個頻率只用一個複數」就足以同時記下一個波有多大、以及它在時間上被移動了多少（它的相位）。這是記帳，不是玄學。
現在把一整圈以 N 個等步取樣。那 N 個點 e^(2*pi*i*k/N)，k = 0、1、...、N-1，就是 N 次單位根——單位圓上 N 個等間隔的點，每個都是「自乘 N 次會得到 1」的數。用 w = e^(-2*pi*i/N) 表示最基本的順時針一步（DFT 依慣例取負號）。於是 w^0、w^1、w^2、... 沿著圓繞行，而關鍵在於它們以 N 為週期循環：w^N = 1，所以 w^{n+N} = w^n。這些旋轉的數，就是 DFT 用來拼寫你的訊號的字母表。
轉換本身，就一條公式
DFT 把 N 個時間取樣 x_0、...、x_{N-1} 轉成 N 個頻率係數 X_0、...、X_{N-1}，每個係數就是一個加權總和。係數 X_k 問的是「在這個視窗裡完整循環 k 次的那個波，出現了多少？」它的回答方式，是把你的資料對齊那個波，然後加總起來：
Forward DFT: X_k = sum over n=0..N-1 of x_n * w^(k*n) with w = e^(-2*pi*i/N) Inverse DFT: x_n = (1/N) * sum over k=0..N-1 of X_k * w^(-k*n) Matrix view: X = F x, where F is N x N with entries F[k][n] = w^(k*n)
把它讀成一個矩陣-向量乘法 X = F x。矩陣 F 每個頻率 k 一列、每個取樣 n 一行，它們相交處的元素就是那個旋轉的數 w^(k*n)。把係數 X_k 一個個疊起來，恰恰就是用這個固定的 N×N 矩陣 F 去乘你的資料向量 x。因為 F 的每個元素都由同樣的單位根組成，F 的結構極為規律——遠不是一個隨機矩陣——而這個藏起來的結構，正是下一篇拉開來、讓成本崩塌的那根線頭。逆 DFT 形狀一模一樣，只是把 w 換成它的共軛、前面再乘 1/N，於是你可以走回時間取樣，原封不動地還原 x_n。
一個小小的演算範例：N = 4
用數字會讓這變得具體。取 N = 4，於是 w = e^(-2*pi*i/4) = -i，四個單位根是 1、-i、-1、i。餵進四個取樣 x = (1, 0, 1, 0)——一個開、關、開、關的訊號，是四個取樣能呈現的最快變化。對每個 k 套用公式 X_k = x_0 + x_1*w^k + x_2*w^(2k) + x_3*w^(3k)，一步步走過去。
- X_0 = x_0 + x_1 + x_2 + x_3 = 1 + 0 + 1 + 0 = 2。k = 0 的係數永遠就是所有取樣的總和——它是平均值的 N 倍，也就是訊號的直流（常數）成分。
- X_1 = x_0 + x_2*w^2 = 1 + 1*(-1) = 0，因為 x_1 與 x_3 為零，而 w^2 = (-i)^2 = -1。在「每視窗一個循環」這個頻率上沒有能量。
- X_2 = x_0 + x_2*w^4 = 1 + 1*(1) = 2，因為 w^4 = 1（繞滿一圈）。這是最快的頻率，每視窗兩個循環——正好就是開-關-開-關的圖樣，所以它的係數很大。
- X_3 = x_0 + x_2*w^6 = 1 + 1*(-1) = 0，因為 w^6 = w^2 = -1。結果是 X = (2, 0, 2, 0)：訊號的全部內容都落在常數成分與最快的波上，正如圖樣所暗示的。
注意我們已經用上了 w^4 = w^0 與 w^6 = w^2——次方會繞回來，因為只有 N 個相異的根。我們把同樣的那幾個乘積算了一遍又一遍。看出並重用這份重複，一句話，就是下一篇 FFT 的全部精神。也要注意，這裡答案剛好是純實數，只是因為這個訊號特別對稱；一般情況下 X_k 是複數，同時編碼了一個大小（這個波有多強）和一個相位（它的波峰落在哪）。
為什麼要花 O(N^2)，以及這為什麼很痛
數一數直接公式裡的工作量。每個係數 X_k 是 N 個乘積之和，而總共有 N 個係數，所以帳單大約是 N*N = N^2 次複數乘加。用計算複雜度的語言說，直接照定義算的 DFT 是 O(N^2)。N 很小時這不算什麼，但這條曲線很殘酷：它是一個矩陣-向量乘法，把 N 加倍，工作量就變成四倍。
代進真實數字看看。幾秒鐘的 CD 音質音訊，N 就已經是數百萬。當 N = 1,000,000 時，直接 DFT 需要約 10^12 次運算——一兆次——這對一次轉換來說是好幾分鐘的電腦時間，而你可能得跑上千次。正是這道牆，讓 DFT 在四十年間一直是個漂亮卻太慢、無法大規模使用的想法。下一篇的 FFT 改用 O(N log N) 算出一模一樣的 X_k：對 N = 1,000,000 來說，那大約是兩千萬次運算，而不是一兆次，加速約五萬倍。答案相同，只是在算術裡走了一條不同的路。
DFT 悄悄做了哪些假設
DFT 是精確且無損的，但它只對一個特定的虛構故事誠實：它把你的 N 個取樣當成一個「永遠重複的訊號」的一個週期。它用的那些波，全都剛好在視窗裡塞進整數個循環，所以這個模型悄悄地把你資料的尾端繞回去、接上開頭。如果你真實的訊號頭尾值並不相同，這個繞接就製造出一個跳階，而 DFT 必須用一堆「其實並不存在」的高頻來解釋它——這種抹散到各係數上的現象叫頻譜洩漏。解法（加窗，之後會談）把兩端漸漸收細，讓接縫變得柔和。
還有第二個、更深的假設，就藏在「取樣」這個動作本身：只用 N 個取樣，你能看見的最快的波是有上限的，而任何比它更快的東西，都會被誤讀成某個更慢的東西。這就是 奈奎斯特極限與混疊現象——本級第 3 篇的整個主題，我們會在那裡把取樣定理講精確。現在，記住兩個界線就夠了：DFT 能表示的最高頻率是取樣率的一半，而高過它的頻率不會消失——它們會折回來，假扮成較低的頻率。
再換一個角度看，逆 DFT 其實是一份三角內插的食譜：它建出「這 N 個波的唯一一種組合」，恰好穿過你的 N 個資料點。所以 DFT 不只是「找出頻率」——它是對週期性資料做內插與微分的自然方式，這正是它在本級結尾通往譜方法的那扇門。把這條線記在心裡：今天這個矩陣 F 是個又慢又清楚的起點，而前方幾乎所有內容，講的都是如何利用它的結構，而不是真的去把它建出來。