实验1 基2-FFT算法实现

实验1基2-FFT算法实现一、实验目的1.掌握基2-FFT的原理及具体实现方法。2.编程实现基2-FFT算法。3.深刻理解FFT算法的特点。二、实验基础理论FFT是DFT的一种快速算法，能使DFT的计算大大简化，运算时间缩短。FFT利用了的三个固有特性。即对称性，周期性和可约性，将长序列的DFT分解为短序列的DFT，合并了DFT运算中的某些项，从而减少了DFT的运算量。FFT算法基本上可分为两大类，即按时间抽取法和按频率抽取法。N=8按照时间抽取的基2-FFT运算流图和N=8按照频率抽取的基2-FFT运算流图如下图。N=8按照时间抽取的基2-FFT运算流图N=8按照频率抽取的基2-FFT运算流图在实现FFT算法时，要重点考虑两个问题，注意数据的读取和存储：(1)输入输出的排序；（2）蝶形运算的实现。按时间抽取算法中输入反序输出顺序，按频率抽取算法中输入顺序输出反序；运算过程中的每一级都有N/2个蝶形运算构成，每一个蝶形运算单元中，两个节点变量运算后得到的结果为下一列相同位置的节点变量，而和其他节点变量无关，可以采用原位运算，节省存储单元。另外，蝶形运算中的复系数可以存储为能及时查阅的系数表，这样可以借阅运算量，但是需要N/2个复数存储器。MATLAB中提供了用于计算FFT的函数fft，可将实验中所得到的结果与利用MATLAB中fft函数计算的结果相比较，以此验证结果的正确性。三、实验内容及实验过程1.编程实现序列长度为N=8的按时间抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。①8点按照时间抽取的FFT程序代码：clear;clc;n=input('N=');v=log2(n);a=[0:0.1:(n-1)*0.1];x=sin(a);xd=bin2dec(fliplr(dec2bin([1:n]-1,v)))+1;y=x(xd);form=1:vnz=2^m;u=1;wn=exp(-2j*pi/nz);forj=1:(nz/2)fork=j:nz:nkp=k+nz/2;t=y(kp)*u;y(kp)=y(k)-t;y(k)=y(k)+t;endu=u*wn;endendfigure(1);subplot(211);stem(a,abs(y));xlabel('x');title('abs:time:dft->fft');subplot(212);prove=fft(x);stem(a,abs(prove));xlabel('x');title('abs:fft');figure(2);subplot(211);stem(a,angle(y));xlabel('x');title('angle:time:dft->fft');subplot(212);stem(a,angle(prove));xlabel('x');title('angle:fft');实验结果：N=82.编程实现序列长度为N=8的按频率抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。②8点按照频率抽取的FFT程序代码：clear;clc;n=input('N=');v=log2(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*pi/nz);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(fliplr(dec2bin([1:n]-1,v)))+1;y=x(xd);figure(1);subplot(211);stem(a,abs(y));xlabel('x');title('abs:frequency:dft->fft');subplot(212);stem(a,abs(prove));xlabel('x');title('abs:fft');figure(2);subplot(211);stem(a,angle(y));xlabel('x');title('angle:frequency:dft->fft');subplot(212);stem(a,angle(prove));xlabel('x');title('angle:fft');实验结果：N=83.将上述FFT程序推广大序列长度为N=2v的情况，要求利用原位运算。③的按照时间抽取的FFT实验代码：与①代码相同。N=1024实验结果：③按照频率抽取的FFT实验代码：与②相同N=1024实验结果：四、实验心得对于整个实验是利用快速算法实现DFT——FFT。对于FFT的两种算法的MATLAB实现。对于基2-FFT按照时间抽取和基2-FFT按照频率抽取这两种方法是我们理论学习中的重点，也是我们必须掌握和熟练计算和画出8点和16点的结果和蝶形运算图。所以对于这个实验，首先在理论上没有什么难度，都能很好的理解整个运算过程。真正的难点是怎么通过MATLAB来实现这一个功能。对于整个设计过程中，我们先分析这个蝶形运算中的纯数学关系，得到了一个数学上的各个变量的关系，这样我们就可以进行相关的程序设计了。对于旋转因子、相同旋转因子的间隔、两个运算关系之间的间隔，我们得到他们与级数的关系。这样就顺利的解决了多层循环之间的关系，那么我们的运算程序也就出来了。将运算流图转成程序思想这是一个困难之处，当解决了这个问题的时候，自然整个问题也解决了。对于基2-FFT算法的实现，使得我掌握FFT两种算法的数字信号处理的理论知识。能够熟练的计算出8点和16点的DFT，并且能够正确的画出他们关于基2-FFT按照时间抽取和基2-FF