實(shí)驗(yàn)1 基2-FFT算法實(shí)現(xiàn)

實(shí)驗(yàn)1基2-FFT算法實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?.掌握基2-FFT的原理及具體實(shí)現(xiàn)方法。2.編程實(shí)現(xiàn)基2-FFT算法。3.深刻理解FFT算法的特點(diǎn)。二、實(shí)驗(yàn)基礎(chǔ)理論FFT是DFT的一種快速算法，能使DFT的計(jì)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短。FFT利用了的三個(gè)固有特性。即對(duì)稱性，周期性和可約性，將長(zhǎng)序列的DFT分解為短序列的DFT，合并了DFT運(yùn)算中的某些項(xiàng)，從而減少了DFT的運(yùn)算量。FFT算法基本上可分為兩大類，即按時(shí)間抽取法和按頻率抽取法。N=8按照時(shí)間抽取的基2-FFT運(yùn)算流圖和N=8按照頻率抽取的基2-FFT運(yùn)算流圖如下圖。N=8按照時(shí)間抽取的基2-FFT運(yùn)算流圖N=8按照頻率抽取的基2-FFT運(yùn)算流圖在實(shí)現(xiàn)FFT算法時(shí)，要重點(diǎn)考慮兩個(gè)問題，注意數(shù)據(jù)的讀取和存儲(chǔ)：(1)輸入輸出的排序；（2）蝶形運(yùn)算的實(shí)現(xiàn)。按時(shí)間抽取算法中輸入反序輸出順序，按頻率抽取算法中輸入順序輸出反序；運(yùn)算過程中的每一級(jí)都有N/2個(gè)蝶形運(yùn)算構(gòu)成，每一個(gè)蝶形運(yùn)算單元中，兩個(gè)節(jié)點(diǎn)變量運(yùn)算后得到的結(jié)果為下一列相同位置的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無(wú)關(guān)，可以采用原位運(yùn)算，節(jié)省存儲(chǔ)單元。另外，蝶形運(yùn)算中的復(fù)系數(shù)可以存儲(chǔ)為能及時(shí)查閱的系數(shù)表，這樣可以借閱運(yùn)算量，但是需要N/2個(gè)復(fù)數(shù)存儲(chǔ)器。MATLAB中提供了用于計(jì)算FFT的函數(shù)fft，可將實(shí)驗(yàn)中所得到的結(jié)果與利用MATLAB中fft函數(shù)計(jì)算的結(jié)果相比較，以此驗(yàn)證結(jié)果的正確性。三、實(shí)驗(yàn)內(nèi)容及實(shí)驗(yàn)過程1.編程實(shí)現(xiàn)序列長(zhǎng)度為N=8的按時(shí)間抽取的基2-FFT算法。給定一個(gè)8點(diǎn)序列，采用編寫的程序計(jì)算其DFT，并與MATLAB中fft函數(shù)計(jì)算的結(jié)果相比較，以驗(yàn)證結(jié)果的正確性。①8點(diǎn)按照時(shí)間抽取的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');實(shí)驗(yàn)結(jié)果：N=82.編程實(shí)現(xiàn)序列長(zhǎng)度為N=8的按頻率抽取的基2-FFT算法。給定一個(gè)8點(diǎn)序列，采用編寫的程序計(jì)算其DFT，并與MATLAB中fft函數(shù)計(jì)算的結(jié)果相比較，以驗(yàn)證結(jié)果的正確性。②8點(diǎn)按照頻率抽取的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');實(shí)驗(yàn)結(jié)果：N=83.將上述FFT程序推廣大序列長(zhǎng)度為N=2v的情況，要求利用原位運(yùn)算。③的按照時(shí)間抽取的FFT實(shí)驗(yàn)代碼：與①代碼相同。N=1024實(shí)驗(yàn)結(jié)果：③按照頻率抽取的FFT實(shí)驗(yàn)代碼：與②相同N=1024實(shí)驗(yàn)結(jié)果：四、實(shí)驗(yàn)心得對(duì)于整個(gè)實(shí)驗(yàn)是利用快速算法實(shí)現(xiàn)DFT——FFT。對(duì)于FFT的兩種算法的MATLAB實(shí)現(xiàn)。對(duì)于基2-FFT按照時(shí)間抽取和基2-FFT按照頻率抽取這兩種方法是我們理論學(xué)習(xí)中的重點(diǎn)，也是我們必須掌握和熟練計(jì)算和畫出8點(diǎn)和16點(diǎn)的結(jié)果和蝶形運(yùn)算圖。所以對(duì)于這個(gè)實(shí)驗(yàn)，首先在理論上沒有什么難度，都能很好的理解整個(gè)運(yùn)算過程。真正的難點(diǎn)是怎么通過MATLAB來(lái)實(shí)現(xiàn)這一個(gè)功能。對(duì)于整個(gè)設(shè)計(jì)過程中，我們先分析這個(gè)蝶形運(yùn)算中的純數(shù)學(xué)關(guān)系，得到了一個(gè)數(shù)學(xué)上的各個(gè)變量的關(guān)系，這樣我們就可以進(jìn)行相關(guān)的程序設(shè)計(jì)了。對(duì)于旋轉(zhuǎn)因子、相同旋轉(zhuǎn)因子的間隔、兩個(gè)運(yùn)算關(guān)系之間的間隔，我們得到他們與級(jí)數(shù)的關(guān)系。這樣就順利的解決了多層循環(huán)之間的關(guān)系，那么我們的運(yùn)算程序也就出來(lái)了。將運(yùn)算流圖轉(zhuǎn)成程序思想這是一個(gè)困難之處，當(dāng)解決了這個(gè)問題的時(shí)候，自然整個(gè)問題也解決了。對(duì)于基2-FFT算法的實(shí)現(xiàn)，使得我掌握FFT兩種算法的數(shù)字信號(hào)處理的理論知識(shí)。能夠熟練的計(jì)算出8點(diǎn)和16點(diǎn)的DFT，并且能夠正確的畫出他們關(guān)于基2-FFT按照時(shí)間抽取和基2-FF