蝶形结

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

圖表一、基底2-DFT 信號流程圖流程圖中，左側輸入訊號 x 連接右側輸出訊號 y，輸入與輸出對應到蝶形結運算，是一個由基底為2的庫利－圖基快速傅立葉變換算法。此信號流程圖的連接方式形似蝴蝶(對應比較可參照閃蝶屬)。

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

基底2蝶形結網路架構

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

$y_{0}=x_{0}+x_{1}$

$y_{1}=x_{0}-x_{1}$

圖表二、基底為2的庫利－圖基快速傅立葉變換的時域抽取法圖示，將長度為N點的DFT轉換為兩組長度為N/2點的DFTs，然後接上很多個2點的蝶形網路架構得到最後的結果

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

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

$y_{0}=x_{0}+x_{1}{\omega }_{n}^{k}$

$y_{1}=x_{0}-x_{1}{\omega }_{n}^{k}$

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

$x_{0}={\frac {1}{2}}(y_{0}+y_{1})\,$

$x_{1}={\frac {\omega _{n}^{-k}}{2}}(y_{0}-y_{1})$

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

參考

^ Alan V. Oppenheim, Ronald W. Schafer, and John R. Buck, Discrete-Time Signal Processing, 2nd edition (Upper Saddle River, NJ: Prentice Hall, 1989)
^ C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters (Report). MIT Lincoln Laboratory. p. 42. Retrieved 2015-02-10. This computation, referred to as a 'butterfly'
^ Cipra, Barry A. (2012-06-04). "FFT and Butterfly Diagram". mathoverflow.net. Retrieved 2015-02-10.

外部連結

[1] Alan V. Oppenheim, Ronald W. Schafer, and John R. Buck, Discrete-Time Signal Processing, 2nd edition (Upper Saddle River, NJ: Prentice Hall, 1989)

[2] C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters (Report). MIT Lincoln Laboratory. p. 42. Retrieved 2015-02-10. This computation, referred to as a 'butterfly'

[3] Cipra, Barry A. (2012-06-04). "FFT and Butterfly Diagram". mathoverflow.net. Retrieved 2015-02-10.

[1]

[2]

[3]

蝶形结

目录

基底2蝶形結網路架構

相關條目

參考

外部連結