资源描述：
《数字信号处理 第四章04new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数字信号处理周治国2012.11第四章快速傅里叶变换往年真题：1、试导出按频率抽取基-2FFT算法的蝶形运算公式，并画出相应的N=16时的算法流图。（要求输入正序，输出反序，原位运算）往年真题：2、试导出按时间抽取基-2FFT算法的蝶形运算公式，并画出相应的N=16时的算法流图，并说明算法的特点。（要求输入反序，输出正序，原位运算）N=16基-2按时间抽取FFT流图N=16基-2按频率抽取FFT流图§4-5N为复合数的FFT算法——统一的FFT算法n如何理解P140N=2®基-2FFT“无害的”？nN¹2，如
2、何快速计算DFT?处理方法：Matlab-FFT(7点)(1)通过补零，使序列长度=2ν→基-2FFT(2)N=ML（复合数）→统一的FFT算法(3)N≠ML（素数）→Chirp-Z变换(CZT)一、算法原理"x(n),0£n£N-1,N=ML（复合数）∵N-DFT~N2M个L-DFT~M×L2∴如果N-DFT减少了运算L个M8/30-DFT~L×M2L为此，令n=Mn1+n0,n0=0,1,…,M-1——列号Mn1=0,1,…,L-1——行号x(n)x(n1,n0)(L,M)éx(0)x(1)Lx(M-1)
3、ùéx(0,0)x(0,1)Lx(0,M-1)ùêúêúx(M)x(M+1)Lx(2M-1)x(1,0)x(1,1)Lx(1,M-1)êúêúêMOOMúêMOOMúêúêúëx(M(L-1))LLx(ML-1)ûëx(L-1,0)x(L-1,1)Lx(L-1,M-1)û9/30横着进L行M列，LxMM同理，对DFT的输出X(k)做类似的处理：令k=Lk1+k0k0=0,1,…,L-1~n1k1=0,1,…,M-1~n0L转置X(k)X(k1,k0)X2(k0,k1)(M,L)(L,M)éùX(0)X(L)L
4、X((ML-1))éùX(0,0)X(1,0)LXM(-1,0)êúêúX(1)X(L+1)LX((ML-+1)1)X(0,1)X(1,1)LXM(-1,1)êúêúêúMOOMêúMOOMêúêúëûX(L-1)X(2L--1)LX(ML1)ëûX(0,L-1)X(1,L-1)LX(ML--1,1)竖着出X2(k0,k1)10/30L行M列，LxMDL-1式中X(k,n)=åx(n,n)Wk0n110010L(M,L)n1=0DX(k)=X(Lk1+k0)=X(k1,k0)一列一列=DFTn[x(nn10,
5、)]N-11kn求DFT=åx(n)WNx(Mn1+n0)0£k00£Ln-"1,n=0DML--11¢kn00=ååx(nnW,)(Mn1++n0)()Lkk10X1(k0,n0)=X1(k00,)nWN10Nnn01==000£n£Mk-"1,0ML--11=x(nn,)WMLkn11WMn1k0WWLk1n0kn00DL-1¢åå10NNNNX(k,n)=åX(k,n)Wk1n0nn==00201100M01ML--11n0=0=ååx(nn,)Wk0n1WWk0n0kn10一行一行D¢10LNM求DF
6、T=DFT[X(kn,)]nn==00n010001L行M列，LxMM-10£kM1£-1,=å[X(k,n)Wk0n0]Wk1n0100NM0£k£Ln-"1,n0=000M-1转置X¢knWk1n0=å1(0,0)M=X2(k0,k1)=X(k1,k0)=X(Lk1+k0)=X(k)n0=00£k11£/L30-1,0£k£M-10£k£N-101L行M列，M行L列，LxMMxL理解：1.x(n)，X(k)都是一维数据；且输入为正序；X(k)=X(Lk+k)=X(k,k)1010N-12.x(n)“横着进
7、”使正序输入变为kn=åx(n)WNx(Mn1+n0)L行M列二维结构(x(n1,n0))，经过n=0复合数算法对二维数据处理；ML--11=ååx(nnW,)(Mn1++n0)()Lkk10①若X(k)“竖着出”输出可以使二10Nnn==00维数据X(k,k)(仍然为L行M列)还01201ML--11原为一维正序X(k)输出；=ååx(nn,)WMLkn11WMn1k0WWLk1n0kn0010NNNN②若X(k)经过将二维数据X(k,k)nn==0020101ML--11译序，X(k)=X(Lk1+k0)
8、输出(“横着=ååx(nn,)Wk0n1WWk0n0kn10出”)，这时一维X(k)输出不是正序10LNMnn01==00；但经过X2(k0,k1)转置成X(k1,k0)L行M列，LxM，再将二维数据X(k1,k0)译序，M-1=å[X(k,n)Wk0n0]Wk1n0X(k)=X(Lk1+k0)输出(“横着出”)100NM，这时一维X(k)输出是正序。n0=0M-1转置X¢knWk1n0=å1(0,
