实验2-matlab中基2-DIT-FFT的实现

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

电子科技大学实验报告学生姓名:学号:2010013080指导教师一、实验室名称:数字信号处理实验室二、实验项目名称:FFT的实现三、实验原理:一.FFT算法思想:1.DFT的定义:对于有限长离散数字信号{x[n]},0nN-1,其离散谱{x[k]}可以由离散付氏变换(DFT)求得。DFT的定义为:210[][]NjnkNnXkxne,k=0,1,…N-1通常令2jNNeW,称为旋转因子。2.直接计算DFT的问题及FFT的基本思想:由DFT的定义可以看出,在x[n]为复数序列的情况下,完全直接运算N点DFT需要(N-1)2次复数乘法和N(N-1)次加法。因此,对于一些相当大的N值(如1024)来说,直接计算它的DFT所作的计算量是很大的。FFT的基本思想在于,将原有的N点序列分成两个较短的序列,这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如,若N为偶数,将原有的N点序列分成两个(N/2)点序列,那么计算N点DFT将只需要约[(N/2)2·2]=N2/2次复数乘法。即比直接计算少作一半乘法。因子(N/2)2表示直接计算(N/2)点DFT所需要的乘法次数,而乘数2代表必须完成两个DFT。上述处理方法可以反复使用,即(N/2)点的DFT计算也可以化成两个(N/4)点的DFT(假定N/2为偶数),从而又少作一半的乘法。这样一级一级的划分下去一直到最后就划分成两点的FFT运算的情况。3.基2按时间抽取(DIT)的FFT算法思想:设序列长度为2LN,L为整数(如果序列长度不满足此条件,通过在后面补零让其满足)。将长度为2LN的序列[](0,1,...,1)xnnN,先按n的奇偶分成两组:12[2][][21][]xrxrxrxr,r=0,1,…,N/2-1DFT化为:1/21/212(21)000/21/21221200/21/211/22/200[]{[]}[][2][21][][][][]NNNnkrkrkNNNnrrNNrkkrkNNNrrNNrkkrkNNNrrXkDFTxnxnWxrWxrWxrWWxrWxrWWxrW上式中利用了旋转因子的可约性,即:2/2rkrkNNWW。又令/21/2111/222/200[][],[][]NNrkrkNNrrXkxrWXkxrW,则上式可以写成:12[][][]kNXkXkWXk(k=0,1,…,N/2-1)可以看出,12[],[]XkXk分别为从[]Xk中取出的N/2点偶数点和奇数点序列的N/2点DFT值,所以,一个N点序列的DFT可以用两个N/2点序列的DFT组合而成。但是,从上式可以看出,这样的组合仅表示出了[]Xk前N/2点的DFT值,还需要继续利用12[],[]XkXk表示[]Xk的后半段本算法推导才完整。利用旋转因子的周期性,有:(/2)/2/2rkrkNNNWW,则后半段的DFT值表达式:/21/21()211/21/2100[][][][]2NNNrkrkNNrrNXkxrWxrWXk,同样,22[][]2NXkXk(k=0,1,…,N/2-1),所以后半段(k=N/2,…,N-1)的DFT值可以用前半段k值表达式获得,中间还利用到()22NNkkkNN,得到后半段的[]Xk值表达式为:12[][][]kNXkXkWXk(k=0,1,…,N/2-1)。这样,通过计算两个N/2点序列12[],[]xnxn的N/2点DFT12[],[]XkXk,可以组合得到N点序列的DFT值[]Xk,其组合过程如下图所示:1[]Xk12[][]kNXkWXk2[]XknkNW-112[][]kNXkWXk比如,一个N=8点的FFT运算按照这种方法来计算FFT可以用下面的流程图来表示:W0W0W2W0W2W0W1W2W3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)W0W0W04.基2按频率抽取(DIF)的FFT算法思想:设序列长度为2LN,L为整数(如果序列长度不满足此条件,通过在后面补零让其满足)。在把[]Xk按k的奇偶分组之前,把输入按n的顺序分成前后两半:1/21100/2/21/21()200/2120[]{[]}[][][][][]2[[][]],0,1,...,12NNNnknknkNNNnnnNNNNnknkNNnnNNknkNNnXkDFTxnxnWxnWxnWNxnWxnWNxnxnWWkN因为21NNW,则有2(1)NkkNW,所以:/210[][[](1)[]],0,1,...,12NknkNnNXkxnxnWkN按k的奇偶来讨论,k为偶数时:/2120[2][[][]],0,1,...,12NrnNnNXrxnxnWkNk为奇数时:/21(21)0[21][[][]],0,1,...,12NrnNnNXrxnxnWkN前面已经推导过2/2rkrkNNWW,所以上面的两个等式可以写为:/21/20[2][[][]],0,1,...,/212NrnNnNXrxnxnWrN/21/20[21]{[[][]]},0,1,...,/212NnnrNNnNXrxnxnWWrN通过上面的推导,[]Xk的偶数点值[2]Xr和奇数点值[21]Xr分别可以由组合而成的N/2点的序列来求得,其中偶数点值[2]Xr为输入x[n]的前半段和后半段之和序列的N/2点DFT值,奇数点值[21]Xr为输入x[n]的前半段和后半段之差再与nNW相乘序列的N/2点DFT值。令1[][][]2Nxnxnxn,2[][[][]]2nNNxnxnxnW,则有:/21/211/22/200[2][],[21][],0,1,...,12NNrnrnNNnnNXrxnWXrxnWr这样,也可以用两个N/2点DFT来组合成一个N点DFT,组合过程如下图所示:[]xn[][]2Nxnxn[]2Nxn-1nNW[[][]]2nNNxnxnW二.在FFT计算中使用到的MATLAB命令:函数fft(x)可以计算R点序列的R点DFT值;而fft(x,N)则计算R点序列的N点DFT,若RN,则直接截取R点DFT的前N点,若RN,则x先进行补零扩展为N点序列再求N点DFT。函数ifft(X)可以计算R点的谱序列的R点IDFT值;而ifft(X,N)同fft(x,N)的情况。四、实验目的:离散傅氏变换(DFT)的目的是把信号由时域变换到频域,从而可以在频域分析处理信息,得到的结果再由逆DFT变换到时域。FFT是DFT的一种快速算法。在数字信号处理系统中,FFT作为一个非常重要的工具经常使用,甚至成为DSP运算能力的一个考核因素。本实验通过直接计算DFT,利用FFT算法思想计算DFT,以及使用MATLAB函数中的FFT命令计算离散时间信号的频谱,以加深对离散信号的DFT变换及FFT算法的理解。五、实验内容:a)计算实数序列5()cos,025616xnnn的256点DFT。b)计算周期为1kHz的方波序列(占空比为50%,幅度取为+/-512,采样频率为25kHz,取256点长度)256点DFT。六、实验器材(设备、元器件):安装MATLAB软件的PC机一台,DSP实验演示系统一套。七、实验步骤:(1)先利用DFT定义式,编程直接计算2个要求序列的DFT值。(2)利用MATLAB中提供的FFT函数,计算2个要求序列的DFT值。(3)(拓展要求)不改变序列的点数,仅改变DFT计算点数(如变为计算1024点DFT值),观察画出来的频谱与前面频谱的差别,并解释这种差别。通过这一步骤的分析,理解频谱分辨力的概念,解释如何提高频谱分辨力。(4)利用FFT的基本思想(基2-DIT或基2-DIF),自己编写FFT计算函数,并用该函数计算要求序列的DFT值。并对前面3个结果进行对比。(5)(拓展要求)尝试对其他快速傅立叶变换算法(如Goertzel算法)进行MATLAB编程实现,并用它来计算要求的序列的DFT值。并与前面的结果进行对比。(6)(拓展要求)在提供的DSP实验板上演示要求的2种序列的FFT算法(基2-DIT),用示波器观察实际计算出来的频谱结果,并与理论结果对比。八、实验数据及结果分析:程序:(1)对要求的2种序列直接进行DFT计算的程序%第一种序列的计算N=0:255;X=cos(5*pi*N/16);fora=1:256Y(a)=0;forb=1:256Y(a)=Y(a)+X(b)*exp(-j*2*pi*(b-1)*(a-1)/256);endendsubplot(2,1,1)stem(N,abs(Y))title('DFTµÄ½á¹û')subplot(2,1,2)Y2=fft(X);stem(N,Y2)title('FFTµÄ½á¹û')%第二种序列的计算N=0:1/(1000*25):255/(1000*25);X=512*square(2*pi*N*1000);fora=1:256Y(a)=0;forb=1:256Y(a)=Y(a)+X(b)*exp(-j*2*pi*(b-1)*(a-1)/256);endend[Y]%»­fftºÍÉÏÃæµÄ½á¹ûµÄ¶Ô±Èf=0:255;Y1=fft(X);subplot(2,1,1)stem(f,Y)title('DFTµÄ½á¹û')subplot(2,1,2)stem(f,Y1)title('FFTµÄ½á¹û')(2)对要求的2种序列进行基2-DIT和基2-DIFFFT算法程序%基-2DIT-FFT的算法%»ù-2-DIT-FFTclearclctic%½«¶ÔÊäÈëÐòÁÐx²¹ÁãÖÁ2^M¸öN=input('ÇëÊäÈëµãÊýN=');x=input('ÇëÊäÈëÐòÁÐx(ÆäÖÐÒѾ­¶¨ÒåÁËn=0:N-1)=');M=nextpow2(length(x));N=2^M;n=0:N-1;x=[x,zeros(1,N-length(x))];%¶ÔÊäÈëµÄÐòÁÐx½øÐÐÖØÐÂÅÅÐòLH=N/2;j1=LH;N1=N-2;fori=1:N1if(ij1)T=x(i+1);x(i+1)=x(j1+1);x(j1+1)=T;endk=LH;while(j1=k)j1=j1-k;k=k/2;endj1=j1+k;end%½øÐеûÐÎÔËËãforL=1:M%¼¶ÊýµÄÑ­»·B=2^(L-1);fori=0:B-1%ͬһ¼¶ÐýתÒò×ÓµÄÑ­»·p=i*2^(M-L);fork=i:2^L:(2^(M-L)-1)*(2^L)+i%ͬһ¼¶Í¬Ò»¸öÐýתÒò×ÓµÄÑ­»·.£¨ÔÚL¼¶ÖÐͬһ¸öÐýתÒò×Ó³öÏÖ2^(M-L)´Î£©temp=x(k+1);x(k+1)=temp+x(k+1+B)*exp(-j*2*pi*p/N);x(k+1+B)=temp-x(k+1+B)*exp(-j*2*pi*p/N);endendendstem(n,x)title('»ù-2-DIT-FFTµÄ½á¹û')time=toc%基-2-DIF-FFT的算法%»ù-2-DIT-FFTclearclctic%½«¶ÔÊäÈëÐòÁÐx²¹ÁãÖÁ2^M¸öN=input('ÇëÊäÈëµãÊýN=');x=input('ÇëÊäÈëÐòÁÐx(ÆäÖÐÒѾ­¶¨ÒåÁËn=0:N-1)=');M=nextpow2(length(x));N=2^M;n=0:N-1;x=[x,zeros(1,N-length(x))];%¶

1 / 13
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功