快速傅里叶变换算法求组合数

以上讨论的都是以2为基数的快速傅里叶变换算法，即N=2^m，这种情况实际上使用得最多，其优点是程序简单、效率高、使用方便。实际应用时，有限长序列的长度N很大程度上由人为因素确定，因此多数场合可取N=2^m，从而直接使用基2的快速傅里叶变换算法。如N不能人为确定，N的数值也不是以2为基数的整数次幂，处理方法有两种：

1）补零。将x[n]补零，使N=2^m。例如N=30，补上x[30]=x[31]=0两点，使N=32=2⁵，这样可直接采用以2为基数m=5的快速傅里叶变换的程序。有限长度序列补零后并不影响其频谱X（e^jω），只是频谱的采样点数增加了，上例中由30点增加到32点，所以在许多场合这种处理是可接受的。

2）如要求准确的N点离散傅里叶变换值，可采用任意数为基数的快速傅里叶变换算法，其计算效率低于以2为基数的快速傅里叶变换算法。

基2快速傅里叶变换算法是将信号按奇偶逐级分解成两部分，当N=2^m时，共可做m次分解，它的基本运算是2点离散傅里叶变换。这一概念可以推广到不是基2的任意组合数的情况。

设N=N₀N₁N₂…N_m-2N_m-1，其中N_i（i=0，1，2，…，m-1）不必相等，并且不一定是2，模仿基2的推导，将N表示成

N=M₀N_m-1 （3.6.1）

式中

M₀=N₀N₁N₂…N_m-2

把x[n]分成N_m-1个子序列，每个有M₀个数据，做N_m-1个M₀点的离散傅里叶变换，然后把对应点组合成M₀个N_m-1点的离散傅里叶变换。下面以N=18为例说明这一算法。

把x[n]分成3个6点的子序列，即N=6×3，此时得

则

方括号内为6点离散傅里叶变换，令

由离散傅里叶变换的周期性，有

x₂[k+12]=x₂[k+6]=x[k] （0≤k≤5） （3.6.5）

因而把序号k写作

k=6k₂+l₂ （0≤k₂≤2，0≤l₂≤5） （3.6.6）

把式（3.6.6）代入式（3.6.3）并化简得

式（3.6.7）算法对应的流图如图3.6.1所示。式中方括号内运算对应图中6点的离散傅里叶变换（对应n₂=0，1，2），每个6点离散傅里叶变换输出分别乘以旋转因子（l₂=0，1，2，3，4，5），3个6点离散傅里叶变换对应的输出组成6个3点的离散傅里叶变换，以此完成第一次分解。

现估算一下第一次分解后所需的复数乘法次数：3个6点需复数乘法次数为3×6²，级间旋转因子的个数N=18，6个3点需6×3²次，因而总共需乘法次数为

m_c=3×6²+18+6×3²=180

而直接计算18点离散傅里叶变换需复数乘法次数18²=324，可见一次分解可以节省复数乘法次数。

由于M₀=6仍是组合数，因而要将每个6点的离散傅里叶变换再进行分解，即每个6点序列分解成3个2点的子序列。

图3.6.1 N=18=6×3时的DIT-FFT 算法第一次分解

注：为清楚起见，6个3点中只画出了一个3点。

x[3m₀]6点序列分为

x[3m₀+1]6点序列分为

x[3m₀+2]6点序列分为

这样，式（3.6.7）方括号内有

式中，x[n₀，n₁，n₂]=x[9n₀+3n₁+n₂]，方括号内为2点离散傅里叶变换。和前面的讨论一样，可将l₂写成

l₂=2k₁+k₀ （0≤k₀≤1，0≤k₁≤2）(www.xing528.com)

把上式代入式（3.6.11）得

式（3.6.6）可以用类似于图3.6.2所示的流图表示，图中对应n₂=0的6点离散傅里叶变换作进一步分解。

把式（3.6.12）代入式（3.3.7）就完成了整个N=18=2×3×3分解的组合数快速傅里叶变换运算。可以看出，以上算法中把x[n]按n进行了抽选，因而它是属于按时间抽取的快速傅里叶变换算法。下面的例子把以上算法加以归纳，并给出完整的数学描述和流图。

【例3.6.1】 试列出N=18=2×3×3分解的按时间抽取的快速傅里叶变换运算表示式，并画出相应的流图。

图3.6.2 图3.6.1中n₂=0的6点DFT进一步分解

解 按题设要求先做2点离散傅里叶变换，再做两个3点的离散傅里叶变换，由此构成18点快速傅里叶变换。

1）设置变量及其维数：由N=N₀N₁N₂=2×3×3，可以设

0≤n₀≤1，0≤n₁≤2，0≤n₂≤2

0≤k₀≤1，0≤k₁≤2，0≤k₂≤2

2）列出n，k表示式为

输入倒序

输出正序 k=6k₂+2k₁+k₀

3）列写运算表示式，并对n做分解再分别化简。由于要求做按时间抽取的快速傅里叶变换，因而化简时是对时间变量n做分解化简，即

4）画出相应的信号流图如图3.6.3所示。

图3.6.3 N=18=2×3×3时的DIT-FFT算法流图

注：图中为简明计，第二、三级蝶形运算只画出相应的1个3点典型蝶形结构，3点蝶形运算旋转因子没有标出。

通过以上例子，对高组合数的快速傅里叶变换算法作以下几点说明：

1）混合基快速傅里叶变换算法。通常高组合数做分解时，短序列的长度可能有多种分解形式，比如例3.6.1，N₂=3，N₁=3，N₀=2，分解结果的最小离散傅里叶变换单元有2点的和3点的两种，通常这些短序列离散傅里叶变换的组合，构成长序列的离散傅里叶变换，因而成为混合基快速傅里叶变换算法，有时也称为多基多进制快速傅里叶变换算法。对混合基算法排列方式有多种，所以组合数快速傅里叶变换算法在形式上比单基（例如基2）更为多样化。

2）广义倒序。为使快速傅里叶变换能够保持原位运算特点，对输入信号应作相应的抽取，这种“乱”序在组合数情况下称为广义倒序。一般情况下设N=N₀N₁N₂…N_m-1，且令0≤n₀≤N₀-1，0≤n₁≤N₁-1，…，0≤n_m-2≤N_m-2-1，0≤n_m-1≤N_m-1-1，则正序表示为

n=（N₀N₁…N_m-2）n_m-1+（N₀N₁…N_m-3）n_m-2+…+（N₀N₁）n₂+N₀n₁+n₀（3.6.13）倒序为

它与基2倒位序的区别在于当低位与高位作位序交换时，相应的加权系数也发生变化，不再满足高位、低位交换时的同位交换性质，因而有时也称n和互为倒序。当做组合数的快速傅里叶变换时，n和k的表达式必须列写成互为倒序的形式，而流图第一级蝶形运算总是决定于n表示式中的最高位点数。

3）旋转因子快速傅里叶变换算法。在上列混合基算法中，两组蝶形运算之间乘以复数因子W^r_N，它只改变前级输出序列的相位，不影响幅度，因而称为旋转因子，这种算法称为旋转因子算法。对于基2情况，N_i=2（0≤i≤m-1），它是混合基的特殊情况，因此基2快速傅里叶变换也是旋转因子算法。

4）旋转因子法所需的乘法运算量

证明 设第l（l=1，2，…，m）级是由N_i点的蝶形运算组成，该级总共有N/N_i个蝶形结构，每个N_i点蝶形运算的离散傅里叶变换需复数乘法次数为N²_i次，因而第一级总共需复数乘法次数为次，对N=N₀N₁…N_m-1，共分解为m级，因而复数乘法次数为

其次，每两级之间的旋转因子个数为N，所以级间旋转因子需复数乘法次数为N（m-1），这样旋转因子法所需复数乘法次数为

与直接计算时需要的复数乘法次数相比较，有

即从各因子的乘积变成各因子求和，其运算量的节省是显而易见的。

式（3.6.17）的统计结果是粗略的，因为所有±1，±j都作为一次乘法统计在内。另外对基2快速傅里叶变换也是不适用的，因为基2、基4等蝶形运算并不需要复数乘法。