N为合数的FFT算法

N为合数的FFT算法
上面讨论的以2为基(即N＝2M)的时间抽选和频率抽选FFT算法，由于具有程序简单、 计算效率高、对存储量要求不很高等优点，因而在实际中得到了最广泛的应用。如果N不等于 2的幂2M，通常有两种处理办法：
(1)用补零的办法将x(n)延长为2M。例如N=60，可在序列x(n)的末尾填补4个0，即 令x(60)=x(61) =x(62)=x(63)=0，使N达到26＝64，这样就可使用基2FFT算法。有限长序列补零以后，只是频谱的取样点有所增加而不会影响它的频谱X(ejω)的形状。
(2)采用以任意数为基数的FFT算法。
设N等于两个整数p和q 的乘积，即N=p·q，则可将N点DFT分解成p个q点DFT或q个p点DFT来计算。为此，首先将x(n) 分为p组，每组长为q，即

从而说明：一个N=p·q点的DFT可以用p个q点DFT来组成，如下图所示。

在最一般的情况下，设
     N=p1p2···pm，其中p1～pm是m个素因子。首先把N分解为两个因子，即N=p1q1，其中q1＝p2p3···pm，并用以上讨论的方法将DFT分解为p1个q1点DFT； 然后，将q1分解为q1=p2q2，其中q2=p3p4···pm，即将每一个q1点DFT分解为p2个q2 点DFT；这样，通过m次分解，最后达到pm点 DFT。这种算法可以使DFT的运算获得最高效率。