《数字信号处理 第2版 教学课件 ppt 作者 张小虹 4数字信号处理3》由会员分享，可在线阅读，更多相关《数字信号处理 第2版 教学课件 ppt 作者 张小虹 4数字信号处理3（35页珍藏版）》请在金锄头文库上搜索。
1、4.5 N是组合数的FFT算法,1、将x(n)补零，使N成为2的整数幂。例N=30，可以,加2点，使N=32=25 ； N=1000 ，可以加24点，使,2、如果要获得准确的N点DFT，可以用任意基的FFT,算法。其基本思路还是将大点DFT尽可能分解为小,点的DFT，充分利用小点DFT的周期性。,对N不是2的整数幂的情况，介绍两种处理方法。,N=1024=210 。,4.5.1、N是任意组合数的FFT算法,1、将N点DFT分解为p1个q1点的DFT,用时间抽取法，将 x(n)分为p1组，每组q1个元素。,N点DFT分解为p1个q1点的DFT,设 N=p1p2pm,pi均为素数,令q1= p2
2、p3 pm,N= p1q1,x(p1r),x(p1r+1),x(p1r +p11),(1),(p1),(2),共有p1个，对每个k值有p11次复乘,计算量：,次复乘。,总的合成X(k)的复乘次数,每一个X(k)值有(p11)次复乘， N个X(k)值有N(p11),mF=N(p11)+ p1 (q1) 2,p1个q1点的DFT复数乘法有 p1 (q1)2次；,2、对q1再分解,令：q2=p3 p4pm，q1=p2 q2,每个q1点DFT又可以分解为p2个q2点的DFT。,因为合成q1点的DFT及有p2个q2点的DFT，所以(q1)2次,的复数乘法应为q1 ( p21)+ p2 (q2)2次，将此
3、代入(4.5-4),得到,mF = N( p11)+ p1q1 ( p21)+ p2 (q2)2,= N ( p11)+ N ( p21)+ p1p2 (q2)2,mF = N( p11)+ p1q1 ( p21)+ p2 (q2)2,= N( p1-1)+ p1 q1 p2 p1 q1 + p1p2 (q2)2,= N ( p1+ p22) + p1p2 (q2)2,N= p1 q1,3、一直分解到最后一个素数 pm,最后总的计算量（类推）,qm=1,mF = N( p1+p2+pm m) +p1p2 pm(qm)2,= N( p1+p2+pm m) +N,= N( p1+p2+pm m +
4、1), N( p1+p2+pm m ),计算效率：,举例 N=18=332,mF =p1 q1=36,q1=6,p1 =3,(1) x(n)分为三组，每组6点,x(0) ,x(3) , x(6) , x(9) , x(12), x(15),x(1) , x(4) , x(7) , x(10) , x(13) , x(16),x(2) , x(5) , x(6) , x(11) , x(14) , x(17),x(3r),x(3r+1),x(3r+2),周期性将3个6点的DFT合成一个18点的DFT。,将x(n)分解为 p1=3组、 q1 =6点的DFT，再利用Gl(k)的,其中,合成时， Gl
5、(k)为6点， X(k)为18点，所以k6, 对Gl (k),有Gl (k)6 （模运算）。,k=0 X(0)= G0(0) + G1(0) + G2(0) ；,k=1,k=9,k=17,(2) q1 =32,可以进一步分为2组3点或3组2点DFT。,取3组2点DFT，即对每个Gl (k)再分。,s=0,1,2,将r =3p+s 代入,r =3p+s,x(3r+l)=,x(3r+1),x(3r+2),x(3r),Hs (k) 两点DFT,其中 s=0,1,2,H0 (1)=x(0)x(9),Hs (k) 两点DFT,其中 s=0,1,2,而 G0(0)= H0(0)+H1(0)+ H2(0),
6、H0(0) = x(0)+x(9),l=0 , s=0,l=0 , s=1,l=0 ,s=2,G0 (k)流图如图所示,则,若以 X0 ()表示广义倒序序列，x ()表示实际输入序列，,这时输出为自然顺序，输入为广义“倒序”。,X0(6 l + 2 s + p) = x (9 p + 3s + l),X0(6 l + 2 s + p) = x (9 p + 3s + l),X0(6 l + 2 s + p) = x (9 p + 3s + l),p个pM-2点的DFT；，最后M次分解为p点的DFT。,按照N是组合数FFT的一般方法，可以将N=pM点DFT,一次分解为p个pM-1点的DFT；pM
7、-1 点DFT二次分解为,4.5.2 组合数为N=pM的FFT算法,用时间抽取法,XlpM1 (k)是第l个p M1点的DFT,Xlp是第 l 个p点的DFT,XlpM2 (k)是第l个p M2点的DFT,计算量：,mF = N ( p+ p+ + pM),= N ( p1) M,特别的，当 p = 2，,mF = N ( p1) M = NM = N log2N,计算量与基2相比,实际的计算量比上述计算量要,(类推基8，基16)的情况时，,小得多。,下面讨论基4 FFT算法。,可见，随着p效率 。,不过，当N=4M ，即以4为基,1、将N=4M点DFT分解为4个N/4点的DFT,Xl(k)均
8、为N/4点的DFT。,其中X0(k), X1(k), X2(k), X3(k)均为N/4点的DFT。,其中,X0(k)=X0(k+N/4) =X0(k+N/2) =X0(k+3N/4),X1(k)=X1(k+N/4) =X1(k+N/2) =X1(k+3N/4),X2(k)=X2(k+N/4) =X2(k+N/2) =X2(k+3N/4),X3(k)=X3(k+N/4) =X3(k+N/2) =X3(k+3N/4),2.由四个N/4点的DFT合成N点DFT，要利用N/4点DFT,的周期性，即,0(N/4) 1,N/4 (N/2)1,N/2 (3N/4)1,3N/4 N 1,3、利用对称性,蝶形如图4.5-3所示。,作乘法）。基四的基本蝶形如图4.5-2所示，简化后的,利用两个对称性，其计算量还可以减少(j,1都不必,比较后，可知基四计算量比基2还少。,例 N=4096=212时，比较基2、4、8、16运算量,同理，基8、基16有类似的结果。,例 N=4096=212时，比较基2、4、8、16运算量,可见，随着基数上升运算效率提高并不多。而基数,的增加会使算法结构复杂。并且基越大，蝶形结构,越复杂。运算量的减少是以程序（或硬件）复杂为,代价，基太大往往得不偿失。,
