第03章-6 N为合数的FFT算法

数字信号处理

第03章 离散傅里叶变换及其快 速算法邹江 zoujiang@http://doc.guandang.net

数字信号处理

3. 6 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=18=3×6,即p=3,q=6;将x(n)分成3组，每组各有6个序列 值，即

然后，将N点DFT也分解为p组来计算，即

数字信号处理

由于WNprk=WN/prk=Wqrk,因此

是一个q点DFT,这样上式可写成

从而说明：一个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的运算获得最高效率。