数字信号处理 第四章04..docx

《数字信号处理 第四章04..docx》由会员分享，可在线阅读，更多相关《数字信号处理 第四章04..docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字信号处理周治国2012.11第四章快速傅里叶变换N= 30= 5x2x3 组合数 FFT流比拟前后蝶形 rt-a空间结构N= 30= 5x2x3 组合数 FFT流比拟前后蝶形 n-aT了/43行2列5纵三、基数(指特定的分解)1. N=2v-基2 FFT算法2. NM(1)N=r1tr2，.rMM级0J?h点DFT -混合基算法(2)r1=r2=,.=rM-N= rMM级r-DFT -基-FFT算法比方：a) N=2M-S-2 FFTb) NW-基-4 FFTU!、运算量估算N=ML M个L-DFT： xMxL2=NxL +MxL(L-1)=N(L-1)乘因子：xN L个M-DFT： xL

2、xM2=NxM+_LxM(M-1)=N(M-1)总运算量：xNL+N+NM=N(L+M+1) vN2+N(L-1)+N(M-1)=N(L+M-2) N(N-1)N为复合数按时间Or抽取FFT算法流图?按频率五、统一的FFT方法与DIT、DIFN=2v(1 ) N= M x L= 2x2(2) N= M x L = 2 x 2v1(1) N=M x L= 2”1x 2为此，令产0,1,M”列号 尸0,131行号x( /, 0)MO) MD.7).心+1) L H2 -1)MQO)MLO)MQ1) L MQ22I) MU) L id)2行2”列同理，对DFT的输出X(k做类似的处理：令k=Lkl+

3、kO X(k X( kl , kO kO=O,l,.,L-l nl kl=O,.，M-lnO X (0 X (2 L X (2v - 2 vX(l X(3L X(2- 1X(0,0X(l,0LX(2v-1,0v-1 X (0,1 X (1,1 L X (2 J26/30例:N=8 4x2 x(0=x(0,0 x(l=x(0,l x(2=x(0,2 x(3=x(0,3 x(4=x( 190 x(5=x(l,l x(6=x(l,2 x(7=x(l,3 XI(0,0 Xl(0,l XI(0,2 XI(0,3 Xl(l,0 X1(1J Xl(l,2 Xl(l,3 X2(0,0 X2(0,l X2(0,

4、2 X2(0,3 X2(l,0 X2(l,l X2(l,2 X2(l,3 X(0 X(2 X(4 X(6 X(1 X(3 X(5 X(7DIF-FFT 28 / 30 图 4-18 N=8,DIF-FFT 算法流图五、统一的 FFT 方法与 DIT、DIF N=2v (2) N= M x L = 2 x 2v-l P134 图 4-11 N=8,DIT-FFT算法流图输入正序，输出逆序往年真题：1、试导出按频率抽取基-2 FFT算法的蝶形运算公式，并 画出相应的N= 16时的算法流 图。（要求输入正序，输出反 序，原位运算）往年真题：2、试导出按时间抽取基2 FFT算法的蝶形运算公式，并画出相

5、应的N= 16时的算法流图，并说明算法的特点。（要求输入反序，输出正序,原位运算）N=16基2按时间抽取FFT流N=16基-2按频率抽取FFT流.UIOIHIDb)如何理解P140“无害的” ？Matlab-FFT(7 点)物5 N为复合数的FFT算法统一的FFT算法N = 2 7基一2 FFTN。2V.如何快速计算。尸7? 处理方法：(1)通过补零，使序列长度=2丫基.2 FFT (2)N=ML (复合数)一统一的FFT算法(3)NfML (素数)-ChipZ 变换(CZT)一、算法原理Vx()，OWWN-1, N = ML (复合数): NDFTZ/ M个L。尸工如果NDFT减少了运算、L

6、个MHFTLxM2为此，令 0=0,/”产0,1,LI列号 行号MOJ) LXU) LO OMU) LMQM-1)MLM-I)MML-LM-l)横着进L行M列.LxM同理，对DFT的输出X(A)做类似的处理:令 k=Lk点X(k)k0=OJ,Lrl kj=O,I,ii工(kj k/转置M“2( k0 9 k/X(H).二 X( 11/9 110)(UM)M0)咖L 二:vtAf-l)F MQ0)HA不i) L*1,0)MQ 二二 6 二二二M M tL 3L-1)ML-1,0)(UM)X(tO)LX(M-tO)-X(L1)LX(Af-Ll)OOMX(LL-l)LX(Af-U-l).(ML)X(

7、0)X()X(W-1)L) I - X(0,0)X(l)M*l) L；X(-glL X(0J)M / O /O / M 广 M姿假设出“2( A。，A/)L行M列.LxMX(L-nyX(2L-D, L “X(江fX(Q1)(M,L)X(A)=X(小+M)=Xg4) y-i= J()唠M/I/+/I0)i=o.W -1 4-1(M,L)X(A)=X(小+M)=Xg4) y-i= J()唠M/I/+/I0)i=o.W -1 4-14-1W-l Z.-1%=0 sl =0w-iX#o，%)二卬产式中”1=0AAL行M列.LxM0 Af-L0A;( L-I,Vh0一列一列=DF(求DFTOJloL-l

8、,V/ioXl (L%) =X伙 0，%)卬；610n(lAf-LVjl2(A:OfH!) = Xt (上，()卬:_/ !一行一行A，求DFT =OF5X (%,%)料 ，w=X| (勺.%)W：，=四1 X(a + k0) = X(A) %=o0ta(仆城网啊W：MW；5 M =o*i=o M-l Z.-I= E5(/，/)%3卬产喏%一口印、 L行M列，LxMM-i=-lx=/)所即,广理解：1 .x(n), X(k)都是一维数据；Il输 入为正序：2 .xm)“横着进”使正序输入变为 L行M列二维结构(Xgm),过 复合数算法对二维数据处理： ?;x(k),/nir 可取便维数据X.(

9、kjk)(仍然为L行M列)还 原为一施止序X(k)输出：假设X(k)经过将二维数据X、(坛M) 译序.X(k)=X(Lk.+%)愉山(“横着 出“)这时一维X(k)输出缺乏正序 ;仅经过XK)咒一成x(k|k) .再将二菰数据X(k1,ko)详序. X(k)=X(LM+()输出(“横假设出”) ，这时维X(k)馀出是正序。= EXI %，=|x；#oA谓&伏 Mq)* X(出 + 储=X =oOjtoL-LVHo一列一列 求DFT式中X( 1 册)= x( %.%)此，H|OA-口(/%).X| X。,(J = x (V /)w；04% VM-l.W旋转因子一行一行 求DFT%=0= /7；J

10、X1 (际.%),0,二、运算步骤1=0.1，,L-InH =0,Af -11=0.1，,L-InH =0,Af -1行号列号(I)r(/ipn0)Tn = m/ij + n0V%, 0/:0-1(针对每一列)/ IX|(Gm)= QF7；Lt(%,0) =*(/, /)W产，防=0,1,.-1A|=O(3)X1 (从,%) = X|伙0jto-l 0noAf-I(4)Wt。，0A:0L-l (针对每一行) /MT XJ即,4)=。/7；8 (心尺=0,1，.W-1CWkWN-l 00L-l 0 外 dM-lCWkWN-l 00 X(k、,kj t X(k). ?k = Lkdh.例：N=12

11、=4x3, M=4, L=3 算法流jC ，(O.Z)4,(3)-*(0.3) C4）（uo）上】4XJ06 XuiO.l)X.(0.3x,iaxji.nX,U.94y X(2.i Xi XUt.3)mr的唐由七叱岭xn &， JC/CO.l)-登XJ0.2； XUO3. m x.4(i.n xz i.:4-20rP.144，dC2 X/CM)(呻 ir.Mvh 1w： HSS40工”1岭xwX. xtnn x.c.o) Xl) Xa& U J,万心+ hT X一 一 xmt xa t* rXb Y*ia，XC)X(5)T*()ffl -2D N=MX，.=，1X3= 12 时的 KNT 运算

12、通用同理：V/(, 0nL-l详见(438) P.142例：N=12=4x3, M=4,L=3 算法流4-20, P. 144(S)r(Q.i) X.(A.4) 尤d Aa Xt X.(C.3CO*UC)，(62ra.Z). Xtd.n *1 1g 7 rC8-“0北)X.O.C)XtO.l)XtO.l)X/D). ,万心4b x一一 y xmx-eX”)j(9K21)，(】，m】t-3 x4a.i) X2.l XM33) XJC.6 X.-1.D xjan X.C1.D */*) X*(2.1) X,*f2.2) X7S,”B -20这是一个蝶形点蝶形=*九=1*3=12时的产1订 s： n

13、un X.I.P Xams Xt Xa这仍然是一个蝶形一 户.畤，F四点蝶形- 一 -xa) T*4) 一 X ：7 xiaXU)一X I*c)xcnx(nHx(0),x(1),x(2).x(11) 乂1XXI1x(0,0)|x(OJ)x(0,2)x(0,3)x(1.0)x(1.1)x(1.2)x(1,3)x(2.oJx(Z1)x(2.2)x(23)L_)Xi(kO/%) =4二OJA-IXaO.O)1x40.1)X,(0,2)XJ0.3)MIO)X41.1)X(1.2)Xt(1.3)W2.0)IXJ2J)XJ2.2)%(2,3)% (%”)= X|(“，o)W3*()4人42-1 OVn04

14、M-1X;(0.0)X；亿 0）X；(04) X；(0,2) X；(0,3) X (1 X；(1.2X；(1.3)X e X；(22) X；(2.3)X2(%(|/)=DFTnJ Xj (A0.* ”4(0 0)X2(0,1) X0,2)X2(0,3)lXjd.O)X2(1J X2(1,2)X2(1,3)X2(Z0)Xq2)xq3)|Xl(o,4)E3HE皿取BTJL1EFAWX(0.0)x（to）X(2.0)X(0.1)X(t1)X(2,1)X(0.2)X(1,2)X(2,2)X(0.3)X(13)X(2.3)X(3 g” ,2)X(6)2X(7)TX(8x，AA)TXQ&)Txa)oi rWn&O，in,：.4r sOADdi)XlHSllJIIHtarnniallkflUAnotAU) UI叫IU) 购 ghiu*59 M-MilM4(U?l比拟前后蝶形