電腦接收有限個數,而週期函數有無窮多個傅立葉(Fourier)係數。離散傅立葉變換(DFT)是有限列表的精確座標變換,卻不會自動恢復產生該列表的函數的全部係數:相差採樣點數整數倍的頻率,在網格上無法區分。
我們先固定歸一化並證明有限代數,再推導快速分解,並在允許交換採樣與無窮級數的假設下證明混疊公式。實線上的帶限採樣定理屬於另一種情形;這裏每個頻率都是整數,指標按有限採樣點數取模。
有限傅立葉座標
定義 1.11.1
(離散傅立葉變換)
對 ,令 。向量 的離散傅立葉變換是向量 ,其中
超出該範圍的指標按模 理解。
關鍵的有限正交性恆等式是
餘數不同時,公比 ,和為 ;餘數相同時,每項都為一。求和指標改名為 而非 時,同一恆等式仍成立。
定理 1.11.2
(DFT 反演、帕塞瓦爾(Parseval)公式與循環卷積)
採用上述歸一化,
定義循環卷積
它的 DFT 是逐點乘積 。
證明
(正交性與指數的週期性)
代入並重排有限和得 。同理 。因此 DFT 矩陣除以 後為酉矩陣。
對於卷積,令 (模 )並重新排列有限求和:
證明透視
每個恆等式從哪裏來
反演與帕塞瓦爾公式各使用一次正交關係 (1),都是對頻率指標 求和:反演時指數之差為 ,帕塞瓦爾公式中為 。兩種情形都只有對角項留下,每項貢獻 ,再由因子 抵消。
卷積恆等式完全不用正交性。它的關鍵一步是按模 重新編號 ;這之所以合法,只因 只依賴於 模 的值:由 ,即使 ,也有 。卷積必須是循環卷積,正是出於這一點;若用普通卷積,繞回的項會落在錯誤的指標上。所有求和都是有限的,每次重排都無需理由。下面的混疊證明恰恰在這裏不同:把無窮級數代入 DFT 求和需要絕對收斂。
出現在反演和帕塞瓦爾公式中,而不在這裏的卷積定義中。若採用酉歸一化,即把變換除以 ,這些因子的分配就會不同,卷積恆等式中也會出現 。
概念視角代數
DFT 把循環矩陣對角化
與固定的 作卷積,就是由循環矩陣 給出的線性映射 。對每個 ,令 。按模 代入 ,
因此由 (1) 兩兩正交的 個向量 是每個循環矩陣的公共特徵向量,特徵值為 。卷積定理正是說:DFT 是換到這組特徵向量的基變換;在新座標下,卷積變成乘以一個對角矩陣。
二進制分解
令 。把數據分成偶數與奇數指標,計算長度為 的變換
對 ,
事實上,,而 。又 、,但把 換成 會使奇數前因子變號。當 時,遞歸分解直到長度為一。取 ,並將旋轉因子預先計算或計入每層線性工作量,算術運算數滿足 ,故為 次複運算;直接計算每個和則需 。這是通常模型下的運算次數,不是捨入誤差保證。
例題 1.11.3
(四點變換)
對 、,
例如,偶數子序列 的變換為 ,奇數子序列 的變換為 。由 (2),、,、。帕塞瓦爾公式檢驗比例:,而 。
例題 1.11.4
(循環卷積與普通卷積)
取 、,循環卷積為 。此例中其支撐沒有繞回,因此與普通有限卷積一致。相反, 與 的循環卷積為 :指標 按模四繞回零。
更一般地,長度為 的序列補零到長度 後,循環卷積在指標 與普通線性卷積一致,其後為零:每個非零指標和至多為 ,所以不會繞回。若補零不足,相差 的指標項會相加。
採樣週期傅立葉級數
設連續 週期函數 的實際傅立葉係數絕對可和,因此
其傅立葉級數一致收斂,傅立葉唯一性將其和與 等同。取樣本 ,令 為 的 DFT 乘以 。有符號頻率 與頻點 對應;大於 的指標可表示負頻率。
定理 1.11.5
(精確混疊公式)
對每個整數 ,
特別地,若 是支撐在 的三角多項式且 ,每個這樣的係數可由 恢復,其中 。當 ,兩個端點頻率 相互重合。
證明
(採樣識別餘數類)
絕對一致收斂允許把傅立葉級數代入有限 DFT 求和:
由 (1),內層和在 時為一,否則為零,證明 (3)。若 且 ,則非零差 的絕對值小於 ,故兩個不同支撐頻率不能屬於同一餘數類。當 ,,該結論失效。
由 (3) 可得一個有用的定量形式。若某個 使 ,則係數絕對可和;對有符號代表 ,有
事實上,對 有 。有限常數依賴於 ,這是絕對誤差界。在 附近,混疊係數可能與目標係數同階;即使遠離此處,若沒有目標係數的下界,也不能推出相對精度。沒有先驗假設,它不能從樣本中恢復未被區分的頻率。
例題 1.11.6
(高頻偽裝成低頻)
在八個等距點採樣 。由於 , 的樣本與 相同。函數 產生同樣數據,儘管它與 在樣本之間不同。沒有額外頻率資訊,DFT 無法區分二者。
下面的互動圖可選取樣本數 與至多四個項,並把精確預測 與直接 DFT 相比,同時顯示與之有相同樣本的混疊函數。
反例模式
邊界頻率可能在網格上消失
當偶數 ,非零函數 滿足
對每個樣本都成立。其整個樣本向量和 DFT 與零函數相同。模式 與 是不同的連續頻率,但按模 屬於同一餘數。若三角多項式支撐在 ,其奈奎斯特(Nyquist)頻點為 。特別地, 的樣本為 ,而正弦部分消失。要把這個頻點分配給兩個端點頻率,需要額外約定。恢復定理中的嚴格不等式 不能換成 。
任意 等價類都不能直接在指定點採樣:改變有限網格上的值會改變樣本,卻不改變傅立葉係數。係數絕對可和是 (3) 的方便充分條件,並非聲稱所有可能的公式都必須有該條件。
常見錯誤
常見錯誤
(把高於 的頻點讀成高頻)
在 個點採樣 。由 (3),,其餘頻點全為零。若把頻點 讀成頻率 ,就會得到 ;由於 ,它的樣本確實相同,但在樣本之間每個週期振盪七次。一個頻點決定的是模 的一個餘數類,而不是一個頻率。通常約定取 的代表;這是對數據的假設,而在 處,連這個約定也有歧義。
常見錯誤
(把未歸一化的 DFT 與傅立葉係數比較)
混疊公式 (3) 是對 而非 敘述的。對常數函數 ,樣本全為一,所以 ,而 。漏掉因子 ,每個恢復出的係數都會大 倍;採用酉歸一化時,因子改為 ,同樣必須記清。
練習
快速檢查
(計算 的四點 DFT 並驗證帕塞瓦爾公式。)
解答 · 答案
,故 。帕塞瓦爾公式兩邊均為二:。
快速檢查
(在長度四下,計算 與自身的循環卷積。與把有效長度為三的列表補零到長度五後的普通卷積比較。)
解答 · 答案
普通卷積為 。長度四時指標零與四合併,得到 。將有效長度為三的列表補零到長度五,得到無繞回的 。
快速檢查
(對在八個點採樣的 ,求 時兩個非零的歸一化 DFT 係數 。)
解答 · 答案
。模八下這兩個頻率為 和 ,故 ,其他 為零。
快速檢查
(令 。以 使用充分的無碰撞條件 時,最小整數 是多少?為甚麼這是充分條件,而不是說對這個特定函數每個更小網格都必然失敗?)
解答 · 答案
充分條件是 ,最小整數為七。它保證 內每個頻率有不同餘數。若已知支撐是 , 也給出三個不同餘數。當 ,正弦樣本全為零,數據與常數 相同。若沒有支撐限制,即使這些較小網格的已知頻率不碰撞,也沒有一般唯一性。