DSP課程設(shè)計(jì)報(bào)告

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

2、匯編語言，需調(diào)試出8點(diǎn)的FFT運(yùn)算結(jié)果。三、設(shè)計(jì)原理 快速傅里葉變換（FFT）是一種高效實(shí)現(xiàn)離散傅里葉變換（DFT）的快速算法，是數(shù)字信號(hào)處理中最為重要的工具之一，它在聲學(xué)，語音，電信和信號(hào)處理等領(lǐng)域有著廣泛的應(yīng)用。1、離散傅里葉變換DFT對(duì)于長度為N的有限長序列x(n)，它的離散傅里葉變換（DFT）為 （1） 式中， ，稱為旋轉(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)）來說，直接

3、計(jì)算它的DFT所需要的計(jì)算量是很大的，因此DFT運(yùn)算的應(yīng)用受到了很大的限制。2、快速傅里葉變換FFT旋轉(zhuǎn)因子WN 有如下的特性:對(duì)稱性： 周期性：利用這些特性，既可以使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算法，它的最小

4、變換是2點(diǎn)DFT。一般而言，F(xiàn)FT算法分為按時(shí)間抽取的FFT（DIT FFT）和按頻率抽取的FFT（DIF FFT）兩大類。DIF 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)的位置不同，但算法是一樣的。在DIF FFT算法中，旋轉(zhuǎn)因子出現(xiàn)在輸入端，而在DIF FFT算法中它出現(xiàn)在輸入端。假定序列x(n)的點(diǎn)數(shù)N是2的冪，按照DIF FFT算法可將其分為偶序列和奇序列，記偶序列為 ，奇序列為，則x(n)的FFT表示為 由于 ，則（3）式可表示為 式中， 和分別為和

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

6、形運(yùn)算，因此，N點(diǎn)FFT總共有個(gè)蝶形運(yùn)算。例如：基數(shù)為2的FFT，當(dāng)N=8時(shí)，共需要3級(jí)，12個(gè)基2 DIT FFT的蝶形運(yùn)算。其信號(hào)流程如圖2所示。 圖2 8點(diǎn)基2 DIF FFT蝶形運(yùn)算從圖2可以看出，輸入是經(jīng)過比特反轉(zhuǎn)的倒位序列，稱為位碼倒置，其排列順序?yàn)?。輸出是按自然順序排列，其順序?yàn)椤?、FFT運(yùn)算的實(shí)現(xiàn)（1）實(shí)現(xiàn)輸入數(shù)據(jù)的比特反轉(zhuǎn)輸入數(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è)

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

8、圖結(jié)束YYYNNN圖3 FFT運(yùn)算的程序流程圖四、基于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運(yùn)算輸出結(jié)果。4、運(yùn)行結(jié)果8點(diǎn)的FFT運(yùn)算，且輸入為1、2、3、8時(shí)，運(yùn)算結(jié)果如圖4所示，16點(diǎn)的FFT運(yùn)算，且輸入為1、2、3、16時(shí)，運(yùn)算結(jié)果如圖5所示。圖4 8點(diǎn)FFT運(yùn)算結(jié)果圖5 16點(diǎn)FFT運(yùn)算結(jié)果五、基于匯編語言的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 *第一級(jí)蝶形運(yùn)算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:*第二級(jí)蝶形運(yùn)算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:*第三級(jí)至最后一級(jí)蝶形運(yùn)算* 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:*計(jì)算功率譜 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