DSP課程設計報告

1、DSP原理及應用課程設計J I A N G S U U N I V E R S I T YDSP原理及應用課程設計報告FFT的DSP實現(xiàn)姓 名： 專業(yè)班級： 通信1002 學 號： 31006010 指導老師： 宋雪樺 設計日期： 2013.05.062013.05.15 一、設計目的1、加深對DFT算法原理和基本性質的理解；2、了解并學習使用FFT算法，以及其在TMS320C54X上的運用；3、學習DSP中FFT的設計和編程思想；4、練習使用CCS的探針和圖形工具來觀察器觀察波形和頻譜情況。二、設計內容用C語言及匯編語言進行編程，實現(xiàn)FFT運算，對于C語言，實現(xiàn)8點和16點的FFT運算，對于

2、匯編語言，需調試出8點的FFT運算結果。三、設計原理 快速傅里葉變換（FFT）是一種高效實現(xiàn)離散傅里葉變換（DFT）的快速算法，是數(shù)字信號處理中最為重要的工具之一，它在聲學，語音，電信和信號處理等領域有著廣泛的應用。1、離散傅里葉變換DFT對于長度為N的有限長序列x(n)，它的離散傅里葉變換（DFT）為 （1） 式中， ，稱為旋轉因子或蝶形因子。 從DFT的定義可以看出，在x(n)為復數(shù)序列的情況下，對某個k值，直接按（1）式計算X(k) 只需要N次復數(shù)乘法和（N-1）次復數(shù)加法。因此，對所有N個k值，共需要N2次復數(shù)乘法和N(N-1)次復數(shù)加法。對于一些相當大有N值（如1024點）來說，直接

3、計算它的DFT所需要的計算量是很大的，因此DFT運算的應用受到了很大的限制。2、快速傅里葉變換FFT旋轉因子WN 有如下的特性:對稱性： 周期性：利用這些特性，既可以使DFT中有些項合并，減少了乘法積項，又可以將長序列的DFT分解成幾個短序列的DFT。FFT就是利用了旋轉因子的對稱性和周期性來減少運算量的。FFT的算法是將長序列的DFT分解成短序列的DFT。例如：N為偶數(shù)時，先將N點的DFT分解為兩個N/2點的DFT，使復數(shù)乘法減少一半：再將每個N/2點的DFT分解成N/4點的DFT，使復數(shù)乘又減少一半，繼續(xù)進行分解可以大大減少計算量。最小變換的點數(shù)稱為基數(shù)，對于基數(shù)為2的FFT算法，它的最小

4、變換是2點DFT。一般而言，F(xiàn)FT算法分為按時間抽取的FFT（DIT FFT）和按頻率抽取的FFT（DIF FFT）兩大類。DIF FFT算法是在時域內將每一級輸入序列依次按奇/偶分成2個短序列進行計算，而DIF FFT算法是在頻域內將每一級輸入序列依次奇/偶分成2個短序列進行計算。兩者的區(qū)別是旋轉因子出現(xiàn)的位置不同，但算法是一樣的。在DIF FFT算法中，旋轉因子出現(xiàn)在輸入端，而在DIF FFT算法中它出現(xiàn)在輸入端。假定序列x(n)的點數(shù)N是2的冪，按照DIF FFT算法可將其分為偶序列和奇序列，記偶序列為 ，奇序列為，則x(n)的FFT表示為 由于 ，則（3）式可表示為 式中， 和分別為和

5、的N/2的DFT。 由于對稱性，則。因此，N點可分為兩部分：前半部分： （4）后半部分： （5）從式（4）和式（5）可以看出，只要求出0N/2-1區(qū)間和的值，就可求出0N-1區(qū)間的N點值。以同樣的方式進行抽取，可以求得N/4點的DFT，重復抽取過程，就可以使N點的DFT用上組2點的 DFT來計算，這樣就可以大減少運算量。在基數(shù)為2的FFT中，設N=2M，共有M級運算，每級有N/2個2點FFT蝶形運算，因此，N點FFT總共有MN/2個蝶形運算。蝶形運算如圖1所示。圖1 蝶形運算設蝶形輸入為和，輸出為和，則有 （6） （7）在基數(shù)為2的FFT中，設N=2M，共有M級運算，每級有N/2個2點FFT蝶

6、形運算，因此，N點FFT總共有個蝶形運算。例如：基數(shù)為2的FFT，當N=8時，共需要3級，12個基2 DIT FFT的蝶形運算。其信號流程如圖2所示。 圖2 8點基2 DIF FFT蝶形運算從圖2可以看出，輸入是經(jīng)過比特反轉的倒位序列，稱為位碼倒置，其排列順序為。輸出是按自然順序排列，其順序為。3、FFT運算的實現(xiàn)（1）實現(xiàn)輸入數(shù)據(jù)的比特反轉輸入數(shù)據(jù)的比特反轉實際上就是將輸入數(shù)據(jù)進行碼位倒置，以便在整個運算后輸出序列是一個自然序列。在用匯編指令進行碼位倒置時，使用位碼倒置尋址可以大大提高程序執(zhí)行速度和使用存儲器的效率。在這種尋址方式下，AR0存放的整數(shù)N的FFT點的一半，一個輔助寄存器指向一個

7、數(shù)據(jù)存放單元。當使用位碼倒置尋址將AR0加到輔助寄存器時，地址將以位碼倒置的方式產(chǎn)生。（2）實現(xiàn)N點復數(shù)FFTN點復數(shù)FFT算法的實現(xiàn)可分為三個功能塊，即第一級蝶形運算、第二級蝶形運算、第三級至log2N級蝶形運算。隊以任何一個2的整數(shù)冪N=2M，總可以通過M次分解后最后成為二點的DFT運算。通過這樣的M次分解，可以構成M級迭代計算，每級由N/2個蝶形運算完成。（4）輸出FFT結果FFT算法的程序流程圖如下圖所示。開始設定輸入序列求出蝶形運算級數(shù)m=3循環(huán)mm=1到3級蝶形運算求該級旋轉因子下標Nm循環(huán)該級1到2mm-1組蝶形運算循環(huán)該組1到23-mm個蝶形運算計算一個蝶形運算單元序列倒序后繪

8、圖結束YYYNNN圖3 FFT運算的程序流程圖四、基于C語言的FFT算法1、源程序FFT.c#include "myapp.h"#include "ICETEK-VC5509-EDU.h"#include "scancode.h"#include <math.h>#define PI 3.1415926#define SAMPLENUMBER 16void MakeWave();int INPUTSAMPLENUMBER;struct compxfloat real,imag; struct compx EE(struct

9、 compx,struct compx); struct compx xinSAMPLENUMBER;struct compx fWaveSAMPLENUMBER;float ySAMPLENUMBER,dataSAMPLENUMBER;struct compx EE(struct compx b1,struct compx b2) struct compx b3; b3.real=b1.real*b2.real-b1.imag*b2.imag; b3.imag=b1.real*b2.imag+b1.imag*b2.real; return(b3);main()int i;MakeWave()

10、;for ( i=0;i<SAMPLENUMBER;i+ )fWavei.real=INPUTi;fWavei.imag=0.0f;yi=0.0f;FFT(fWave);for ( i=0;i<SAMPLENUMBER;i+ )datai=yi;while ( 1 );/ break pointvoid FFT(struct compx *xin) int f,m,nv2,nm1,i,k,j=0,l;struct compx v,w,t; nv2=SAMPLENUMBER/2; f=SAMPLENUMBER;for(m=1;(f=f/2)!=1;m+); nm1=SAMPLENUM

11、BER-1;for(i=0;i<nm1;i+) if(i<j) t=xinj; xinj=xini; xini=t; k=nv2; while(k<=j) j=j-k; k=k/2; j=j+k; int le,lei,ip; for(l=1;l<=m;l+) le=2<<(l-1); lei=le/2; v.real=1.0;v.imag =0.0; w.real =cos(PI/lei);w.imag =-sin(PI/lei); for(j=0;j<=lei-1;j+) for(i=j;i<=SAMPLENUMBER;i=i+le) ip=

12、i+lei; t=EE(xinip,v); xinip.real=xini.real-t.real; xinip.imag =xini.imag-t.imag; xini.real=xini.real+t.real; xini.imag=xini.imag+t.imag; v=EE(v,w); for ( i=0;i<SAMPLENUMBER;i+ ) yi=sqrt(xini.real*xini.real+xini.imag*xini.imag); void MakeWave()int i;for ( i=0;i<SAMPLENUMBER;i+ )INPUTi=i+1;2、鏈接命

13、令文件ICETEK-VC5509-A.cmd-w-stack 500-sysstack 500-l rts55x.libMEMORY DARAM:o=0x100,l=0x7f00 VECT : o=0x8000,l=0x100 DARAM2: o=0x8100,l=0x7f00 SARAM: o=0x10000,l=0x30000 SDRAM:o=0x40000,l=0x3e0000SECTIONS .text: > DARAM .vectors: > VECT .trcinit: > DARAM .gblinit: > DARAM frt: > DARAM .c

14、init: > DARAM .pinit: > DARAM .sysinit: > DARAM .bss: > DARAM2 .far: > DARAM2 .const: > DARAM2 .switch: > DARAM2 .sysmem: > DARAM2 .cio: > DARAM2 .MEM$obj: > DARAM2 .sysheap: > DARAM2 .sysstack > DARAM2 .stack: > DARAM2 3、FFT程序的使用方法（1）根據(jù)N值，修改FFT.c中的中的常數(shù)，如N=8，將#

15、define SAMPLENUMBER 16語句中的“16”修改為8。（2）編譯、匯編、鏈接，得到.out文件，加載。（3）將data加入觀察窗，可看到FFT運算輸出結果。4、運行結果8點的FFT運算，且輸入為1、2、3、8時，運算結果如圖4所示，16點的FFT運算，且輸入為1、2、3、16時，運算結果如圖5所示。圖4 8點FFT運算結果圖5 16點FFT運算結果五、基于匯編語言的FFT算法1、匯編源程序fft.asm .title "fft.asm" .mmregs .include "coeff.inc" .include "in.inc&

16、quot; .def startsine: .usect "sine",512sine1: .usect "sine1",512cosine: .usect "cosine",512cosine1: .usect "cosine1",512fft_data: .usect "fft_data",1024fft_out: .usect "fft_out",512 STACK .usect "STACK",10K_DATA_IDX_1 .set 2K_DATA

17、_IDX_2 .set 4K_DATA_IDX_3 .set 8K_TWID_TBL_SIZE .set 512K_TWID_IDX_3 .set 128K_FLY_COUNT_3 .set 4K_FFT_SIZE .set 8 K_LOGN .set 3 PA0 .set 0 .bss d_twid_idx,1 .bss d_data_idx,1 .bss d_grps_cnt,1 .sect "fft_prg"*位碼倒置程序* .asg AR2,REORDERED .asg AR3,ORIGINAL_INPUT .asg AR7,DATA_PROC_BUF start:

18、 SSBX FRCT STM #STACK+10,SP STM #sine,AR1 RPT #K_TWID_TBL_SIZE-1 MVPD #sine1,*AR1+ STM cosine,AR1 RPT #K_TWID_TBL_SIZE-1 MVPD #cosine1,*AR1+ STM #d_input,ORIGINAL_INPUT STM #fft_data,DATA_PROC_BUF MVMM DATA_PROC_BUF,REORDERED STM #K_FFT_SIZE-1,BRC RPTBD bit_rev_end-1 STM #K_FFT_SIZE,AR0 MVDD *ORIGIN

19、AL_INPUT+,*REORDERED+ MVDD *ORIGINAL_INPUT-,*REORDERED+ MAR *ORIGINAL_INPUT+0B bit_rev_end:*FFT CODE* .asg AR1,GROUP_COUNTER .asg AR2,PX .asg AR3,QX .asg AR4,WR .asg AR5,WI .asg AR6,BUTTERFLY_COUNTER .asg AR7,STAGE_COUNTER *第一級蝶形運算stage1* STM #0,BK LD #-1,ASM STM #fft_data,PX STM #fft_data+K_DATA_ID

20、X_1,QX STM K_FFT_SIZE/2-1,BRC LD *PX,16,A RPTBD stage1end-1 STM #K_DATA_IDX_1+1,AR0 SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+ ST B,*QX+ |LD *PX,A SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+0% ST B,*QX+0% 2 |LD *PX,A stage1end:*第二級蝶形運算stage2* STM #fft_data,PX STM #fft_data+K_DATA_IDX_2,QX STM #K_FFT_

21、SIZE/4-1,BRC LD *PX,16,A RPTBD stage2end-1 STM #K_DATA_IDX_2+1,AR0;1st butterfly SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+ ST B,*QX+ |LD *PX,A SUB *QX,16,A,B ADD *QX,16,A STH A,ASM,*PX+ STH B,ASM,*QX+ ;2nd butterfly MAR *QX+ ADD *PX,*QX,A SUB *PX,*QX-,B STH A,ASM,*PX+ SUB *PX,*QX,A ST B,*QX |LD *QX

22、+,B ST A,*PX |ADD *PX+0%,A ST A,*QX+0% |LD *PX,A stage2end:*第三級至最后一級蝶形運算* STM #K_TWID_TBL_SIZE,BK ST #K_TWID_IDX_3,d_twid_idx STM #K_TWID_IDX_3,AR0 STM #cosine,WR STM #sine,WI STM #K_LOGN-2-1,STAGE_COUNTER ST #K_FFT_SIZE/8-1,d_grps_cnt STM #K_FLY_COUNT_3-1,BUTTERFLY_COUNTER ST #K_DATA_IDX_3,d_data_i

23、dx stage: STM #fft_data,PX LD d_data_idx,A ADD *(PX),A STLM A,QX MVDK d_grps_cnt,GROUP_COUNTER group: MVMD BUTTERFLY_COUNTER,BRC RPTBD butterflyend-1 LD *WR,T MPY *QX+,A MAC *WI+0%,*QX-,A ADD *PX,16,A,B ST B,*PX |SUB *PX+,B ST B,*QX |MPY *QX+,A MAS *QX,*WR+0%,A ADD *PX,16,A,B ST B,*QX+ |SUB *PX,B LD

24、 *WR,T ST B,*PX+ |MPY *QX+,A butterflyend: PSHM AR0 MVDK d_data_idx,AR0 MAR *PX+0 MAR *QX+0 BANZD group,*GROUP_COUNTER- POPM AR0 MAR *QX- LD d_data_idx,A SUB #1,A,B STLM B,BUTTERFLY_COUNTER STL A,1,d_data_idx LD d_grps_cnt,A STL A,ASM,d_grps_cnt LD d_twid_idx,A STL A,ASM,d_twid_idx BANZD stage,*STAGE_COUNTER- MVDK d_twid_idx,AR0 fft_end:*計算功率譜 STM #fft_data,AR2 ; STM #fft_data,AR3 STM #fft_out,AR4 STM #K_FFT_SIZE*2-1,BRC RPTB power_end-1 SQUR *AR2+,A SQURA *AR2+,A STH A,*AR4+power_end