快速傅立葉轉換-上

2025/8/7 數學傅立葉分析訊號與系統快速計算

這篇文章主要回顧筆者在求學期間的一些記憶。當時曾經被「快速計算方法」這門課折磨得不輕，許多理論內容雖然當時學過，但畢業後工作一段時間，早已少有接觸。最近重新翻閱舊筆記與程式碼，趁機整理一下，也當作幫自己複習一遍

快速傅立葉轉換( Fast Fourier Transform, FFT)，計算離散傅立葉轉換的一種演算法，更準確地來說這裡我們介紹的是Cooley–Tukey FFT algorithm

首先我們從離散傅立葉轉換(Discrete Fourier Transform, DFT)定義開始，因為文章篇幅有限，我這裡純粹從計算角度出發，如果想要了解從傅立葉轉換角度、或是從訊號系統角度、可以參考文章，裡面介紹得非常清楚

離散傅立葉轉換(Discrete Fourier Transform, DFT)

離散傅立葉轉換，就是在時間域與頻率域都進行離散採樣，對於一個維度離散複數向量作用後，可以得到離散維度的複數向量，是從時域轉換到頻域的過程

相對的還有另一個轉換稱為逆離散傅立葉轉換(Inverse Discrete Fourier Transform, iDFT)

逆離散傅立葉轉換，可以將向量從頻域轉換回時域

其中 $＝$ 是一個複數平面上的點，稱為複數的N次單位根(Root of Unity)，也有人稱為旋轉因子，原因可以參照下圖

旋轉因子

上圖是一個的複數單位根，滿足的五次方為 ()，只要每次自己乘上自己，就可以在複數的單位圓上旋轉，所以也被稱為旋轉因子

可以發現有以下性質

【週期性】
【對陣性】
【週期可除性】 如果是的因數
【正交性】 $如果是的倍數如果不是的倍數$

PF:

【週期性】

【對陣性】

週期可除性: $注意因為是的因數，所以是一個整數週期變為$

【正交性】

假設 Case (1) 是的倍數

令，則

所以：

Case (2) 且不是的倍數

設，則，而為首項為，公比為，共項的等比級數：又因為所以：綜合以上Case (1)、Case (2) 討論 $如果是的倍數如果不是的倍數$

🔸FFT與卷積的關係

對於長度為和的兩個離散序列，他們的離散卷積(Discrete Convolution)定義為：考慮式離散卷積定義中與的範圍：

$：$
$：$

因此，的範圍會是： $且$ 但因為的範圍本身是，所以對所有可能的而言：

當時，
當時，

因此，卷積結果的有效範圍是：

繼續觀察式(1)發現的索引值也不是只要滿足就可以，如果的值大於，且時候，會超出的索引；同理當的取值大於的取值的時候，此時索引值會產生負數，也會超出的索引。

所以在離散卷積(Discrete Convolution)中需假設，當索引值超過數列的範圍時，其值為零，也就是： $如果如果或如果如果或$ 這個「當索引直超出陣列範圍時，其值為零」的假設很重要，稍後推導時會用到

離散卷積滿足對陣性(commutativity)，也就是

PF:

這裡是遍歷的索引。為了對調和的角色（證明交換性），我們做變數代換： $令$ 考慮變數替換後的求和範圍

原本：

是從到

對應到，會得到：

當，

當，

所以新的求和範圍為：

是從到

在數學求和的符號中，習慣寫為下界小、上界大，所以順序會寫成：

是從到 $乘法交換性改寫的範圍與僅是符號，沒差$ 注意：在倒數第二個等適中，的求和範圍可以改變的原因是：

若超出的定義範圍，則

若超出的定義範圍，則

因此，兩個總和的非零項完全一致，只要和都滿足「當索引直超出陣列範圍時，其值為零」的假設，也就是說：兩邊實際參與運算的項目都只有那些索引合法的部分，其它相乘為零的部分不影響總和。

綜合以上討論，我們證明了離散卷積滿足對陣性

除了證明之外，我們也舉簡單的例子來說明對陣性

令：

方法一：

我們計算

方法二：

現在用：

🔸補零捲積（Zero Padding)

在推導，卷積定理的時候，需要將兩個數列做DFT，然後使用卷積，在使用iDFT，但是離散卷積的結果向量會讓長度變長(從變成)，為了解決不同長度序列卷積的運算，我們有兩種常見作法：

循環離散卷積 (Circular Discrete Convolution)：將序列視為週期性的（模），適合處理頻域計算或週期訊號。
補零卷積 (Zero Padding Convolution)：將兩個序列補零，使其長度足以容納完整的線性卷積結果。

這裡我們採取補零卷積 (Zero Padding Convolution)來推導

設長度為，長度為，令。

定義補零後的序列：

for , 否則為 0
for , 否則為 0

這樣都被補到長度。

📘離散捲積定理

若對補零後的序列分別取取 DFT得到，並進行頻域逐點相乘，再用iDFT轉換回時域，即可得到它們的線性捲積結果，也就是滿足一下等式：

🔸捲積定理的推導（Zero Padding + DFT）

考慮兩個經過 Zero Padding 補零 到相同長度的序列和，對應的 DFT 分別為：兩者在頻域相乘，得到：將乘積展開：

✨補充：這裡我們能合併成是因為兩個序列都已經補零到長度，也就是同一週期的旋轉因子。

回到時域：對做iDFT

將式 (3) 代入上式 (4)：將三重求和順序調整為外部先對：

觀察指數和這一項，回想旋轉因子【正交性】： $如果為的倍數其他$

以上指數和只會在一種情況下為 1：當，且旋轉因子滿足【週期性】，也就是說：所以我們僅考慮，有的情況 $令$

變數變換後得到：

再提醒一次，這個求和公式的含義是「當索引直超出陣列範圍時，其值為零」：

與同時存在（即不為 0）時，該乘積項才有效。
如果超出的範圍，那麼，自然對總和無影響。

因此，的結果就是補零後的離散捲積： $其中$

下一篇文章中我們會開始介紹演算法的部分，也就是有名的Cooley–Tukey FFT演算法

Reference

從傅立葉轉換到數位訊號處理

LOADING...