蝶式运算

蝶式运算(butterfly computation) ，是一种在快速傅立叶变换中得到广泛运用的运算方法。

蝶式运算定义

在快速傅立叶变换中，基2算法用得最普遍。通常按序列在时域或在频域分解过程的不同，又可分为两种：一种是时间抽取FFT算法（DIT），将N点DFT输入序列x(n)、在时域分解成2个N/2点序列而x₁(n)和x₂(n)。前者是从原序列中按偶数序号抽取而成，而后者则按奇数序号抽取而成。DIT就是这样有规律地按奇、偶次序逐次进行分解所构成的一种快速算法。其过程可表示为如图1.

则N点DFT可写成为如图2.

式中，X₁(k)和X₂(k)分别是N/2点序列x₁（n）和x₂(n)的DFT，它们的周期都是N/2，即X₁(k+N/2)=X_l(k);X₂(k+N/2)=X₂(k)。由于在高速专用器件出现以前，在实际运算中复数乘法花时较多，所以常以复乘次数的多少来估算速度的快慢。按直接计算N/2点DFT的复乘次数为(N/2)，故式

①所需总的复乘次数为2×(N/2）+N/2=N(N/2+1)≈N/2。显然，比不通过分解而直接计算N点DFT的复乘次数减少约一半。不难推出，若N是2的整数幂（N=2），则上述被分解后的N/2点序列还可以进一步分解成2个更短的N/4点序列，使复乘次数更进一步减少。依此类推，由于每分解一次降低一阶幂次，所以总可以通过r次分解，最后变换成一系列2点DFT的组合，使复乘次数大大减少，运算速度随之提高。

以N=2为例，第一次按序号(0，2，4，6)与（1，5，3，7)分解为2个4点DFT，然后又把4点DFT分别按序号（0，4)，(2，6)和（1，5)，(3，7)分解为4个2点DFT。为了直观和便于进一步导出FFT计算机程序流程框图，通常采用信号流图表示特定的算法，见图1。从图中可见，8点DFT的计算共分三级：第一级是4个2点DFT；第二级是2个4点DFT(由2个2点DFT组成）；第三级是一个8点DFT(由2个4点DFT组成）。每一级的基本运算都是由四个形似蝴蝶的蝶形运算所组成。如图2所示，每一蝶形运算的输入是两个复数数据a和b，运算结果的输出是A和B，所以完成每一个蝶形运算只含有一个复乘和两个复加。因而对于N=2点的DFT计算共分r级，每级有N/2个蝶形运算，故总共的复乘次数为如图3.

与直接算法相比，则得如图4.

当N=1024，α≈0．5%，这说明若直接计算DFT需要200秒，而采用FFT只需1秒。从图1可见，FFT的基本运算单元是蝶形运算，当输入存储单元的每一对数据一旦进入计算单元，它们就不需保留。因而可以把通过蝶形运算输出的一对数据，分别就地存储在原来的存储单元里，实现同址运算，大大减少计算机内存容量。FFT除了具有快速和节省设备外，该算法由于要求输入数据按位序颠倒，即所谓反序排列。所以还存在将原按自然顺序（正序）输入的序列通过变址，即所谓整序过程进行重新排列。一般的规律是，输入正序、输出反序；输入反序、输出正序。

还有一种是频率抽取FFT算法（DIF），将N点DFT输出序列X（k），在频域分解2个N/2点序列X（2k）和X(2k+1)。前者是从X(k)按偶数序号抽取而成，而后者则按奇次序号抽取而成。DIF就是这样有规律地按奇、偶次序进行分解所构成的一种快速算法。图3表示N=8按频率抽取FFT算法的信号流图。与按时间抽取FFT算法类似，它们之间存在对偶关系。该算法的基本运算也是蝶形运算，见图2(b)，所以计算量一样，也具有同址运算的优点和对输入或输出序列进行整序的特点。用单片高速信号处理器实现FFT常采用DIF算法。

换句话说，可以采用高基算法来实现。理论和实践证明，基数越高总运算量越会减少，但算法与控制设备更加复杂。一般说来，基4和基8算法最有效，基2算法最便于实现。因此在实际中，基2算法仍获得广泛应用。倘若序列变换长度是任意的，但总可以通过适当补零使N=2。

分裂基算法(RSFFT) 1984年由P．杜哈美尔和H．赫尔曼等导出的一种比库利图基算法更加有效的改进算法，其基本思想是在变换式的偶部采用基2算法，在变换式的奇部采用基4算法。优点是具有相对简单的结构，非常适用于实对称数据，对长度N=2能获得最少的运算量(乘法和加法），所以是选用固定基算法中的一种最佳折衷算法。