数字信号处理实验报告-实验1 基2-FFT算法实现

数字信号处理实验数字信号处理实验（基于MATLAB语言）实验1基2-FFT算法实现实验目的掌握基2-FFT的原理及具体实现方法。编程实现基2-FFT算法。加深理解FFT算法的特点。实验设备与环境计算机、MATLAB软件环境。实验基础理论FFT是DFT的一种快速算法，能使DFT的计算大大简化，运算时间缩短。FFT利用了WNnkFFT算法基本上可以分为两大类，即按时间抽取法和按频率抽取法。在实现FFT算法时，要重点考虑两个问题，注意数据的读取和存储：（1）输入输出的排序；（2）碟形运算的实现。按时间抽取算法中输入反序输出顺序，按频率抽取算法中输入顺序输出反序；运算过程中的每一级都由N/2个碟形运算构成，每一个碟形运算单元中，两个节点变量运算后得到的结果为下一列相同位置的节点变量，而和其他节点变量无关，可以采用原位运算，节省存储单元。另外，碟形运算中的复系数WNMATLAB中提供了用于计算FFT的函数fft，可将实验中所得到的结果与利用MATLAB中fft函数计算的结果相比较，以此验证结果的正确性。图1-1N=8按时间抽取的基-2FFT运算流图图1-2N=8按频率抽取的基-2FFT运算流图实验内容1.编程实现序列长度为N=8的按时间抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。实验过程与实验结果：设序列为{0,1,2,3,4,5,6,7}编程实现序列长度为N=8的按时间抽取的基2-FFT算法%输入数据并计算常量xn=[0,1,2,3,4,5,6,7];M=nextpow2(length(xn)),N=2^M,form=0:N/2-1;WN(m+1)=exp(-j*2*pi/N)^m;endA=[xn,zeros(1,N-length(xn))];%数据倒序操作J=0;forI=0:N-1;ifI<J;T=A(I+1);A(I+1)=A(J+1);A(J+1)=T;endK=N/2;whileJ>=K;J=J-K;K=K/2;endJ=J+K;end%分级按序依次进行蝶形运算forL=1:M;B=2^(L-1);forR=0:B-1;P=2^(M-L)*R;forK=R:2^L:N-2;T=A(K+1)+A(K+B+1)*WN(P+1);A(K+B+1)=A(K+1)-A(K+B+1)*WN(P+1);A(K+1)=T;endendendXk=A运行结果为：Xk=Columns1through528.0000-4.0000+9.6569i-4.0000+4.0000i-4.0000+1.6569i-4.0000Columns6through8-4.0000-1.6569i-4.0000-4.0000i-4.0000-9.6569i②调用函数fft计算：>>fftxn=fft(xn,N)运行结果为：fftxn=Columns1through528.0000-4.0000+9.6569i-4.0000+4.0000i-4.0000+1.6569i-4.0000Columns6through8-4.0000-1.6569i-4.0000-4.0000i-4.0000-9.6569i实验结果分析：两种计算方法结果一样，结果正确。2.编程实现序列长度为N=8的按频率抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。实验过程与实验结果：设序列为{7,6,5,4,3,2,1,0}编程实现序列长度为N=8的按频率抽取的基2-FFT算法xn=[7,6,5,4,3,2,1,0];N=8;M=log2(N);fork1=0:M-1D=2^k1;E=N/2^k1;F=N/2^(k1+1);G=N/2^(k1+1)-1;Wn=exp(-j*2*pi/E);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)]*Wn^r;endendendn1=fliplr(dec2bin([0:N-1]));n2=[bin2dec(n1)];fori=1:NXk(i)=xn(n2(i)+1);endXk运行结果为：Xk=Columns1through528.00004.0000-9.6569i4.0000-4.0000i4.0000-1.6569i4.0000Columns6through84.0000+1.6569i4.0000+4.0000i4.0000+9.6569i调用函数fft计算：>>fftxn=fft(xn,N)运行结果为：fftxn=Columns1through528.00004.0000-9.6569i4.0000-4.0000i4.0000-1.6569i4.0000Columns6through84.0000+1.6569i4.0000+4.0000i4.0000+9.6569i实验结果分析：两种计算方法结果一样，结果正确。3.将上述FFT程序推广到序列长度为N=2v的情况，要求利用原位运算。实验过程与实验结果：按时间抽取：xn=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];M=nextpow2(length(xn));N=2^M;form=0:N/2-1WN(m+1)=exp(-j*2*pi/N)^m;endDF1=[xn,zeros(1,N-length(xn))];H=0;forI=0:N-1;ifI<H;T=DF1(I+1);DF1(I+1)=DF1(H+1);DF1(H+1)=T;endK=N/2;whileH>=K;H=H-K;K=K/2;endH=H+K;endforG=1:M;F=2^(G-1);forS=0:F-1;P=2^(M-G)*S;forK=S:2^G: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;endendendDF1运行结果为：DF1=1.0e+02*Columns1through51.2000-0.0800+0.4022i-0.0800+0.1931i-0.0800+0.1197i-0.0800+0.0800iColumns6through10-0.0800+0.0535i-0.0800+0.0331i-0.0800+0.0159i-0.0800-0.0800-0.0159iColumns11through15-0.0800-0.0331i-0.0800-0.0535i-0.0800-0.0800i-0.0800-0.1197i-0.0800-0.1931iColumn16-0.0800-0.4022i按频率抽取：xn=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];M=nextpow2(length(xn));N=2^M;M=log2(N);fork1=0:M-1D=2^k1;E=N/2^k1;F=N/2^(k1+1);G=N/2^(k1+1)-1;Wn=exp(-j*2*pi/E);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)]*Wn^r;endendendn1=fliplr(dec2bin([0:N-1]));n2=[bin2dec(n1)];fori=1:NXk(i)=xn(n2(i)+1);endXk运行结果为：Xk=1.0e+02*Columns1through51.2000-0.0800+0.4022i-0.0800+0.1931i-0.0800+0.1197i-0.0800+0.0800iColumns6through10-0.0800+0.0535i-0.0800+0.0331i-0.0800+0.0159i-0.0800-0.0800-0.0159iColumns