蝶形结

蝶形结或蝶形网路（英语：Butterfly diagram）是快速傅立叶转换演算法中的组成单位，将原本的较大点数的离散傅立叶运算，拆成较小点数的离散傅立叶运算组合，反之亦然(将原本点数较小的离散傅立叶运算，组合成较大点数的离散傅立叶运算组合)，其中蝶形结架构的n点离散傅立叶转换并不一定需要满足为点数 n = 2^p 的条件。蝶形结其名来自于底数为2的信号流成图形似蝴蝶外观(图表一)^[1]。这个词最早是由1969年一份MIT的技术性报告提到^[2]^[3]，类似的架构也出现于维特比演算法中，用于寻找隐匿层中最有可能的序列。

而蝶形结此词汇仍最常使用于库利－图基快速傅立叶变换演算法中，利用递回的方式将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蝶形结网路架构

相关条目

参考

外部链接