查看“︁蝶形结”︁的源代码

{{not|蝴蝶結}}
[[File:Butterfly-FFT.png|替代=|缩略图|圖表一、[[底数 (对数)|基底]]2[[离散傅里叶变换|-DFT]][[信号流图|信號流程圖]]
流程圖中，左側輸入訊號 x 連接右側輸出訊號 y，輸入與輸出對應到蝶形結運算，是一個由基底為2的[[库利－图基快速傅里叶变换算法|庫利－圖基快速傅立葉變換算法]]。此[[信号流图|信號流程圖]]的連接方式形似[[蝴蝶]](對應比較可參照[[閃蝶屬]])。
]]
'''蝶形結'''或'''蝶形網路'''（{{lang-en|Butterfly diagram}}）是[[快速傅里叶变换|快速傅立葉轉換]]演算法中的組成單位，將原本的較大點數的[[离散傅里叶变换|離散傅立葉運算]]，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的[[离散傅里叶变换|離散傅立葉運算]]組合)，其中蝶形結架構的n點[[离散傅里叶变换|離散傅立葉轉換]]並不一定需要滿足為點數 n = 2<sup> p</sup> 的條件。蝶形結其名來自於底數為2的[[信号流图|信號流成圖]]形似蝴蝶外觀(圖表一)<ref>Alan V. Oppenheim, Ronald W. Schafer, and John R. Buck, ''Discrete-Time Signal Processing'', 2nd edition (Upper Saddle River, NJ: Prentice Hall, 1989)</ref>。這個詞最早是由1969年一份MIT的技術性報告提到<ref>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'</ref><ref>[[wikipedia:Barry_Arthur_Cipra|Cipra, Barry A.]] (2012-06-04). [http://mathoverflow.net/a/98804 "FFT and Butterfly Diagram"]. ''mathoverflow.net''. Retrieved 2015-02-10.</ref>，類似的架構也出現於[[维特比算法|維特比演算法]]中，用於尋找隱匿層中最有可能的序列。

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

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

<math>y_0=x_0+x_1</math>

<math>y_1=x_0-x_1</math>[[File:DIT-FFT-butterfly.png|缩略图|391x391像素|圖表二、基底為2的庫利－圖基快速傅立葉變換的時域抽取法圖示，將長度為N點的DFT轉換為兩組長度為N/2點的DFTs，然後接上很多個2點的蝶形網路架構得到最後的結果]]公式裡的這對加/減法操作可畫成信號流程圖，(''x''<sub>0</sub>, ''x''<sub>1</sub>)與 (''y''<sub>0</sub>, ''y''<sub>1</sub>)連接網路圖彷彿一對蝴蝶的翅膀，因而稱作蝶形結網路架構，或簡稱蝶形結(如圖表一所示)

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

<math>y_0=x_0+x_1{\omega}_n^k </math>

<math>y_1=x_0-x_1{\omega}_n^k </math>

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

<math>x_0 = \frac{1}{2} (y_0 + y_1) \, </math>

<math>x_1 = \frac{\omega^{-k}_n}{2} (y_0 - y_1) </math>

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

== 相關條目 ==
* [[库利－图基快速傅里叶变换算法]]
* [[信号流图]]
* [[维特比算法]]
* [[快速傅里叶变换]]

== 參考 ==
<references />

== 外部連結 ==
* [https://web.archive.org/web/20060423170713/http://www.relisoft.com/science/Physics/fft.html 解釋FFT原理與蝶形結網路架構圖(英文)]
* [https://web.archive.org/web/20100430161231/http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html 蝶形結架構在不同點數的FFT實作(英文)]

[[Category:数字信号处理]]
[[Category:图表]]