N为组合数的FFT(任意基数的FFT算法).ppt

1、五. N为组合数的FFT（任意基数的FFT算法）,以上讨论的都是以2为基数的FFT算法，即N=2M，这种情况实际上使用得最多。 优点：程序简单，效率高，使用方便。 实际应用时，有限长序列的长度N很大程度上由人为因素确定，因此多数场合可取 N=2M，从而直接使用以 2 为基数的FFT算法。 如N不能人为确定 , N的数值也不是以2为基数的整数次方,处理方法有两种: 补零: 将x(n)补零 , 使N=2M. 例如N=30,补上x(30)=x(31)=0两点,使N=32=25,这样可直接采用以2为基数M=5的FFT程序。 有限长度序列补零后并不影响其频谱 X(ejw) ，只是频谱的采样点数增加了,上

2、例中由30点增加到32点，所以在许多场合这种处理是可接受的。, 如要求准确的N点DFT值,可采用任意数为基数的 FFT 算法 , 其 计算效率低于以2为基数FFT算法。 如 N 为复合数，可分解为两个整数p与q的乘积,像前面以2为基数时一样,FFT的基本思想是将DFT的运算尽量分小,因此,在N=pq情况下,也希望将N点的DFT分解为p个q点DFT或q个p点DFT,以减少计算量。 步骤：,分别为0, 1,，Q-1;,分别为0, 1,，P-1。,N点DFT可以重新写成为,考虑到,再令,令,以P=3，Q=4, N=12为例,(1) 先将 x(n)通过 x(n1Q+n0)改写成 x(n1,n0)。因为

3、 Q=4, n1=0,1,2, n0=0,1,2,3,故输入是按自然顺序的，即 x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,3)=x(3) x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,3)=x(7) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,3)=x(11),(2) 求个点的DFT,（）X1(k0,n0)乘以得到X1(k0,n0)。 （）求P个点的DFT，参变量是k0,（）将X2(k0,k1)通过X(k0+k1P)恢复为X(k),N=12为组合数时的FFT,（）求个P点DFT需要P2

4、次复数乘法和P(P-1)次复数加法； （）乘个W因子需要次复数乘法； （）求P个点DFT需要PQ2 次复数乘法和P（-1)次复数加法。 总的复数乘法量: QP2+N+PQ2=N(P+Q+1)； 总的复数加法量: QP(P-1)+PQ(Q-1)=N(P+Q-2),上述分解原则可推广至任意基数的更加复杂的情况。 例如, 如果N可分解为m个质数因子p1,p2,，pm，即 N=p1p2p3pm 则 第一步：可把N先分解为两个因子N=p1q1，其中q1=p2p3pm ，并用上述讨论的方法将DFT分解为p1个q1点DFT； 第二步：将q1分解为q1=p2q2，q2=p3p4pm，然后将每个q1 点DFT再

5、分解为p2个q2点DFT； ： ： 依此类推， ： 通过m次分解，一直分到最少点数的DFT运算，从而获得最高的运算效率。其运算量近似为N(p1+p2+pm)次复数乘法和复数加法。 但计算效率的提高是要以编程的复杂性为代价的，一般较少应用。 p1=p2 = =pm =2，为基2 FFT 算法。,当组合数 N=P1P2P3Pm中所有的Pi均为4时，就是基四FFT算法,以N=43为例,第一级运算的一般形式为：,6、Chirp-z变换,采用FFT可以算出全部N点DFT值，即z变换X（z）在z平面单位圆上的等间隔取样值，但要求 N 为复合数。 问题的提出： 不需要计算整个单位圆上z变换的取样，如对于窄带

6、信号，只需要对信号所在的一段频带进行分析，这时,希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑。 对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的将出现明显的尖峰，由此可较准确地测定极点频率。 要求能有效地计算当N是素数时序列的DFT。,算法原理：,螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。 已知x（n），0nN-1 令zk=AW-k ，k=0，M-

7、1 ，M ：采样点数，A、W：任意复数 其中： A0表示起始取样点的半径长度，通常A01 0表示起始取样点z0的相角 0表两相邻点之间的等分角 W0螺旋线的伸展率，W01则线外伸，W01则线内缩（反时针），W0=1则表示半径为A0的一段圆弧，若A0=1，这段圆弧则是单位圆的一部分。,图 螺旋线采样,计算z变换在采样点 zk 的值 k=0,1, ,M-1 显然，按照以上公式计算出全部M点采样值需要 NM 次复乘和（N-1）M次复加，当N及M较大时，计算量迅速增加，以上运算可转换为卷积形式，从而可采用FFT进行，这样可大大提高计算速度。 利用zk的表示式代入,nk可以用以下表示式来替换,则,定义：

8、,则,上式说明，如对信号x（n）先进行一次加权处理，加权系数为 ，然后通过一个单位脉冲响应为h（n）的线性系统，最后，对该系统的前M点输出再作一次 的加权 ，就可得到全部M点螺旋线采样值。 系统的单位脉冲响应 与频率随时间成线性增加的线性调频信号相似，因此称为Chirp -z变换。,算法实现： 由于输入信号 g（n）是有限长的，长为N， 但序列 是无限长的，而计算 0M-1 点卷积 g（k）*h（k）所需要的 h（n）是取值在n= -（N-1）M-1那一部分的值，因此，可认为h（n）是一个有限长序列，长为L=N+M-1。 所以，Chirp -z变换为两个有限长序列的线性卷积g（k）*h（k），

9、可用圆圈卷积通过FFT来实现。 h（n）的主值序列 可由h（n）作周期延拓后取0nL-1部分值获得，将 与g（n）作圆周卷积后，其输出的前M个值就是Chirp -z变换的M个值。这个圆周卷积的过程可在频域上通过FFT实现。,Chirp-z变换的实现步骤,(1)选择一个最小的整数L,使其满足L=N+M-1,同时满足L=2m ，以便采用基-2FFT算法。 （2）将 补上零值点，变为L点的序列。 （3）形成L点序列h(n)，为,（4）G（k）=FFT g（n） , L点 （5）Y（k）=G（k）H（k）, L点 （6）y（n）=IFFTY（k） , L点 （7） , 0kM-1,利用FFT计算Chirp-z变换,计算量估算： 乘法数估计 （1）（2）两步可以事先计算，不必实时计算。 （3）（7）两步两次加权共计N+M次复乘,形成Y（k）需L次复乘，一个FFT与一个IFFT需Llog2L次乘，所以 总乘法数：L+N+M+Llog2L，直接计算乘法数NM ， N及M较大时，用FFT实现Chirp-Z变换，速度上有很大的改进。,Chirp-z变换的特点：,1）输入序列的长度N 与 输出序列的长度 M 不需要相等； 2）N 及 M 不必是高度复合数，二者均