蝶形結

蝶形結或蝶形網路是快速傅立葉轉換算法中的組成單位，將原本的較大點數的離散傅立葉運算，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的離散傅立葉運算組合)。

基本介紹

• 中文名：蝶形結
• 外文名：Butterfly-shaped knot
• 套用：算法計算
• 學科：數學、信號處理

定義

蝶形結或蝶形網路（英語:Butterfly diagram）是快速傅立葉轉換算法中的組成單位，將原本的較大點數的離散傅立葉運算，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的離散傅立葉運算組合)，其中蝶形結架構的n點離散傅立葉轉換並不一定需要滿足為點數 n=2的條件。蝶形結其名來自於底數為2的信號流成圖形似蝴蝶外觀(圖表一)。這個詞最早是由1969年一份MIT的技術性報告提到，類似的架構也出現於維特比算法中，用於尋找隱匿層中最有可能的序列。

而蝶形結此辭彙仍最常使用於庫利－圖基快速傅立葉變換算法中，利用遞迴的方式將n點離散傅立葉運算中的n點輸入分解為 n=r*m，轉換輸入信號為r點的m組信號分別進行r點離散傅立葉運算(換句煥說就是r點DFT做m次)，而r點的離散傅立葉運算基本上為轉換後的輸入信號乘上旋轉因子以蝶形結架構做加法運算。(前述為時域抽取法的運算方式，逆向操作先進行蝶形結架構做加法運算，再乘上旋轉因子，則為頻域抽取法運算方式)。

基底2蝶形結網路架構

在基底為2的庫利－圖基快速傅立葉變換算法例子裡，蝶形結架構等效於2點的離散傅立葉運算，輸入為(x₀,x₁)兩點訊號，經過轉換後得到(y₀,y₁)的兩點輸出訊號，此轉換公式如下(不包含旋轉因子)：

公式里的這對加/減法操作可畫成信號流程圖，(x₀,x₁)與(y₀,y₁)連線網路圖仿佛一對蝴蝶的翅膀，因而稱作蝶形結網路架構，或簡稱蝶形結(如圖所示)。

基底為2的庫里快速傅立葉變換

更準確的來說，在基底為2的庫利－圖基快速傅立葉變換的時域抽取法中，當輸入為n=2點訊號，對應的旋轉因子，完整的蝶形結網路架構表示如下:

其中k取決於每點輸入訊號在原訊號中的位置。如果要進行逆運算，只要將上式中的ω取代為 ω即可達成。逆寫蝶形架構圖也能達到同樣效果:

此逆運算即為基底為2的庫利－圖基快速傅立葉變換的頻域抽取法。