快速傅里葉變換FFT的DSP實(shí)現(xiàn)

1、目錄1、 前言2、 設(shè)計(jì)題目3、 設(shè)計(jì)要求3.1 設(shè)計(jì)目的3.2 設(shè)計(jì)要求4、 設(shè)計(jì)內(nèi)容5、 設(shè)計(jì)原理5.2 離散傅里葉變換DFT5.3 快速傅里葉變換FFT6、 總體方案設(shè)計(jì)6.1 設(shè)計(jì)有關(guān)程序流程圖6.2 在CCSM境下加載、調(diào)試源程序7、 主要參數(shù)8、 實(shí)驗(yàn)結(jié)果分析9、 設(shè)計(jì)總結(jié)一、前言隨著數(shù)字電子技術(shù)的發(fā)展，數(shù)字信號(hào)處理的理論和技術(shù)廣泛的應(yīng)用于通訊、語音處理、計(jì)算機(jī)和多媒體等領(lǐng)域?？焖俑道锶~變換（ FFT）使離散傅里葉變換的時(shí)間縮短了幾個(gè)數(shù)量級(jí)。在數(shù)字信號(hào)處理領(lǐng)域被廣泛的應(yīng)用。FFT已經(jīng)成為現(xiàn)代化信號(hào)處理的重要手段之一。本次課程設(shè)計(jì)主要運(yùn)用 CCSS一工具。CCS（Code Compo

2、ser Studio） 是一種針對(duì)TM320系列DSP的集成開發(fā)環(huán)境，在 Windows操作系統(tǒng) 下，采用圖形接口界面，提供環(huán)境配置、源文件編輯、程序調(diào)試、跟蹤和分析等工具，可以幫助用戶在一個(gè)軟件環(huán)境下完成編輯、編譯、 鏈接、調(diào)試和數(shù)據(jù)分析等工作。CCS有兩種工作模式，即軟件仿真器和硬件在線編程。軟件仿真 器工作模式可以脫離 DSP芯片，在PC上模擬DSP的指令集和工作機(jī) 制，主要用于前期算法實(shí)現(xiàn)和調(diào)試。硬件在線編程可以實(shí)時(shí)運(yùn)行在DSP芯片上，與硬件開發(fā)板相結(jié)合進(jìn)行在線編程和調(diào)試應(yīng)用程序。2 、 設(shè)計(jì)題目快速傅里葉變換（FFT的DSP實(shí)現(xiàn)3 、 設(shè)計(jì)要求3.1 設(shè)計(jì)目的加深對(duì)DFT算法原理和基

3、本性質(zhì)的理解； 熟悉FFT的算法原理和FFT子程序的算法流程和應(yīng)用；學(xué)習(xí)用FFT對(duì)連續(xù)信號(hào)和時(shí)域信號(hào)進(jìn)行頻譜分析的方法；學(xué)習(xí)DSP中FFT的設(shè)計(jì)和編程思想；學(xué)習(xí)使用CCS勺波形觀察器觀察波形和頻譜情況；3.2 基本要求研究FFT原理以及利用DSP實(shí)現(xiàn)的方法；編寫FFT®序；調(diào)試程序，觀察結(jié)果。四、設(shè)計(jì)內(nèi)容用DSP匯編語言及C語言進(jìn)行編程；實(shí)現(xiàn)FFT運(yùn)算、對(duì)輸入信號(hào)進(jìn)行頻譜分析。五、設(shè)計(jì)原理快速傅里葉變換FFT快速傅里葉變換(FFTT是一種高效實(shí)現(xiàn)離散傅里葉變換(DFT 的快速算法，是數(shù)字信號(hào)處理中最為重要的工具之一，它在聲學(xué)，語 音，電信和信號(hào)處理等領(lǐng)域有著廣泛的應(yīng)用。5.1. 離散

4、傅里葉變換DFT對(duì)于長度為N的有限長序列x(n),它的離散傅里葉變換(DFT為 n 1X (k) -，x(n)WNnk ,k = 0,1, N -1T(1)j2 二/ N式中，WN 'e,稱為旋轉(zhuǎn)因子或蝶形因子。從DFT的定義可以看出，在x(n)為復(fù)數(shù)序列的情況下，對(duì)某 個(gè)k值，直接按(1)式計(jì)算X(k)只需要N次復(fù)數(shù)乘法和(N-1)次 復(fù)數(shù)加法。因此，對(duì)所有 N個(gè)k值，共需要N2次復(fù)數(shù)乘法和N(N-1) 次復(fù)數(shù)加法。對(duì)于一些相當(dāng)大有 N值(如1024點(diǎn))來說，直接計(jì)算 它的DFT所需要的計(jì)算量是很大的，因此DFT運(yùn)算的應(yīng)用受到了很大的限制5.2. 快速傅里葉變換FFT旋轉(zhuǎn)因子WN有如

5、下的特性。kk N /2對(duì)稱性：WN =WNkk N周期性：Wn = WN利用這些特性，既可以使 DFT中有些項(xiàng)合并，減少了乘法積項(xiàng),又可以將長序列的DFT分解成幾個(gè)短序列的DFT FFT就是利用了旋轉(zhuǎn)因子的對(duì)稱性和周期性來減少運(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ù)， 對(duì)于基數(shù)為2的FFT算法，它的最小變換是 2點(diǎn)DFT一般而言，F(xiàn)FT算法分為按時(shí)間抽取的 FFT

6、 (DIT FFT)和按 頻率抽取的F FT ( DIF FFT兩大類。D IF FFT算法是在時(shí)域內(nèi)將每 一級(jí)輸入序列依次按奇/偶分成2個(gè)短序列進(jìn)行計(jì)算。而DIF FFT算法是在頻域內(nèi)將每一級(jí)輸入序列依次奇/偶分成2個(gè)短序列進(jìn)行計(jì) 算。兩者的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同，得算法是一樣的。在kDIF FFT算法中，旋轉(zhuǎn)因子Wn出現(xiàn)在輸入端，而在 DIF FFT算法中它出現(xiàn)在輸入端。假定序列x(n)的點(diǎn)數(shù)N是2的哥，按照DIF FFTT法可將其分為偶序列和奇序列偶序列:x(0), x,x(4), x(N-2),即 X1x(2r), r = 0,1, N /2 - 1奇序列:x(1), x(3),

7、 x(5), x(N-1),即 X2x(2r 1), r=0,1, N /2 - 1則x(n)的DFT表不為N J nkX (k) = v x(n)WNn /N _1x(n)Wn 0nkNn為偶數(shù)n為奇數(shù)N /2 J二、x(2r)Wr zz0N /2 J 2rk-X1 (r )Wnr =0N /22rkn '、 X(2r 1)Wr MN/2kWn(2 r 1)kN2 rkX2 (r )W nr =0(2)2由于Wn 可表不為|e-j(2 7：/N ) 2|-i2- /(N /2)e- W N /2，則(3)式X(k)N/2-1一rk=" X1 ( r )W N / 2r3N/

8、2-1k _rkWn 、X2")Wn/2r日k=X1(k) Wn X2(k)k = 0,1, N /2 1式中，X1(k)和X2(k)分別為"(n)和X2(n)的N/2的DFT由于對(duì)稱性，k : ：；N / 2KkW N=-Wn，貝 ljX(k + N /2) = X 1(k) -Wn X 2(k)因此，N點(diǎn)X (k)可分為兩部分:k前半部分：X(k) =X1(k) WNX2(k)k =0,1, N /2 -1(4)k后半部分.X (k N /2) = X1(k) -Wn X2(k)k =0,1，N /2 -1從式(4)和式(5)可以看出，只要求出0N/2-1區(qū)間X1(k)

9、和X2(k)的值，就可求出0N-1區(qū)間X (k)的N點(diǎn)值以同樣的方式進(jìn)行抽取，可以求得N/4點(diǎn)的DFT,重復(fù)抽取過程，就可以使N點(diǎn)的DFT用上組2點(diǎn)的DFT來計(jì)算，這樣就可以大減少 運(yùn)算量基2 DIF FFT的蝶形運(yùn)算如圖(a)所示。設(shè)蝶形輸入為xm(p)和Xmdq),輸出為Xm(P m，則有(6)(7)Xm ( P) = Xm i( p) Xm“小kXm(q) =Xm(P) Xm(q)WN在基數(shù)為2的FFT中，設(shè)N=2M,共有M級(jí)運(yùn)算，每級(jí)有N/2個(gè)2點(diǎn)FFT蝶形運(yùn)算，因此，N點(diǎn)FFT總共有(N /2)10g 2 N個(gè)蝶形運(yùn)算圖(a)基2 DIF FFT的蝶形運(yùn)算Xm( P)Xm (q)例如

10、：基數(shù)為2的FFT當(dāng)N=8時(shí)，共需要3級(jí)，12個(gè)基2 DIT FFT的蝶形運(yùn)算。其信號(hào)流程如圖(b)所示圖(b) 8 點(diǎn)基2 DIF FFT蝶形運(yùn)算從圖(b)可以看出，輸入是經(jīng)過比特反轉(zhuǎn)的倒位序列，稱為位碼倒置，其排列順序?yàn)閤,x(4)，x,x(6)，x,x,x(3)，x。輸出是按自然順 序排列，其順序?yàn)閤,x,，x(6)，x。六、總體方案設(shè)計(jì)6.1 設(shè)計(jì)程序流程圖6.2 在CCSM境下加載、調(diào)試源程序(1)起動(dòng)CCS在CCS中建立一個(gè)工程文件 projectnewFFT,往工程文件里添加程序filenewsourcefile.建立C源文件和一個(gè)命令文件, 并將這兩個(gè)文件添加到工程，再編譯并裝

11、載程序:閱讀Dsp原理及應(yīng)用中fft用dsp實(shí)現(xiàn)的有關(guān)程序。雙擊S號(hào)士即CCS 2 c cooa) 快捷方式,啟動(dòng)CCS的仿真平臺(tái)的配著選項(xiàng)。選擇C5510 Simulator。Add 力口到J my system 按下 save* J* rMfincev SUQ S*lnp(2)啟動(dòng)c5510后打開文件FFT.pjt將編寫好的源程序，和命令文件加載到文件FFT.pjtSource.(3)按下projectbuild調(diào)試程序，看其中是否有錯(cuò)誤一一一一一一一一一一一一一一一一一一一一一一一一一一一一 FFT.pjt Debug Bui Id Complete,0 Errors, 0 Warnin

12、g5.0 Remarks.(4)無錯(cuò)后，Debugrun運(yùn)行FFT.out程序。FFT - pj X - Dehufj(5)通過graph property dialog窗口，改變N點(diǎn)的值,得到不同的結(jié) 果。七.主要參數(shù)進(jìn)行N點(diǎn)FFT運(yùn)算，分別實(shí)現(xiàn)N=256,N=512得到不同的功率譜圖六.源程序：Cmd源文件代碼:-f 0-w-stack 500-sysstack 500-l rts55.libMEMORYDARAM: o=0x100, l=0x7f00VECT:o=0x8000, l=0x100DARAM2:o=0x8100,l=0x7f00SARAM: o=0x10000,l=0x300

13、00SDRAM:o=0x40000,l=0x3e0000SECTIONS.text: >DARAM.vectors: >VECT.trcinit:>DARAM.gblinit:>DARAM.frt:>DARAM.cinit:>DARAM.pinit:>DARAM.sysinit:>DARAM2.far:>DARAM2.const:>DARAM2.switch:>DARAM2.sysmem:>DARAM2 .cio:>DARAM2.MEM$obj:>DARAM2.sysheap:>DARAM2.syssta

14、ck:>DARAM2.stack:>DARAM2.input:>DARAM2.fftcode:>DARAM2C 文件源碼：#include "math.h"#define sample_1 256#define signal_1_f 60#define signal_2_f 200#define signal_sample_f 512#define pi 3.1415926int inputsample_1;float fwaversample_1,fwaveisample_1,wsample_1;float sin_tabsample_1;floa

15、t cos_tabsample_1;void init_fft_tab();void input_data();void fft(float datarsample_1,float dataisample_1);void main()int i;init_fft_tab();input_data();f or (i=0;i<sample_1;i+)fwaveri=inputi;fwaveii=0.0f;wi=0.0f;fft(fwaver,fwavei);while(1);void init_fft_tab()float wt1;float wt2;int i;for (i=0;i<

16、;sample_1;i+)wt1=2*pi*i*signal_1_f;wt1=wt1/signal_sample_f;wt2=2*pi*i*signal_2_f;wt2=wt2/signal_sample_f;inputi=(cos(wt1)+cos(wt2)/2*32768;void input_data()int i;for(i=0;i<sample_1;i+)sin_tabi=sin(2*pi*i/sample_1);cos_tabi=cos(2*pi*i/sample_1);void fft(float datarsample_1,float dataisample_1)int

17、x0,x1,x2,x3,x4,x5,x6,x7,xx;int i,j,k,b,p,L;float TR,TI,temp;for(i=0;i<sample_1;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;x7=(i/128)&0x01;xx=x0*128+x1*64+x2*32+x3*16+x4*8+x5*4+x6*2+x7;d

18、ataixx=datari;)for(i=0;i<sample_1;i+)(datari=dataii;dataii=0;)for(L=1;L<=8;L+)(b=1;i=L-1;while(i>0)(b=b*2;i-;)for(j=0;j<=b-1;j+)(p=1;i=8-L;while(i>0)p=p*2;i-;p=p*j;for(k=j;k<256;k=k+2*b)TR=datark;TI=dataik;temp=datark+b;datark=datark+datark+b*cos_tabp+dataik+b*sin_tabp;dataik=datai

19、k-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+b*cos_tabp;for(i=0;i<sample_1/2;i+) wi=sqrt(datari*datari+dataii*dataii);八、實(shí)驗(yàn)結(jié)果及分析作圖，得到輸入信號(hào)的功率圖譜2) FFT變換結(jié)果圖 < pqirilirifipiiiril|11|'|1| |119 li ail'lllll |i|ipqipifip|l flipi 'Tl F" «FW' FW 'P'' FW'FW Iff。與它J.7弋=7FH*TRfii邙白咱 中2,之十曰£-1 GetK；1 一更：何町0;-54F-;.I - aJ1 .配儀22川3)改變信號(hào)的頻率可以再做次實(shí)驗(yàn)B2 Graiph fr®pertjr Di&XagXDi splay Type1陽n口七TimeT j=ll .Graph TitleGraphical BiplaywPageDATAAcq-ui si ti oil IBuf £er Sizel