DSP課程設(shè)計(jì)報(bào)告點(diǎn)FFT的實(shí)現(xiàn)

1、DSP課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目： 256點(diǎn)FFT 院 系： 計(jì)算機(jī)科學(xué)學(xué)院 專 業(yè)： 自動(dòng)化 年 級(jí)： 2008級(jí) 姓 名： 學(xué) 號(hào)： 指導(dǎo)教師： 2011年 11 月 28日256點(diǎn)FFT的實(shí)現(xiàn)一、 設(shè)計(jì)目的1、 加深對(duì)DFT算法原理和基本性質(zhì)的理解；2、 熟悉FFT的算法原理和FFT子程序的算法流程和應(yīng)用；3、 學(xué)習(xí)用FFT對(duì)連續(xù)信號(hào)和時(shí)域信號(hào)進(jìn)行頻譜分析的方法；4、 學(xué)習(xí)DSP中FFT的設(shè)計(jì)和編程思想；5、 學(xué)習(xí)使用CCS的波形觀察器觀察波形和頻譜情況；二、 設(shè)計(jì)內(nèi)容給定256 采樣點(diǎn),求頻譜,統(tǒng)計(jì)運(yùn)行時(shí)間并在PC 上顯示。三、 設(shè)計(jì)原理快速傅里葉變換（FFT）是一種高效實(shí)現(xiàn)離散傅里葉變換（

2、DFT）的快速算法，是數(shù)字信號(hào)處理中最為重要的工具之一，它在聲學(xué)，語(yǔ)音，電信和信號(hào)處理等領(lǐng)域有著廣泛的應(yīng)用?？焖俑道锶~變換FFT旋轉(zhuǎn)因子WN 有如下的特性。對(duì)稱性： WNk+N/2=-WNk 周期性：WNn(N-k)=WNk(N-n)=WN-nk利用這些特性，既可以使DFT中有些項(xiàng)合并，減少了乘法積項(xiàng)，又可以將長(zhǎng)序列的DFT分解成幾個(gè)短序列的DFT。FFT就是利用了旋轉(zhuǎn)因子的對(duì)稱性和周期性來(lái)減少運(yùn)算量的。FFT的算法是將長(zhǎng)序列的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ù)乘又

3、減少一半，繼續(xù)進(jìn)行分解可以大大減少計(jì)算量。最小變換的點(diǎn)數(shù)稱為基數(shù)，對(duì)于基數(shù)為2的FFT算法，它的最小變換是2點(diǎn)DFT。一般而言，F(xiàn)FT算法分為按時(shí)間抽取的FFT（DIT）和按頻率抽取的（DIF FFT）兩大類。IF FFT算法是在時(shí)域內(nèi)將每一級(jí)輸入序列依次按奇偶分成個(gè)短序列進(jìn)行計(jì)算。而DIF FFT算法是在頻域內(nèi)將每一級(jí)輸入序列依次奇偶分成個(gè)短序列進(jìn)行計(jì)算。兩者的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同，得算法是一樣的。在DIF FFT算法中，旋轉(zhuǎn)因子出現(xiàn)在輸入端，而在DIF FFT算法中它出現(xiàn)在輸入端。假定序列x(n)的點(diǎn)數(shù)N是2的冪，按照DIF FFT算法可將其分為偶序列和奇序列。偶序列：x(2r)=

4、x1(r)奇序列：x(2r+1)=x2(r)其中：r=0,1,2,N/2-1 則x(n)的DFT表示為 式中，x1(k)和x2(k)分別為x1(r)和x2(r)的N/2的DFT。 由于對(duì)稱性，WNk+N/2=-WNk。因此，N點(diǎn)DFT可分為兩部分：前半部分：x(k)=x1(k)+WkNx2(k) （4）后半部分： x(N/2+k)=x1(k)-WkNx2(k) k=0,1,N/2-1 （5）從式（4）和式（5）可以看出，只要求出0N/2-1區(qū)間x1(k)和x2(k)的值，就可求出0N-1區(qū)間x(k)的N點(diǎn)值。以同樣的方式進(jìn)行抽取，可以求得N/4點(diǎn)的DFT，重復(fù)抽取過(guò)程，就可以使N點(diǎn)的DFT用上

5、組2點(diǎn)的 DFT來(lái)計(jì)算，這樣就可以大減少運(yùn)算量。基2 DIF FFT的蝶形運(yùn)算如圖(a)所示。設(shè)蝶形輸入為X1(K)和X2(K)，輸出為x(k)和x(N/2+K)，則有 x(k)=x1(k)+WkNx2(k) （6） x(N/2+k)=x1(k)-WkNx2(k) （7）在基數(shù)為2的FFT中，設(shè)N=2M，共有M級(jí)運(yùn)算，每級(jí)有N/2個(gè)2點(diǎn)FFT蝶形運(yùn)算，因此，N點(diǎn)FFT總共有MN/2個(gè)蝶形運(yùn)算。 圖(a) 基2 DIF FFT的蝶形運(yùn)算例如：基數(shù)為2的FFT，當(dāng)N=8時(shí)，共需要3級(jí)，12個(gè)基2 DIT FFT的蝶形運(yùn)算。其信號(hào)流程如圖(b)所示。x(0) x(0) WN0x(4) x(1) -1

6、 WN0x(2) x(2) -1 WN0 WN2x(6) x(3) -1 -1 WN0x(1) x(4) -1 WN0 WN1x(5) x(5) -1 -1 WN0 WN2x(3) x(6) -1 -1 WN0 WN2 WN3x(7) x(7) -1 -1 -1 圖(b) 8點(diǎn)基2 DIF FFT蝶形運(yùn)算從圖(b)可以看出，輸入是經(jīng)過(guò)比特反轉(zhuǎn)的倒位序列，稱為位碼倒置，其排列順序?yàn)閤(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ì)步驟1、 啟動(dòng)CS

7、S。2、 加載工程項(xiàng)目。3、 編譯。4、 加載.out文件5、 打開(kāi)串口調(diào)試。6、 運(yùn)行。7、 輸入Texas點(diǎn)手工發(fā)送。8、 觀察s的頻譜。si.imag=0; /虛部為0正弦波形圖，由于定義了虛部，0的下方有波形。9、 調(diào)整，只顯示實(shí)部。10、調(diào)整顯示大小，顯示更好。五、 程序主要代碼1、main( )函數(shù)#include "DSP28_Device.h"#include "FFT.h"#define send(A) SciaRegs.SCITXBUF= (A);#define WaitForReady while(SciaRegs.SCICTL2.

8、bit.TXEMPTY=0)interrupt void sci_rx_isr(void);interrupt void sci_tx_isr(void);interrupt void timer0_isr(void);void TakeTheBit(Uint32 in);Uint8 strcmp(char *a,char *b);void printf(char *a);void menu(void);char jilu26='0','0','0','0','0','0'unsigned char

9、 message20;Uint8 index=0,flag=0;Uint32 Timer0InterruptCount=0;void main(void) /-系統(tǒng)初始化（PLL，鎖相環(huán)，外設(shè)時(shí)鐘等等）-/ InitSysCtrl();/-gpio初始化-/ InitGpio(); /- 禁止CPU中斷，清除所有中斷標(biāo)志位-/ DINT; IER = 0x0000; IFR = 0x0000;/-初始化PIE控制寄存器-/ InitPieCtrl();/-初始化中斷向量表-/ InitPieVectTable();/=中斷向量配置=/ EALLOW; PieVectTable.RXAINT =

10、 & sci_rx_isr;/sci 接受中斷入口 PieVectTable.TXAINT = & sci_tx_isr;/sci 發(fā)送中斷入口 PieVectTable.TINT0 = & timer0_isr;/定時(shí)器0中斷入口 EDIS;/-分界-/ /-初始化串口（根據(jù)需要）-/ InitSci();/=初始化事件管理器=/ InitEv();/=初始化定時(shí)器0=/ InitCpuTimers(); / For this example, only initialize the Cpu Timers/ Configure CPU-Timer 0 to inter

11、rupt every second:/ 100MHz CPU Freq, 1 second Period (in uSeconds) ConfigCpuTimer(&CpuTimer0, 150, 10); /10us產(chǎn)生一次中斷/=用戶自定義的初始化 =/=顯示菜單=/ menu();/=開(kāi)啟中斷=/ PieCtrl.PIEIER1.bit.INTx7 =1 ; /CPU定時(shí)器0中斷開(kāi) PieCtrl.PIEIER9.bit.INTx1 =1 ;/SCI 接受中斷開(kāi)啟/ PieCtrl.PIEIER9.bit.INTx2 =1 ;/SCI 發(fā)送中斷開(kāi)啟 IER |=M_INT1; I

12、ER |=M_INT9;/關(guān)掉 sci中斷 EINT; ERTM;/=運(yùn)行程序=/ while(1) /=FFT測(cè)試程序=/ if(flag=1) CreatVirtualData(); /創(chuàng)建虛擬的256個(gè)采樣點(diǎn) StartCpuTimer0();/啟動(dòng)定時(shí)器開(kāi)始計(jì)時(shí) TestFFT();/開(kāi)始FFT變換 StopCpuTimer0();/停止計(jì)時(shí) TakeTheBit(Timer0InterruptCount*10); printf(jilu2);/顯示變換時(shí)間 printf("us"); flag=0; /等待中斷 ;/=/函數(shù)原型：void menu(void)/函

13、數(shù)功能：在PC上顯示本設(shè)計(jì)界面（需要根據(jù)具體調(diào)試更改）/輸入?yún)?shù)：無(wú)/輸出參數(shù)：無(wú)/=void menu(void)printf("DSP 課程設(shè)計(jì)之256點(diǎn)FFTrn");printf("運(yùn)行時(shí)間rn");interrupt void timer0_isr(void) Timer0InterruptCount+;/計(jì)數(shù)值 每10us PieCtrl.PIEACK.all=PIEACK_GROUP1; /確認(rèn)pie中斷/=/串口接收中斷服務(wù)程序/=interrupt void sci_tx_isr(void)SciaRegs.SCITXBUF=messa

14、geindex+;/自動(dòng)發(fā)送數(shù)據(jù)PieCtrl.PIEACK.all=0x0100;/確認(rèn)中斷/=/串口發(fā)送中斷服務(wù)程序/=interrupt void sci_rx_isr(void)int i;char buffer16;for (i=0;i<16;i+) bufferi=SciaRegs.SCIRXBUF.all;/receive the data from pc PieCtrl.PIEACK.all=0x0100;/響應(yīng)中斷if(strcmp(buffer,"Texas")>4)flag=1;/接受PC端發(fā)送的命令/=相應(yīng)的操作就在這添加就okSciaR

15、egs.SCIFFRX.bit.RXFIFORESET=0;SciaRegs.SCIFFRX.bit.RXFIFORESET=1;SciaRegs.SCIFFRX.bit.RXFFINTCLR=1;/=/函數(shù)原型：void printf(char *a)/函數(shù)功能：/輸入?yún)?shù)：/輸出參數(shù)：/=void printf(char *a)Uint8 i;for(i=0;ai!='0'i+)WaitForReady;/等待上個(gè)字節(jié)發(fā)送完成SciaRegs.SCITXBUF=ai;/發(fā)送當(dāng)前字節(jié)/=/函數(shù)原型：void TakeTheBit(Uint32 in)/函數(shù)功能：整形數(shù)據(jù)轉(zhuǎn)化為

16、字符型數(shù)據(jù)/輸入?yún)?shù)：轉(zhuǎn)換完成的整形數(shù)據(jù)/輸出參數(shù)：字符串的首地址/=void TakeTheBit(Uint32 in)jilu20=in/10000+48;/取萬(wàn)位jilu21=in%10000/1000+48;/取千位jilu22=in%1000/100+48;/取百位jilu23=in%100/10+48;/取十位jilu24=in%10+48;/取個(gè)位/=/函數(shù)原型：Uint8 strcmp(char *a,char *b)/函數(shù)功能：字符串比較函數(shù)/輸入?yún)?shù)：/輸出參數(shù)：/=Uint8 strcmp(char *a,char *b)Uint8 i,jilu=0;for(i=0;(a

17、i!='0')&&(bi!='0');i+)if(ai=bi) jilu+;return jilu;2、主程序簡(jiǎn)要說(shuō)明：此程序包是通用的快速傅里葉變換C語(yǔ)言函數(shù)，移植性強(qiáng)，以下部分不依賴硬件。此程序包采用聯(lián)合體的形式表示一個(gè)復(fù)數(shù)，輸入為自然順序的復(fù)數(shù)（輸入實(shí)數(shù)是可令復(fù)數(shù)虛部為0），輸出為經(jīng)過(guò)FFT變換的自然順序的復(fù)數(shù).此程序包可在初始化時(shí)調(diào)用create_sin_tab()函數(shù)創(chuàng)建正弦函數(shù)表，以后的可采用查表法計(jì)算耗時(shí)較多的sin和cos運(yùn)算，加快可計(jì)算速度。#include "math.h"#define FFT_N 256

18、 /定義福利葉變換的點(diǎn)數(shù)struct compx float real,imag; /定義一個(gè)復(fù)數(shù)結(jié)構(gòu)struct compx sFFT_N; /FFT輸入和輸出：從S0開(kāi)始存放，根據(jù)大小自己定義float SIN_TABFFT_N/4+1; /定義正弦表的存放空間/*函數(shù)原型：struct compx EE(struct compx b1,struct compx b2) 函數(shù)功能：對(duì)兩個(gè)復(fù)數(shù)進(jìn)行乘法運(yùn)算輸入?yún)?shù)：兩個(gè)以聯(lián)合體定義的復(fù)數(shù)a,b輸出參數(shù)：a和b的乘積，以聯(lián)合體的形式輸出*/struct compx EE(struct compx a,struct compx b) struct

19、 compx c; c.real=a.real*b.real-a.imag*b.imag; c.imag=a.real*b.imag+a.imag*b.real; return(c);/*函數(shù)原型：void create_sin_tab(float *sin_t)函數(shù)功能：創(chuàng)建一個(gè)正弦采樣表，采樣點(diǎn)數(shù)與福利葉變換點(diǎn)數(shù)相同輸入?yún)?shù)：*sin_t存放正弦表的數(shù)組指針輸出參數(shù)：無(wú)*/void create_sin_tab(float *sin_t) int i; for(i=0;i<=FFT_N/4;i+) sin_ti=sin(2*PI*i/FFT_N);/*函數(shù)原型：void sin_ta

20、b(float pi)函數(shù)功能：采用查表的方法計(jì)算一個(gè)數(shù)的正弦值輸入?yún)?shù)：pi 所要計(jì)算正弦值弧度值，范圍0-2*PI，不滿足時(shí)需要轉(zhuǎn)換輸出參數(shù)：輸入值pi的正弦值*/float sin_tab(float pi) int n; float a; n=(int)(pi*FFT_N/2/PI); if(n>=0&&n<=FFT_N/4) a=SIN_TABn; else if(n>FFT_N/4&&n<FFT_N/2) n-=FFT_N/4; a=SIN_TABFFT_N/4-n; else if(n>=FFT_N/2&&am

21、p;n<3*FFT_N/4) n-=FFT_N/2; a=-SIN_TABn; else if(n>=3*FFT_N/4&&n<3*FFT_N) n=FFT_N-n; a=-SIN_TABn; return a;/*函數(shù)原型：void cos_tab(float pi)函數(shù)功能：采用查表的方法計(jì)算一個(gè)數(shù)的余弦值輸入?yún)?shù)：pi 所要計(jì)算余弦值弧度值，范圍0-2*PI，不滿足時(shí)需要轉(zhuǎn)換輸出參數(shù)：輸入值pi的余弦值*/float cos_tab(float pi) float a,pi2; pi2=pi+PI/2; if(pi2>2*PI) pi2-=2*PI

22、; a=sin_tab(pi2); return a;/*函數(shù)原型：void FFT(struct compx *xin,int N)函數(shù)功能：對(duì)輸入的復(fù)數(shù)組進(jìn)行快速傅里葉變換（FFT）輸入?yún)?shù)：*xin復(fù)數(shù)結(jié)構(gòu)體組的首地址指針，struct型輸出參數(shù)：無(wú)*/void FFT(struct compx *xin) int f,m,nv2,nm1,i,k,l,j=0; struct compx u,w,t; nv2=FFT_N/2; /變址運(yùn)算，即把自然順序變成倒位序，采用雷德算法 nm1=FFT_N-1; for(i=0;i<nm1;i+) if(i<j) /如果i<j,即進(jìn)

23、行變址 t=xinj; xinj=xini; xini=t; k=nv2; /求j的下一個(gè)倒位序 while(k<=j) /如果k<=j,表示j的最高位為1 j=j-k; /把最高位變成0 k=k/2; /k/2，比較次高位，依次類推，逐個(gè)比較，直到某個(gè)位為0 j=j+k; /把0改為1 int le,lei,ip; /FFT運(yùn)算核，使用蝶形運(yùn)算完成FFT運(yùn)算 f=FFT_N; for(l=1;(f=f/2)!=1;l+) /計(jì)算l的值，即計(jì)算蝶形級(jí)數(shù) ; for(m=1;m<=l;m+) / 控制蝶形結(jié)級(jí)數(shù) /m表示第m級(jí)蝶形，l為蝶形級(jí)總數(shù)l=log（2）N le=2&l

24、t;<(m-1); /le蝶形結(jié)距離，即第m級(jí)蝶形的蝶形結(jié)相距l(xiāng)e點(diǎn) lei=le/2; /同一蝶形結(jié)中參加運(yùn)算的兩點(diǎn)的距離 u.real=1.0; /u為蝶形結(jié)運(yùn)算系數(shù)，初始值為1 u.imag=0.0; /w.real=cos(PI/lei); /不適用查表法計(jì)算sin值和cos值 / w.imag=-sin(PI/lei); w.real=cos_tab(PI/lei); /w為系數(shù)商，即當(dāng)前系數(shù)與前一個(gè)系數(shù)的商 w.imag=-sin_tab(PI/lei); for(j=0;j<=lei-1;j+) /控制計(jì)算不同種蝶形結(jié)，即計(jì)算系數(shù)不同的蝶形結(jié) for(i=j;i<=FFT_N-1;i=i+le) /控制同一蝶形結(jié)運(yùn)算，即計(jì)算系數(shù)相同蝶形結(jié) ip=i+lei; /i，ip分別表示參加蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn) t=EE(xin