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

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

1、实验1基2-FFT算法实现一、实验目的1掌握基2-FFT的原理及具体实现方法。2 .编程实现基2-FFT算法。3 .深刻理解FFT算法的特点。二、实验基础理论FFT是DFT的一种快速算法，能使DFT的计算大大简化，运算时间缩短。FFT利用了W，的三个固有特性。即对称性，周期性和可约性，将长序列的DFT分解为短序列的DFT,合并了DFT运算中的某些项，从而减少了DFT的运算量。在实现FFT算法时，要重点考虑两个问题，注意数据的读取和存储：(1)输入输出的排序；(2)蝶形运算的实现。按时间抽取算法中输入反序输出顺序，按频率抽取算法中输入顺序输出反序；运算过程中的每一级都有N/2个蝶形运算构成,每一

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

3、c1ear;c1c;n=input(,N-);v=1og2(n);a=0:0.1:(n-1)*0.1;x=sin(a);xd=bin2dec(f1ip1r(dec2bin(1:n-1,v)+1；y=(d);form=1:vnz=2m;u=1;wn=exp(-2j*pinz);forj=k(nz2)fork=j:nz:nkp=k+nz/2;t=y(kp)*u;y(kp)=y(k)-1;y(k)=y(k)+1;endu=u*wn;endendfigure(1);subp1ot(211);stem(a,abs(y);x1abe1(x);tit1e(abs:time:dft-ffO;subp1ot(2

4、12);prove=fft(x);stem(a,abs(prove);x1abe1(x,)tit1e(absrfft,);figure(2);subp1ot(211);stem(a,ang1e(y);x1abe1(x,)itit1e(,ang1e1imerdft-fft,);sub1ot(212);stem(a,ang1e(prove);x1abe1(x,)jtit1e(ang1efft);实验结果：N=8abs:time:dft-fft2 .编程实现序列长度为N=8的按频率抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT,并与MAT1AB中fft函数计算的结果相比较，以验

5、证结果的正确性。8点按照频率抽取的FFT程序代码：c1ear;c1c;n=input(,N=);V=1og2(n);a=0:0.1:(n-1)*0.1;x=sin(a);prove=fft(x);form=1:vnz=2(v+1-m);u=1;wn=exp(-2j*pinz);forj=1:(nz/2)fork=j:nz:nkp=k+nz/2;t=x(k)+x(kp);x(kp)=(x(k)-x(kp)*u;x(k)=t;endu=u*wn;endendxd=bin2dec(f1ip1r(dec2bin(1:n-1,v)+1;y=X(Xd);figure(1);subp1ot(211);ste

6、m(a,abs(y);x1abe1(x,)itit1e(,absfrequencyft-fft);subp1ot(212);stem(a,abs(prove);x1abe1(x)itit1e(absfft,);figure(2);subp1ot(211);stem(a,ang1e(y);x1abe1(x,)itit1e(,ang1efrequencydft-fft);subp1ot(212);stem(a,ang1e(prove);x1abe1(,x,)jtit1e(ang1ezfft);实验结果：N=8abs:frequency3 卜IIII1;O21 -QOItyyyY.00.10.20.

7、30.40.50.60.7xabs:fft3IIIO2 1-QO1?T.00.10.20.30.40.50.60.73.将上述FFT程序推广大序列长度为N=2v的情况，要求利用原位运算。2的按照时间抽取的FFT实验代码：与代码相同。N=1024Xabs:fft按照频率抽取的FFT实验代码：与相同N=1024abs:frequencyxang1e:frequency:dft-fftO20406080100120xang1e:fftO20406080100120四、实验心得X对于整个实验是利用快速算法实现DFTFFT0对于FFT的两种算法的MAT1AB实现。对于基2-FFT按照时间抽取和基2-FF

8、T按照频率抽取这两种方法是我们理论学习中的重点，也是我们必须掌握和熟练计算和画出8点和16点的结果和蝶形运算图。所以对于这个实验，首先在理论上没有什么难度，都能很好的理解整个运算过程。真正的难点是怎么通过MAT1AB来实现这一个功能。对于整个设计过程中，我们先分析这个蝶形运算中的纯数学关系，得到了一个数学上的各个变量的关系，这样我们就可以进行相关的程序设计了。对于旋转因子、相同旋转因子的间隔、两个运算关系之间的间隔，我们得到他们与级数的关系。这样就顺利的解决了多层循环之间的关系，那么我们的运算程序也就出来了。将运算流图转成程序思想这是一个困难之处，当解决了这个问题的时候，自然整个问题也解决了。对于基2-FFT算法的实现，使得我掌握FFT两种算法的数字信号处理的理论知识。能够熟练的计算出8点和16点的DFT,并且能够正确的画出他们关于基2-FFT按照时间抽取和基2-FFT按照频率抽取的运算流图。通过实验，我加深了对于基2-FFT算法的理解，并且加深和巩固了自己对于DFT的理解，并且提升了自己对于FFT的运用。并且熟悉了对于MAT1AB这个强大的数学软件的对DSP处理方面的强大优势。这样也有助于我在学习理论知识的使用MAT1AB来实现一些信号的的处理。