蝶形结

蝶形结或蝶形网络是快速傅立叶转换算法中的组成单位，将原本的较大点数的离散傅立叶运算，拆成较小点数的离散傅立叶运算组合，反之亦然(将原本点数较小的离散傅立叶运算，组合成较大点数的离散傅立叶运算组合)。

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

而蝶形结此词汇仍最常使用于库利－图基快速傅立叶变换算法中，利用递回的方式将n点离散傅立叶运算中的n点输入分解为 n=r*m，转换输入信号为r点的m组信号分别进行r点离散傅立叶运算(换句焕说就是r点DFT做m次)，而r点的离散傅立叶运算基本上为转换后的输入信号乘上旋转因子以蝶形结架构做加法运算。(前述为时域抽取法的运算方式，逆向操作先进行蝶形结架构做加法运算，再乘上旋转因子，则为频域抽取法运算方式)。

基底2蝶形结网络架构在基底为2的库利－图基快速傅立叶变换算法例子里，蝶形结架构等效于2点的离散傅立叶运算，输入为(x0,x1)两点讯号，经过转换后得到(y0,y1)的两点输出讯号，此转换公式如下(不包含旋转因子)2：

公式里的这对加/减法操作可画成信号流程图，(x0,x1)与(y0,y1)连接网络图仿佛一对蝴蝶的翅膀，因而称作蝶形结网络架构，或简称蝶形结(如图所示)。

更准确的来说，在基底为2的库利－图基快速傅立叶变换的时域抽取法中，当输入为n=2点讯号，对应的旋转因子，完整的蝶形结网络架构表示如下:

其中k取决于每点输入讯号在原讯号中的位置。如果要进行逆运算，只要将上式中的ω取代为 ω即可达成。逆写蝶形架构图也能达到同样效果:

此逆运算即为基底为2的库利－图基快速傅立叶变换的频域抽取法。

本词条内容贡献者为:

李宗秀 - 副教授 - 黑龙江财经学院