基于DSP的FFT實(shí)現(xiàn)設(shè)計(jì)報(bào)告

1、DSP課 程 設(shè) 計(jì)姓名：學(xué)號：日期：一、實(shí)驗(yàn)?zāi)康?. 加深對DFT算法原理和基本性質(zhì)的理解；2. 熟悉FFT的算法原理和FFT子程序的算法流程和應(yīng)用；3. 學(xué)習(xí)用FFT對連續(xù)信號和時(shí)域信號進(jìn)行頻譜分析的方法；4. 學(xué)習(xí)DSP中 FFT的設(shè)計(jì)和編程思想；5. 學(xué)習(xí)使用CCS勺波形觀察器觀察波形和頻譜情況；二、實(shí)驗(yàn)內(nèi)容用DSP匯編語言及C語言進(jìn)行編程，實(shí)現(xiàn)FFT運(yùn)算、對輸入信號進(jìn)行 頻譜分析。三、實(shí)驗(yàn)原理快速傅里葉變換 FFT旋轉(zhuǎn)因子 WN 有如下的特性。對稱性： WNk+N/2 =-WNk(2)周期性： WNn(N-k) =WNk(N-n) =WN-nk(3)利用這些特性，既可以使 DFT中有

2、些項(xiàng)合并，減少了乘法積項(xiàng)， 又可以將長序列的DFT分解成幾個(gè)短序列的DFT FFT就是利用了旋 轉(zhuǎn)因子的對稱性和周期性來減少運(yùn)算量的。FFT的算法是將長序列的DFT分解成短序列的DFT例如：N為 偶數(shù)時(shí)，先將N點(diǎn)的DFT分解為兩個(gè)N/2點(diǎn)的DFT使復(fù)數(shù)乘法減少 一半：再將每個(gè)N/2點(diǎn)的DFT分解成N/4點(diǎn)的DFT,使復(fù)數(shù)乘又減少 一半，繼續(xù)進(jìn)行分解可以大大減少計(jì)算量。 最小變換的點(diǎn)數(shù)稱為基數(shù)， 對于基數(shù)為2的FFT算法，它的最小變換是 2點(diǎn)DFT一般而言，F(xiàn)FT算法分為按時(shí)間抽取的FFT( DIT FFT)和按頻率 抽取的FFT (DIF FFT)兩大類。DIF FFT算法是在時(shí)域內(nèi)將每一級輸

3、 入序列依次按奇/偶分成2個(gè)短序列進(jìn)行計(jì)算。而DIF FFT算法是在頻域內(nèi)將每一級輸入序列依次奇偶分成2個(gè)短序列進(jìn)行計(jì)算。 兩者的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同，得算法是一樣的。在DIF FFT算法中，旋轉(zhuǎn)因子VN出現(xiàn)在輸入端，而在DIF FFT算法中它出現(xiàn)在輸入假定序列x(n)的點(diǎn)數(shù)N是2的幕，按照DIF FFT算法可將其分 為偶序列和奇序列。偶序列： x(2r)=x 1(r) 奇序列： x(2r+1)=x 2(r) 其中：r=0,1,2,N/2 -1 ,NXkW Nnk則x(n)的DFT表示為NiWnkNn0n為偶數(shù)N / 2iWnk N 0 n為奇數(shù)r0r0xiixi2rW N2 rkW

4、N2W Nrk/ 2W Nk X 2rkr0W Nk2r NN / 2 kNr0r0r,kx2x20,1rkrkN / 2N/2i式中，由于對稱性，WT2二-WNk。因此，N點(diǎn)DFT可分為兩部分：前半部分： x(k)=x i(k)+WkNx2(k) 后半部分：x(N/2+k)=x i(k)-W kNX2(k)k=0,1,N/2 -1從式( 4)和式( 5)可以看出，只要求出 0N/2-iX2(k)的值，就可求出0N-1區(qū)間x(k)的N點(diǎn)值。Xi (k)和 X2(k)分別為 Xi(r)和 X?(r)的 N/2 的DFT。(4)(5) 區(qū)間 xi(k) 和以同樣的方式進(jìn)行抽取，可以求得N/4點(diǎn)的D

5、FT重復(fù)抽取過程， 就可以使N點(diǎn)的DFT用上組2點(diǎn)的DFT來計(jì)算，這樣就可以大減少運(yùn) 算量?；?2 DIF FFT 的蝶形運(yùn)算如圖 3.1 所示。設(shè)蝶形輸入為 x1(k) 和X2(k),輸出為 x(k)和 x(N/2+K)，則有x(k)=x i(k)+WkNX2(k)(6)x(N/2+k)=x i(k)-WkNx2(k)(7)在基數(shù)為2的FFT中，設(shè)N=共有M級運(yùn)算，每級有N/2個(gè)2 點(diǎn)FFT蝶形運(yùn)算，因此，N點(diǎn)FFT總共有MN/2個(gè)蝶形運(yùn)算。A BC圖3.1基2 DIF FFT的蝶形運(yùn)算A+ BC例如：基數(shù)為2的FFT,當(dāng)N=8時(shí)，共需要3級，12個(gè)基2 DITFFT的蝶形運(yùn)算。其信號流程如

6、圖3.2所示x(0)Wx(4)-1Wx(2)x(2)Wx(6)Wx(1)WWx(5)5)Wx(3)x(x(7)7)-1 -1 -1Wx(圖3.2 8點(diǎn)基2 DIF FFT蝶形運(yùn)算從圖(b)可以看出，輸入是經(jīng)過比特反轉(zhuǎn)的倒位序列，稱為位碼倒置，其排列順序?yàn)?x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)其順序?yàn)檩敵鍪前醋匀豁樞蚺帕衳(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7).程序設(shè)計(jì)順序 四、FFT算法的DSP實(shí)現(xiàn)過程:觀看轉(zhuǎn)換結(jié)果，保存數(shù) 據(jù)DSP芯片的出現(xiàn)使FFT的實(shí)現(xiàn)方法變得更為方便。由于大多數(shù)DSP 芯片都具有在單指令周期

7、內(nèi)完成乘法累加操作， 并且提供了專門的 FFT指令，使得FFT算法在DSPS片實(shí)現(xiàn)的速度更快。FFT算法可以分為按時(shí)間抽取FFT和按頻率抽取FFT兩大類，輸 入也有實(shí)數(shù)和復(fù)數(shù)之分，一般情況下，都假定輸入序列為復(fù)數(shù)。（一）FFT運(yùn)算序列的存儲(chǔ)分配FFT運(yùn)算時(shí)間是衡量DSP芯片性能的一個(gè)重要指標(biāo)，因此提高FFT 的運(yùn)算速度是非常重要的。在用DSPS片實(shí)現(xiàn)FFT算法時(shí)，應(yīng)允許利 用DSPS片所提供的各種軟、硬件資源。如何利用DSPS片的有限資 源，合理地安排好所使用的存儲(chǔ)空間是十分重要的。（二）FFT運(yùn)算的實(shí)現(xiàn)用TMS320C54的匯編程序?qū)崿F(xiàn)FFT算法主要分為四步：1. 實(shí)現(xiàn)輸入數(shù)據(jù)的比特反轉(zhuǎn)輸入

8、數(shù)據(jù)的比特反轉(zhuǎn)實(shí)際上就是將輸入數(shù)據(jù)進(jìn)行碼位倒置， 以便在整個(gè)運(yùn)算后的輸出序列是一個(gè)自然序列。 在用匯編指令進(jìn)行碼位倒 置時(shí)，使用碼位倒置可以大大提高程序執(zhí)行速度和使用存儲(chǔ)器的效 率。在這種尋址方式下，AR0存放的整數(shù)N是FFT點(diǎn)的一半，一個(gè)輔 助寄存器指向一個(gè)數(shù)據(jù)存放的單元。當(dāng)使用位碼倒置尋址將 ARO加到 輔助寄存器時(shí)，地址將以位碼倒置的方式產(chǎn)生。2. 實(shí)現(xiàn)N點(diǎn)復(fù)數(shù)FFTN點(diǎn)復(fù)數(shù)FFT算法的實(shí)現(xiàn)可分為三個(gè)功能塊，即第一級蝶形運(yùn)算、第二級蝶形運(yùn)算、第三級至lOg2N級蝶形運(yùn)算。對于任何一個(gè)2的整數(shù)幕，總可以通過M次分解最后成為2點(diǎn)的DFT 計(jì)算。通過這樣的M次分解，可構(gòu)成M (即)級迭代計(jì)算，

9、每 級由N/2個(gè)蝶形運(yùn)算組成。3. 功率譜的計(jì)算用FFT計(jì)算想x(n)的頻譜，即計(jì)算NilVx(n) wnkX (k)=仁y IyX(k) 一般是由實(shí)部入R(k)和虛部Al(k)組成的復(fù)數(shù)，即YVX (k)= R(k)+j i(k)因此，計(jì)算功率譜時(shí)只需將 FFT變換好的數(shù)據(jù)，按照實(shí)部實(shí)部 XR(k)和虛部X你)求它們的平方和，然后對平方和進(jìn)行開平方運(yùn)算。 但是考慮到編程的難度，對于求FFT變換后數(shù)據(jù)的最大值，不開平方 也可以找到最大值，并對功率譜的結(jié)果沒有影響，所以在實(shí)際的DSP編程中省去了開方運(yùn)算。4. 輸出FFT結(jié)果(三) 匯編語言程序程序主體由rfft-task 、bit-rev、ff

10、t和power四個(gè)子程序組成。 rfft-task :主調(diào)用子程序，用來調(diào)用其他子程序，實(shí)現(xiàn)統(tǒng)一的接口。 bit-rev :位碼倒置子程序，用來實(shí)現(xiàn)輸入數(shù)據(jù)的比特反轉(zhuǎn)。fft : FFT算法子程序，用來完成N點(diǎn)FFT運(yùn)算。在運(yùn)算過程中，為 避免運(yùn)算結(jié)果的溢出，對每個(gè)蝶形的運(yùn)算結(jié)果右移一位。fft子程序分為三個(gè)功能塊：第一級蝶形運(yùn)算、第二級蝶形運(yùn)算、第三級至至10g2N級蝶形運(yùn)算。（四）正弦系數(shù)表和余弦系數(shù)表：正弦系數(shù)表和余弦系數(shù)表可以由數(shù)據(jù)文件coeff.inc 給出，主程序通過.copy匯編命令將正弦和余弦系數(shù)表與程序代碼匯編在一起。 在本例中，數(shù)據(jù)文件coeff.inc 給出1024復(fù)數(shù)點(diǎn)

11、FFT的正弦、余弦 系數(shù)各512個(gè)。利用此系數(shù)表可完成81024點(diǎn)FFT的運(yùn)算。（五）FFT算法的模擬信號輸入：FFT算法的模擬信號輸入可以采用C語言編程來生成一個(gè)文本文 件sin data，然后在rfft-task匯編程序中，通過.copy匯編命令將生成的數(shù)據(jù)文件復(fù)制到數(shù)據(jù)存儲(chǔ)器中，作為FFT算法的輸入數(shù)據(jù)參與 FFT運(yùn)算。這種方法的優(yōu)點(diǎn)是程序的可讀性強(qiáng)，缺點(diǎn)是當(dāng)輸入數(shù)據(jù)修 改后，必須重新編譯、匯編和鏈接。五、設(shè)計(jì)步驟：1.啟動(dòng)CCS在CCS中建立一個(gè)C源文件和一個(gè)命令文件，并將這兩 個(gè)文件添加到工程，再編譯并裝載程序：閱讀 Dsp原理及應(yīng)用中fft 用dsp實(shí)現(xiàn)的有關(guān)程序。2.雙擊O啟動(dòng)C

12、CS的仿真平臺(tái)的配著選項(xiàng)。選擇C5502Simulator3.啟動(dòng)ccs2后建立工程文件FFT.pjt4.建立源文件FFT.c與鏈接文件FFT.cmd5將這兩個(gè)文件加到FFT.pjt這個(gè)工程中6. 創(chuàng)建out文件7. 加載out文件Ml M 卅1 Q s!回 db iCSi Drajil3dtihhArlufeld rnlatAr EftpfTi 9 W*niiIPftFi卩Lxn網(wǎng) Xktiklag?liU旦 rarhMlMHTD =六、編譯程序int INPUTSAMPLENUMBER,DATASAMPLENUMBER; float fWaveRSAMPLENUMBER,fWaveISAM

13、PLENUMBER,wSAMPLENUMBER; float sin_tabSAMPLENUMBER,cos_tabSAMPLENUMBER;void InitForFFT()int i;for ( i=0;iSAMPLENUMBER;i+ ) sin_tabi=sin(PI*2*i/SAMPLENUMBER); cos_tabi=cos(PI*2*i/SAMPLENUMBER);void MakeWave()int i;for ( i=0;iSAMPLENUMBER;i+ ) INPUTi=sin(PI*2*i/SAMPLENUMBER*3)*1024;main()int i;InitFor

14、FFT();MakeWave();for ( i=0;iSAMPLENUMBER;i+ ) fWaveRi=INPUTi; fWaveIi=0.0f; wi=0.0f;FFT(fWaveR,fWaveI);for ( i=0;iSAMPLENUMBER;i+ ) DATAi=wi;while ( 1 );/ break pointvoid FFT(float dataRSAMPLENUMBER,float dataISAMPLENUMBER)int x0,x1,x2,x3,x4,x5,x6,xx;int i,j,k,b,p,L;float TR,TI,temp;/* following cod

15、e invert sequence */for ( i=0;iSAMPLENUMBER;i+ )x0=x1=x2=x3=x4=x5=x6=0;x0=i&0x01; x1=(i/2)&0x01; x2=(i/4)&0x01; x3=(i/8)&0x01;x4=(i/16)&0x01; x5=(i/32)&0x01; x6=(i/64)&0x01;xx=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6;dataIxx=dataRi;for ( i=0;iSAMPLENUMBER;i+ )dataRi=dataIi; dataIi=0;for ( L=1;L0 )b=b*2;

16、i-; /* b= 2A(L-1) */for ( j=0;j0 ) /* p=pow(2,7-L)*j; */p=p*2; i-;p=p*j;for ( k=j;k128;k=k+2*b ) /* for (3) */TR=dataRk; TI=dataIk; temp=dataRk+b; dataRk=dataRk+dataRk+b*cos_tabp+dataIk+b*sin_tabp; dataIk=dataIk-dataRk+b*sin_tabp+dataIk+b*cos_tabp; dataRk+b=TR-dataRk+b*cos_tabp-dataIk+b*sin_tabp; da

17、taIk+b=TI+temp*sin_tabp-dataIk+b*cos_tabp; /* END for (3) */ /* END for (2) */ /* END for (1) */for ( i=0;iGraph- Time/Frequency進(jìn)行如下圖所示設(shè)置。G it apt) Prnijer-ty DaJ.O；D i spl ajr T jrp eSiTime4Gr乞ph TitleffAVE5tar t Adir essftINFUTPageDATAA.cqui si 11 otl Buffer Size126TiLtdesz Titer enri ent1 ElPi sp

18、lay D nt ：sl SiDSF J?錄t 縊 Typ1Sbi t1 ievtu 邕它了0SampT Ing R&_f.色。電立)JFl o t Da FiromLe ft. t oLe ftshx t e d De_IL 豈 D1 spl a-y蘭27n!altaOKI Cane elHlp1圖33.清除顯示：在以上打開的窗口中單擊鼠標(biāo)右鍵，選擇彈出式菜單中“ Clear Display ”功能4.設(shè)置斷點(diǎn)：在程序FFT.c中有注釋“ break point ”的語句上設(shè)置 軟件斷點(diǎn)。圖45. 運(yùn)行并觀察結(jié)果。 選擇“ Debug菜單的“ Animate”項(xiàng)，或按Alt+F5鍵運(yùn)行程序 觀察“Test Wave”窗口中時(shí)域圖形；圖5 在“Test Wave窗口中點(diǎn)擊右鍵，選擇屬性，更改圖形顯示為FFT。 觀察頻域圖形。圖6 觀察“ FFT窗口中的由CCS計(jì)算出的正弦波的FFT圖7(5)改變輸入函數(shù)INPUTi=(s