DSP-快速傅立葉變換算法實(shí)驗(yàn)

1、中 南 大 學(xué)dsp技術(shù)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：快速傅立葉變換(fft) 算法實(shí)驗(yàn)專業(yè)班級(jí)：信息0602學(xué)生姓名：張倩曦 （學(xué)號(hào)： 24）指導(dǎo)老師：陳寧完成日期： 2009 年12月2日中南大學(xué)信息科學(xué)與工程學(xué)院快速傅立葉變換 (fft) 算法實(shí)驗(yàn)一實(shí)驗(yàn)?zāi)康?掌握用窗函數(shù)法設(shè)計(jì) fft 快速傅里葉的原理和方法；2熟悉 fft 快速傅里葉特性；3了解各種窗函數(shù)對(duì)快速傅里葉特性的影響。二實(shí)驗(yàn)設(shè)備pc 兼容機(jī)一臺(tái)，操作系統(tǒng)為 windows2000(或windows98，windowsxp，以下默認(rèn)為windows2000)，安裝 code composer studio 2.0 軟件。三實(shí)驗(yàn)原理1fft

2、 的原理和參數(shù)生成公式：公式（ 1）fft 運(yùn)算公式fft 并不是一種新的變換，它是離散傅立葉變換（dft）的一種快速算法。由于我們?cè)谟?jì)算 dft 時(shí)一次復(fù)數(shù)乘法需用四次實(shí)數(shù)乘法和二次實(shí)數(shù)加法；一次復(fù)數(shù)加法則需二次實(shí)數(shù)加法。每運(yùn)算一個(gè) x（k）需要4n 次復(fù)數(shù)乘法及 2n+2（n-1）=2（2n-1）次實(shí)數(shù)加法。所以整個(gè) dft運(yùn)算總共需要 4n2 次實(shí)數(shù)乘法和 n*2(2n-1)=2n(2n-1) 次實(shí)數(shù)加法。如此一來，計(jì)算時(shí)乘法次數(shù)和加法次數(shù)都是和n2 成正比的，當(dāng) n 很大時(shí)，運(yùn)算量是可觀的，因而需要改進(jìn)對(duì)dft 的算法減少運(yùn)算速度。根據(jù)傅立葉變換的對(duì)稱性和周期性，我們可以將dft 運(yùn)算

3、中有些項(xiàng)合并。我們先設(shè)序列長(zhǎng)度為 n=2l，l 為整數(shù)。將n=2l 的序列 x(n)(n=0,1, ， n-1)，按n的奇偶分成兩組，也就是說我們將一個(gè)n 點(diǎn)的dft 分解成兩個(gè) n/2 點(diǎn)的dft，他們又重新組合成一個(gè)如下式所表達(dá)的n 點(diǎn)dft：一般來說，輸入被假定為連續(xù)的。 當(dāng)輸入為純粹的實(shí)數(shù)的時(shí)候，我們就可以利用左右對(duì)稱的特性更好的計(jì)算dft。我們稱這樣的 rfft 優(yōu)化算法是包裝算法：首先2n 點(diǎn)實(shí)數(shù)的連續(xù)輸入稱為“ 進(jìn)包” 。其次 n 點(diǎn)的fft 被連續(xù)運(yùn)行。最后作為結(jié)果產(chǎn)生的n 點(diǎn)的合成輸出是“ 打開” 成為最初的與 dft 相符合的 2n 點(diǎn)輸入。使用這一思想，我們可以劃分fft

4、 的大小，它有一半花費(fèi)在包裝輸入 o （n） 的操作和打開輸出上。 這樣的 rfft 算法和一般的 fft 算法同樣迅速，計(jì)算速度幾乎都達(dá)到了兩次dft的連續(xù)輸入。下列一部分將描述更多的在tms320c55x 上算法和運(yùn)行的細(xì)節(jié)。5程序流程圖：四實(shí)驗(yàn)步驟（一）第一部分1實(shí)驗(yàn)準(zhǔn)備：-設(shè)置軟件仿真模式。-啟動(dòng)ccs。2打開工程。瀏覽程序，工程目錄為 c:icetek-vc5509-edulablab0503-fftfft.pjt 。3編譯并下載程序。4打開觀察窗口選擇菜單 view-graph-time/frequency5清除顯示在以上打開的窗口中單擊鼠標(biāo)右鍵，選擇彈出式菜單中“clear di

5、splay”功能。6設(shè)置斷點(diǎn)在程序 fft.c 中有注釋“ break point”的語句上設(shè)置軟件斷點(diǎn)。7運(yùn)行并觀察結(jié)果。選擇“ debug”菜單的“ animate”項(xiàng)，或按 f12 鍵運(yùn)行程序。觀察“ test wave ”窗口中時(shí)域圖形；在“test wave”窗口中點(diǎn)擊右鍵，選擇屬性，更改圖形顯示為fft。觀察頻域圖形。觀察“ fft”窗口中的由 ccs 計(jì)算出的正弦波的 fft。8退出 ccs。9. 實(shí)驗(yàn)結(jié)果10.源代碼（ c語言）#include myapp.h #include icetek-vc5509-edu.h #include scancode.h #include #

6、define pi 3.1415926 #define samplenumber 128 void initforfft(); void makewave(); int inputsamplenumber,datasamplenumber; float fwaversamplenumber,fwaveisamplenumber,wsamplenumber; float sin_tabsamplenumber,cos_tabsamplenumber; main() int i; initforfft(); makewave(); for ( i=0;isamplenumber;i+ ) fwav

7、eri=inputi; fwaveii=0.0f; wi=0.0f; fft(fwaver,fwavei); for ( i=0;isamplenumber;i+ ) datai=wi; while ( 1 ); / break point void 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; for ( i=0;isamplenumber;i+ ) x0=x1=x2=x3=x4=x5=x6=0; x0=i

8、&0 x01; x1=(i/2)&0 x01; x2=(i/4)&0 x01; x3=(i/8)&0 x01;x4=(i/16)&0 x01; x5=(i/32)&0 x01; x6=(i/64)&0 x01; 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; i-; /* b= 2(l-1) */ for ( j=0;j0 )

9、 /* 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; dataik+b=ti+temp*sin_tabp-dataik

10、+b*cos_tabp; /* end for (3) */ /* end for (2) */ /* end for (1) */ for ( i=0;isamplenumber/2;i+ ) wi=sqrt(datari*datari+dataii*dataii); /* end fft */ 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

11、 ( i=0;isamplenumber;i+ ) inputi=sin(pi*2*i/samplenumber*3)*1024; （二）第二部分1.程序參數(shù)說明extern void initc5402(void) extern void openmcbsp(void) extern void closemcbsp(void) extern void readad50(void) extern void writead50(void) void kfft(pr,pi,n,k,fr,fi,l,il) ：基 2 快速傅立葉變換子程序， n 為變換點(diǎn)數(shù)， 應(yīng)滿足 2 的整數(shù)次冪，k 為冪次（正整數(shù)

12、） ；數(shù)組 x ：輸入信號(hào)數(shù)組，數(shù)據(jù)存放于地址為3000h307fh 存儲(chǔ) 器中，轉(zhuǎn)為浮點(diǎn)型后，生成 x 數(shù)組，長(zhǎng)度 128；數(shù)組 mo：fft 變換輸出數(shù)組，長(zhǎng)度128，浮點(diǎn)型，整型后，寫入存儲(chǔ)器中。2.子程序流程圖：初始化輸入數(shù)組排序計(jì)算第一層中間值計(jì)算層數(shù)計(jì)算對(duì)應(yīng)層步長(zhǎng)計(jì)算計(jì)算各層中間結(jié)果計(jì)算層數(shù) =0？計(jì)算結(jié)果輸出ny3.啟動(dòng) ccs 2.0，用 project/open 打開“ expfft01.pjt ”工程文件雙擊“ expfft01.pjt” 及“source”可查看各源程序；加載“expfft01.out” ；4.在主程序中， k+處設(shè)置斷點(diǎn)5.單擊“ run”運(yùn)行程序或按

13、f5 運(yùn)行程序；程序?qū)⑦\(yùn)行至斷點(diǎn)處停止；6.用 view / graph / time/frequency打開一個(gè)圖形觀察窗口；7.單擊“ animate ”運(yùn)行程序。 或按 f10運(yùn)行，調(diào)整觀察窗口并觀察變換結(jié)果。五.實(shí)驗(yàn)總結(jié)這次 dsp技術(shù)的實(shí)驗(yàn)是在我們學(xué)習(xí)了數(shù)字信號(hào)處理、c語言程序設(shè)計(jì)的先修課程和 dsp技術(shù)，以及熟悉了 ccs軟件之后完成的。 實(shí)驗(yàn)一我們首先熟悉要用的各種軟硬件環(huán)境，接下來的實(shí)驗(yàn)二和三我們完成了有限沖擊響應(yīng)濾波器（fir）算法實(shí)驗(yàn)和快速傅里葉變換（fft ）算法實(shí)驗(yàn)。這次實(shí)驗(yàn)我個(gè)人認(rèn)為在以下幾個(gè)方面收獲最大：1.首先是實(shí)驗(yàn)前對(duì)自己過去幾個(gè)學(xué)期已學(xué)理論知識(shí)的鞏固加深、綜合應(yīng)用以及對(duì)實(shí)驗(yàn)相關(guān)資料的收集能力的提高。2.實(shí)驗(yàn)中各個(gè)部分的要求要理解掌握，認(rèn)真對(duì)待。實(shí)驗(yàn)鍛煉了我們認(rèn)真的態(tài)度和嚴(yán)謹(jǐn)?shù)木瘛?.當(dāng)遇到問題和困難的時(shí)候， 一定要保持冷靜， 慢