十、按时间抽取基2-FFT原理及实现

1、实验题目按时间抽取基2-FFT原理及实现实验时间实验台号实验目的基2-FFT按时间抽取的程序实现；运算量的核算；实验仪器PC台式机，软件MATLAB1实验预习：1、DFT及其性质；2、FFT算法原理；实验原理：N11、dft：X(k)DFTx(n)x(n)WN1kk0,1N1n02、W:一些性质：共轲性：(W；k)*WNnki“,nki“,mnk.nk/m可约性：WnWmNWN/m.n.nk、n.(nN)k.n.n(kN)周期性：wnwNwn3、算法原理：实验预习算怯理论推导：设序列的长度为N,且满足N二十,M为自然数,按n奇偶把分解为两个N/2点的子序列$=工(2/)，r=0,*-!,V工“

2、=x(2r+1),r=0J.-1则x(n)的DFT为Zawf+2工出印：N门-J/3-l=yH2r此、，x(2r+l)lVyZfT，r=Qr=QNt2-l常以T二£町£&*M)l!)因为.gW.用”=。2=啖rrpi"2-1Nf2-1-x(&)=zx«)W工+四XS叱z，=0=X#)+阅X#)A=0,1,2.,3其中X/k)和Xz(k)分别为X(r)和X2(r)的N/2点DFT,即N/2IK(Q=Z'(叩工=。口"("r=0JV/2-1X2(A)=Z(r)Wv；2=P?T|x2(r)Ir=0N由于X(k)和X2

3、(k)均以N/2为周期，且M月=吆所以X(k)又可表示为NX(k)=X(k)+W；X*)k=0.1,1NNX(&+；)=XI(k)-MXJA)=O,L-y-l至此，一欢时域抽取法的理论推导就完成了。从上面的两个式子中，我们定义一种新的运算符一媒形运算符。x?工一卬；号实验步骤应用函数for();题目10-1:一、根据原理图编写DIT-FFT算法程序?解：对应MATLA就码为：functionXk=ditfft(xn)M=nextpow2(length(xn);N=2AM;form=0:N/2-1WN(m+1)=exp(-j*2*pi/N)Am;%endA=xn,zeros(1,N-le

4、ngth(xn);%disp('输入到各存储单元的数据,);disp(A);须序J=0;forI=0:N-1ifI<JT=A(I+1);A(I+1)=A(J+1);A(J+1)=T;蝶形因子指数范围计算蝶形因子数据输入end%算下一个倒序K=N/2;whileJ>=KJ=J-K;K=K/2;endJ=J+K;enddisp('倒序后各个存储单元的数据');disp(A);%安次序依次进行蝶形运算forL=1:Mdisp('运算级次');disp(L);B=2A(L-1);forR=0:B-1P=2A(M-L)*R;forK=R:2AL:N-2

5、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;endenddisp('本级运算后各个存储单元的数据,);disp(A);enddisp('输出各个存储单元的数据,);Xk=A;题目10-2:二、对序列进行DFT变换时，比较直接计算法计算DFT和DIT-FTT算法计算DFT时间的差异？(需要用到第八次实验中DFT函数定义DFTfor和DFTmat)Nmax=256;ditfft_time=zeros(1,Nmax);forn=1:Nmaxx=rand(1,n);t=clock;ditfft(

6、x);ditfft_time(n)=etime(clock,t);endk=1:Nmax;subplot(3,1,1);plot(k,ditfft_time,'-');ylabel('t/s');title('DIT-FFT执行时间,)；DFTfortime=zeros(1,Nmax);forn=1:Nmaxx=rand(1,n);t=clock;DFTfor(x);DFTfor_time(n)=etime(clock,t);endsubplot(3,1,2);plot(k,DFTfor_time,ylabel('t/s');title('DFTfor执行时间);DFTmat_time=zeros(1,Nmax);forn=1:Nmaxx=rand(1,n);t=clock;DFTmat(x);'-');'DFTmat执行时间);结果10-1DFTmat_time(n)=etime(clock,t);endsubplot(3,1,3);plot(k,DFTmat_time,xlabel('n');ylabel('t/s');tit