实验1 基2-FFT算法实现(1).docx

《实验1 基2-FFT算法实现(1).docx》由会员分享，可在线阅读，更多相关《实验1 基2-FFT算法实现(1).docx（6页珍藏版）》请在第一文库网上搜索。

1、实验1基2-FFT算法实现一、实验目的1 .掌握基2-FFT的原理及具体实现方法。2 .编程实现基2FFT算法。3 .加深理解FFT算法的特点。二、实验设备与环境计算机、MAT1AB软件环境。三、实验基础理论FFT是DFT的一种快速算法，能使DFT的计算大大简化，运算时间缩短。FFT利用了第人的三个固有特性，即对称性、周期性和可约性，将长序列的DFT分解为短序列的DFT,合并了DFT运算中的某些项，从而减少了DFT的运算量。FFT算法基本上可以分为两大类，即按时间抽取法和按频率抽取法。在实现FFT算法时，要重点考虑两个问题，注意数据的读取和存储：(1)输入输出的排序；(2)碟形运算的实现。按时

2、间抽取算法中输入反序输出顺序，按频率抽取算法中输入顺序输出反序；运算过程中的每一级都由N/2个碟形运算构成，每一个碟形运算单元中，两个节点变量运算后得到的结果为下一列相同位置的节点变量，而和其他节点变量无关，可以采用原位运算，节省存储单元。另外，碟形运算中的复系数除比可以存储为能及时查阅的系数表，这样可以节约计算量，但是需要N/2个复数存储器。MAT1AB中提供了用于计算FFT的函数fft,可将实验中所得到的结果与利用MAT1AB中fft函数计算的结果相比较，以此验证结果的正确性。四、实验内容1编程实现序列长度为N=8的按时间抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT

3、,并与MAT1AB中fft函数计算的结果相比较，以验证结果的正确性。2 .编程实现序列长度为N=8的按频率抽取的基2FFT算法。给定一个8点序列，采用编写的程序计算其DFT,并与MAT1AB中fft函数计算的结果相比较，以验证结果的正确性。3 .将上述FFT程序推广到序列长度为N=2v的情况，要求利用原位运算。五、实验代码及分析4 .实验代码：x=1+2j0.5+3j5+4j-2+3j6-3j5+1j9-1-2j;n=bin2dec(f1ip1r(dec2bin(18-1,3)+1;x=x;for1=1:3form=1:2A(1-1)fork=1:2A(3-1)t=xO(k+(m-1)*2A(

4、4-1)+2A(3-1);x0(k+(m-1)*2(4-1)+2(3-1)=(x0(k+(m-1)*2(4-1)-t)exp(-2*1j*pi*(k-1)(82(1-1);xO(k+(m-1)*2A(4-1)=xO(k+(m-1)*2A(4-1)+t;endendendy1=fft(x)fori=1:8y(i)=x(n(i);endyyi=Co1umns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iCo1umns6through8-3.4749+7.2322i-10.00

5、00+3.5000i-16.4246-5.0104iy=Co1umns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000-2.0000iCo1umns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104i分析：y和y1两者结果完全相同，说明结果正确。2 .实验代码： x=1+2j0.5+3j5+4j-2+3j6-3j5+1j9-1-2j;n=bin2dec(f1ip1r(dec2bin(1:8-1,3)+1；x=x; for1=1:3

6、form=1:2A(1-1)fork=1:2A(3-1)t=xO(k+(m-1)*2A(4-1)+2A(3-1);x0(k+(m-1)*2A(4-1)+2A(3-1)=(x0(k+(m-1)*2A(4-1)-t)*exp(-2*1j*pi*(k-1)/(8/2A(1-1);xO(k+(m-1)*2A(4-1)=xO(k+(m-1)*2A(4-1)+t;endendendy1=fft(x) fori=1:8y(i)=x(n(i);endyyi=Co1umns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i

7、18.5000 2.0000iCo1umns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104iy=Co1umns1through523.5000+8.0000i1.4749+10.7678i-4.0000-13.5000i-1.5754+7.0104i18.5000 2.0000iCo1umns6through8-3.4749+7.2322i-10.0000+3.5000i-16.4246-5.0104i分析：两种算法的结果相同，说明结果相同。3 .实验代码：(1)按时间抽取x=1,4,7,5,9,2,3,8,6,5,2,7,6,4

8、,13,2;M=nextpow2(1ength(xn);N=2M; form=0:N/2-1WN(m+1)=exp(-j*2*piN)m;endDF1=xn,zeros(IzN-Iengthfxn); H=0; forI=OrN-I;if1 K=N2; whi1eH=K;H=H-K;K=K2;end H=H+K;endforG=1:M;F=2(G-1);forS=0:F-1;P=2(M-G)*S;forK=S:2AG:N-2;T=DF1(K+1)+DF1(K+F+1)*WN(P+1);DF1(K+F+1)=DF1(K+1)-DF1(K+F+1)*WN(P+1);DF1(K+1)=T;enden

9、dendDF1DF1=Co1umns1through10-5.0060-5.006084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.986710.0000-4.5526Co1umns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060F1=fft(xn)F1=Co1umns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.986710.0000-4.5526Co1umns11through16-8.1429-4.9962-2.9869-5.

10、2093-7.9872-5.0060(2)按频率抽取=1,4,7,5,9,2,3,8,6,5,2,7,6,4,13,2;M=nextpow2(1ength(xn);N=2M;M=1og2(N);fork1=0:M-1D=2k1;E=N2k1;F=N2(k1+1);G=N2(k1+1)-1;Wn=exp(-j*2*piE);forg=1:DH1=(g-1)*E;H2=(g-1)*E+F;forr=0:G;k=r+1;xn(k+H1)=xn(k+H1)+xn(k+H2);xn(k+H2)=xn(k+H1)-xn(k+H2)-xn(k+H2)*Wnr;endendendn1=f1ip1r(dec2b

11、in(0:N-1);2=bin2dec(n1);fori=1:NXk(i)=n(n2(i)+1);endXkXk=Co1umns1through10-5.006084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.986710.0000-4.5526Co1umns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060F2=fft(xn)F2Co1umns1through1084.0000-5.0057-7.8833-5.0141-3.0131-5.2100-7.9867-5.006010.0000-4.5526Co1umns11through16-8.1429-4.9962-2.9869-5.2093-7.9872-5.0060六、收获与感悟通过本次数字信号处理实验，学习了基2FFT算法的实现，通过对MAT1AB中fft函数的运行结果与所编写程序结果的对比，了解了按时间抽取算法和按频率抽取算法的异同，按时间抽取算法，两种方式的结果相同，而按频率抽取算法，两种方式的结果不同。并且知道了碟形图在MAT1AB中的实现方法，对课程中的知识有了更深刻的认识。