現(xiàn)代信號通信課程設計---dft的快速算法分析及fft的dsp實現(xiàn)

1、<p>　　《現(xiàn)代信號處理課程設計》</p><p><b>　　課程設計報告</b></p><p>　　設計題目 DFT的快速算法分析及FFT的DSP實現(xiàn)</p><p><b>　　目 錄</b></p><p>　　第1章 引言........................

2、......................2</p><p>　　第2章 FFT算法簡介.......................................2</p><p>　　2.1 離散傅里葉變換DFT...................................2</p><p>　　2.2 快速傅里葉變換FFT.............

3、......................2</p><p>　　第3章FFT算法的DSP實現(xiàn)...................................5</p><p>　　3.1 實現(xiàn)數(shù)據(jù)的比特反轉(zhuǎn)...................................5</p><p>　　3.2 實現(xiàn)N點復數(shù)FFT…...............

4、.....................5</p><p>　　3.3  輸出FFT結(jié)果........................................6</p><p>　　第4章 系統(tǒng)開發(fā)平臺與環(huán)境.................................6</p><p>　　4.1 CCS開發(fā)環(huán)境.............

5、.............................6</p><p>　　4.2SEED-DEC2812開發(fā)試驗箱..................6</p><p>　　第5章 軟件設計...........................................7</p><p>　　5.1流程圖.......................

6、........................7</p><p>　　5.2 源程序..............................................8 </p><p>　　第6章 系統(tǒng)仿真..........................................14 </p><p>　　第七章 總結(jié)…………………..……

7、………………………...………..19</p><p>　　參考文獻.................................................19</p><p><b>　　1.引言</b></p><p>　　傅里葉變換是將信號從時域變換到頻域的一種變換形式，是信號處理領域中一種重要的分析工具。離散傅里葉變換（DFT

8、）是連續(xù)傅里葉變換在離散系統(tǒng)中的表現(xiàn)形式。由于DFT的計算量很大，因此在很長一段時間內(nèi)使其應用受到很大的限制。</p><p>　　20世紀60年代由Cooley和Tukey提出了快速傅里葉變換（FFT）算法，它是快速計算DFT的一種高效方法，可以明顯地降低運算量，大大地提高DFT的運算速度，從而使DFT在實際中得到了廣泛的應用，已成為數(shù)字信號處理最為重要的工具之一。</p><p>　　

9、DSP芯片的出現(xiàn)使FFT的實現(xiàn)變得更加方便。由于多數(shù)的DSP芯片都能在單指令周期內(nèi)完成乘法—累加運算，而且還提供了專門的FFT指令（如實現(xiàn)FFT算法所必需的比特反轉(zhuǎn)等），使得FFT算法在DSP芯片上實現(xiàn)的速度更快。本節(jié)首先簡要介紹FFT算法的基本原理，然后介紹FFT算法的DSP實現(xiàn)。</p><p>　　2.FFT算法的簡介</p><p>　　快速傅里葉變換（FFT）是一種高效實現(xiàn)離散傅

10、里葉變換（DFT）的快速算法，是數(shù)字信號處理中最為重要的工具之一，它在聲學，語音，電信和信號處理等領域有著廣泛的應用。</p><p>　　2.1離散傅里葉變換DFT</p><p>　　對于長度為N的有限長序列x(n)，它的離散傅里葉變換（DFT）為</p><p><b>　　（1）</b></p><p>　　式中

11、， ，稱為旋轉(zhuǎn)因子或蝶形因子。</p><p>　　從DFT的定義可以看出，在x(n)為復數(shù)序列的情況下，對某個k值，直接按（1）式計算X(k) 只需要N次復數(shù)乘法和（N-1）次復數(shù)加法。因此，對所有N個k值，共需要N2次復數(shù)乘法和N(N-1)次復數(shù)加法。對于一些相當大有N值（如1024點）來說，直接計算它的DFT所需要的計算量是很大的，因此DFT運算的應用受到了很大的限制。</p><

12、;p>　　2.2快速傅里葉變換FFT</p><p>　　旋轉(zhuǎn)因子WN 有如下的特性。</p><p><b>　　對稱性： </b></p><p><b>　　周期性：</b></p><p>　　利用這些特性，既可以使DFT中有些項合并，減少了乘法積項，又可以將長序列的DFT分解成

13、幾個短序列的DFT。FFT就是利用了旋轉(zhuǎn)因子的對稱性和周期性來減少運算量的。</p><p>　　FFT的算法是將長序列的DFT分解成短序列的DFT。例如：N為偶數(shù)時，先將N點的DFT分解為兩個N/2點的DFT，使復數(shù)乘法減少一半：再將每個N/2點的DFT分解成N/4點的DFT，使復數(shù)乘又減少一半，繼續(xù)進行分解可以大大減少計算量。最小變換的點數(shù)稱為基數(shù)，對于基數(shù)為2的FFT算法，它的最小變換是2點DFT。<

14、/p><p>　　一般而言，F(xiàn)FT算法分為按時間抽取的FFT（DIT?。疲疲裕┖桶搭l率抽取的ＦＦＴ（DIF FFT）兩大類。ＤIF FFT算法是在時域內(nèi)將每一級輸入序列依次按奇／偶分成２個短序列進行計算。而DIF FFT算法是在頻域內(nèi)將每一級輸入序列依次奇／偶分成２個短序列進行計算。兩者的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同，得算法是一樣的。在DIF FFT算法中，旋轉(zhuǎn)因子　出現(xiàn)在輸入端，而在DIF FFT算法中它出現(xiàn)在輸入

15、端。</p><p>　　假定序列x(n)的點數(shù)N是2的冪，按照DIF FFT算法可將其分為偶序列和奇序列。</p><p><b>　　偶序列：</b></p><p><b>　　奇序列：</b></p><p>　　則x(n)的DFT表示為</p><p>　　由于 ，

16、則（3）式可表示為</p><p>　　式中， 和分別為和的N/2的DFT。</p><p><b>　　由于對稱性，</b></p><p>　　則。因此，N點可分為兩部分：</p><p>　　前半部分： （4）</p><p>　　后半部分： （5）</

17、p><p>　　從式（4）和式（5）可以看出，只要求出0~N/2-1區(qū)間和的值，就可求出0~N-1區(qū)間的N點值。</p><p>　　以同樣的方式進行抽取，可以求得N/4點的DFT，重復抽取過程，就可以使N點的DFT用上組2點的 DFT來計算，這樣就可以大減少運算量。</p><p>　　基2 DIF FFT的蝶形運算如圖(a)所示。設蝶形輸入為和，輸出為和，則有<

18、;/p><p><b>　?。?）</b></p><p><b>　　（7）</b></p><p>　　在基數(shù)為2的FFT中，設N=2M，共有M級運算，每級有N/2個2點FFT蝶形運算，因此，N點FFT總共有個蝶形運算。</p><p><b>　　-1</b></p&g

19、t;<p>　　圖(a) 基2 DIF FFT的蝶形運算</p><p>　　例如：基數(shù)為2的FFT，當N=8時，共需要3級，12個基2 DIT FFT的蝶形運算。其信號流程如圖(b)所示。</p><p>　　x(0) x(0)</p>

20、;<p><b>　　WN0</b></p><p>　　x(4) x(1)</p><p>　　-1 </p><p><b>　　WN0</b></p>

21、;<p>　　x(2) x(2)</p><p><b>　　-1</b></p><p>　　WN0 WN2</p><p>　　x(6)

22、 x(3)</p><p>　　-1 -1</p><p><b>　　WN0</b></p><p>　　x(1)

23、 x(4)</p><p><b>　　-1</b></p><p>　　WN0 WN1</p><p>　　x(5)

24、 x(5)</p><p>　　-1 -1</p><p>　　WN0 WN2</p><p>　　x(3)

25、 x(6)</p><p>　　-1 -1</p><p>　　WN0 WN2 WN3</p><p>　　x(7)

26、 x(7)</p><p>　　-1 -1 -1</p><p>　　圖(b) 8點基2 DIF FFT蝶形運算</p><p>　　從圖(b)可以看出，輸入是經(jīng)過比特反轉(zhuǎn)的倒位序列，稱為位碼倒置，其排列順序為。輸出是按自然順序排列，其順序

27、為。</p><p>　　3.FFT算法的DSP實現(xiàn)</p><p>　　DSP芯片的出現(xiàn)使FFT的實現(xiàn)方法變得更為方便。由于大多數(shù)DSP芯片都具有在單指令周期內(nèi)完成乘法—累加操作，并且提供了專門的FFT指令，使得FFT算法在DSP芯片實現(xiàn)的速度更快。</p><p>　　FFT算法可以分為按時間抽取FFT (DIF FFT)和按頻率抽取FFT (DIF FFT)兩

28、大類，輸入也有實數(shù)和復數(shù)之分，一般情況下，都假定輸入序列為復數(shù)。下面以N復數(shù)點FFT算法為例，介紹用DSP芯片實現(xiàn)的方法。</p><p>　　實現(xiàn)FFT算法主要分為三步:</p><p>　　3.1實現(xiàn)輸入數(shù)據(jù)的比特反轉(zhuǎn)</p><p>　　輸入數(shù)據(jù)的比特反轉(zhuǎn)實際上就是將輸入數(shù)據(jù)進行位碼倒置,以便在整個運算后的輸出序列是一個自然序列。在用匯編指令進行位碼倒置是，使

29、用位碼倒置尋址可以大大擔高程序執(zhí)行速度和使用存儲器的效率。在這種尋址方式下，AR0存放的整數(shù)N是FFT點的一半，一個輔助寄存器指向一個數(shù)據(jù)存放的章元。當使用位碼倒置尋址將AR0加到輔助寄存器時，地址將以位碼倒置的方式產(chǎn)生。</p><p>　　3.2實現(xiàn)N點復數(shù)FFT</p><p>　　N點復數(shù)FFT算法的實現(xiàn)可分為三個功能塊，即第一級蝶形運算，第二蝶形運算，第三級至級蝶形運算。<

30、/p><p>　　對于任何一個2的整數(shù)冪N=2M，，總可以通過M次分解最后成為2點的DFT計算。通過這樣的M次分解，可構(gòu)成M（即）級迭代運算完成。</p><p>　　3.3輸出FFT結(jié)果</p><p>　　四.系統(tǒng)開發(fā)平臺與環(huán)境</p><p>　　4.1 CCS開發(fā)環(huán)境</p><p>　　CCS提供了配置、建立、調(diào)

31、試、跟蹤和分析程序的工具，它便于實時、嵌入式信號處理程序的編制和測試，它能夠加速開發(fā)進程，提高工作效率。</p><p>　　CCS提供了基本的代碼生成工具，它們具有一系列的調(diào)試、分析能力。CCS支持如下圖1.1所示的開發(fā)周期的所有階段。</p><p><b>　　圖 1.1</b></p><p>　　4.2 SEED-DEC2812開發(fā)實

32、驗箱</p><p>　　SEED-DECxxxx系列嵌入式DSP開發(fā)板本著模塊化、總線型、開放式、系列化的設計思想，采用統(tǒng)一的系統(tǒng)結(jié)構(gòu)、模塊結(jié)構(gòu)和機械結(jié)構(gòu)，以多種典型DSP處理器構(gòu)成具有標準總線和相同物理尺寸的高性能嵌入式DSP開發(fā)板。</p><p>　　SEED-DEC2812 嵌入式DSP開發(fā)板原理框圖如圖1.2所示：</p><p><b>　　

33、圖 1.2</b></p><p><b>　　五.軟件設計</b></p><p><b>　　5.1程序流程圖</b></p><p><b>　　5.2源程序</b></p><p>　　#include "DSP281x_Device.h"

34、; // DSP281x Headerfile Include File</p><p>　　#include "DSP281x_Examples.h" // DSP281x Examples Include File</p><p>　　#include "f2812a.h"</p><p>　　#include

35、"math.h"</p><p>　　#define PI 3.1415926</p><p>　　#define SAMPLENUMBER 128</p><p>　　#include "DSP281x_Device.h" // DSP281x Headerfile Include File</p>&

36、lt;p>　　#include "DSP281x_Examples.h" // DSP281x Examples Include File</p><p>　　// Prototype statements for functions found within this file.</p><p>　　interrupt void adc_isr(void);

37、</p><p>　　// Global variables used in this example:</p><p>　　void admain();</p><p>　　void InitForFFT();</p><p>　　void MakeWave();</p><p>　　//void FFT(float

38、 dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER]);</p><p>　　Uint16 LoopCount;</p><p>　　Uint16 ConversionCount;</p><p>　　Uint16 Voltage1[1024];</p><p>　　Uint16 Voltage2[10

39、24];</p><p>　　Uint16 nMixing[1024];</p><p>　　int INPUT[SAMPLENUMBER],DATA[SAMPLENUMBER];</p><p>　　float fWaveR[SAMPLENUMBER],fWaveI[SAMPLENUMBER],w[SAMPLENUMBER];</p><p&g

40、t;　　float sin_tab[SAMPLENUMBER],cos_tab[SAMPLENUMBER];</p><p>　　admain(void) </p><p><b>　　{</b></p><p>　　InitSysCtrl();//初始化cpu</p><p>　　DINT;//關(guān)中斷</p>

41、;<p>　　InitPieCtrl();//初始化pie寄存器</p><p>　　IER = 0x0000;//禁止所有的中斷</p><p>　　IFR = 0x0000;</p><p>　　InitPieVectTable();//初始化pie中斷向量表</p><p>　　// Interrupts that are

42、 used in this example are re-mapped to</p><p>　　// ISR functions found within this file. </p><p>　　EALLOW; // This is needed to write to EALLOW protected register</p><p>　　Pi

43、eVectTable.ADCINT = &adc_isr;</p><p>　　EDIS; // This is needed to disable write to EALLOW protected registers</p><p>　　AdcRegs.ADCTRL1.bit.RESET = 1;// Reset the ADC module</p>&

44、lt;p>　　asm(" RPT #10 || NOP");// Must wait 12-cycles (worst-case) </p><p>　　AdcRegs.ADCTRL3.all = 0x00C8;// first power-up ref and bandgap circuits</p><p>　　AdcRegs.ADCTRL3.b

45、it.ADCBGRFDN = 0x3;// Power up bandgap/reference circuitry</p><p>　　AdcRegs.ADCTRL3.bit.ADCPWDN = 1;// Power up rest of ADC</p><p>　　// Enable ADCINT in PIE</p><p>　　PieCtrlRegs.

46、PIEIER1.bit.INTx6 = 1;</p><p>　　IER |= M_INT1; // Enable CPU Interrupt 1</p><p>　　EINT; // Enable Global interrupt INTM</p><p>　　ERTM; // Enable Global realtime in

47、terrupt DBGM</p><p>　　LoopCount = 0;</p><p>　　ConversionCount = 0;</p><p>　　// Configure ADC</p><p>　　AdcRegs.ADCMAXCONV.all = 0x0001; // Setup 2 conv's on SE

48、Q1</p><p>　　AdcRegs.ADCCHSELSEQ1.bit.CONV00 = 0x0; // Setup ADCINA3 as 1st SEQ1 conv.</p><p>　　AdcRegs.ADCCHSELSEQ1.bit.CONV01 = 0x1; // Setup ADCINA2 as 2nd SEQ1 conv.</p><p>　　Adc

49、Regs.ADCTRL2.bit.EVA_SOC_SEQ1 = 1; // Enable EVASOC to start SEQ1</p><p>　　AdcRegs.ADCTRL2.bit.INT_ENA_SEQ1 = 1; // Enable SEQ1 interrupt (every EOS)</p><p>　　// Configure EVA</p><p

50、>　　// Assumes EVA Clock is already enabled in InitSysCtrl();</p><p>　　EvaRegs.T1CMPR = 0x0080; // Setup T1 compare value</p><p>　　EvaRegs.T1PR = 0x10; // Setup p

51、eriod register</p><p>　　EvaRegs.GPTCONA.bit.T1TOADC = 1; // Enable EVASOC in EVA</p><p>　　EvaRegs.T1CON.all = 0x1042; // Enable timer 1 compare (upcount mode)</p><p&g

52、t;　　// Wait for ADC interrupt</p><p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　LoopCount++;</p><p><b>　　}</b></p><p>

53、;<b>　　}</b></p><p>　　interrupt void adc_isr(void)</p><p><b>　　{</b></p><p>　　Voltage1[ConversionCount] = AdcRegs.ADCRESULT0 >>4;</p><p>　

54、　Voltage2[ConversionCount] = AdcRegs.ADCRESULT1 >>4;</p><p>　　nMixing[ConversionCount]=Voltage1[ConversionCount]+Voltage2[ConversionCount];</p><p>　　// If 40 conversions have been logged,

55、start over</p><p>　　if(ConversionCount == 1023) </p><p><b>　　{</b></p><p>　　ConversionCount = 0;</p><p><b>　　}</b></p><p>　　else Co

56、nversionCount++;</p><p>　　// Reinitialize for next ADC sequence</p><p>　　AdcRegs.ADCTRL2.bit.RST_SEQ1 = 1; // Reset SEQ1</p><p>　　AdcRegs.ADCST.bit.INT_SEQ1_CLR = 1; /

57、/ Clear INT SEQ1 bit</p><p>　　PieCtrlRegs.PIEACK.all = PIEACK_GROUP1; // Acknowledge interrupt to PIE</p><p><b>　　return;</b></p><p><b>　　}</b></p>

58、<p>　　void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER])</p><p><b>　　{</b></p><p>　　int x0,x1,x2,x3,x4,x5,x6,xx;</p><p>　　int i,j,k,b,p,L;</p><

59、;p>　　float TR,TI,temp;</p><p>　　/********** following code invert sequence ************/</p><p>　　for ( i=0;i<SAMPLENUMBER;i++ )</p><p><b>　　{</b></p><p

60、>　　x0=x1=x2=x3=x4=x5=x6=0;</p><p>　　x0=i&0x01; x1=(i/2)&0x01; x2=(i/4)&0x01; x3=(i/8)&0x01;x4=(i/16)&0x01; </p><p>　　x5=(i/32)&0x01; x6=(i/64)&0x01;</p>&l

61、t;p>　　xx=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6;</p><p>　　dataI[xx]=dataR[i];</p><p><b>　　}</b></p><p>　　for ( i=0;i<SAMPLENUMBER;i++ )</p><p><b>　

62、　{</b></p><p>　　dataR[i]=dataI[i]; dataI[i]=0; </p><p><b>　　}</b></p><p>　　/************** following code FFT *******************/</p><p>　　for ( L=1;

63、L<=7;L++ )</p><p>　　{ /* for(1) */</p><p>　　b=1; i=L-1;</p><p>　　while ( i>0 ) </p><p><b>　　{</b></p><p>　　b=b*2; i--;</p><p&g

64、t;　　} /* b= 2^(L-1) */</p><p>　　for ( j=0;j<=b-1;j++ ) /* for (2) */</p><p><b>　　{</b></p><p>　　p=1; i=7-L;</p><p>　　while ( i>0 ) /* p=pow(2,7-L)*j;

65、*/</p><p><b>　　{</b></p><p>　　p=p*2; i--;</p><p><b>　　}</b></p><p><b>　　p=p*j;</b></p><p>　　for ( k=j;k<128;k=k+2*b

66、) /* for (3) */</p><p><b>　　{</b></p><p>　　TR=dataR[k]; TI=dataI[k]; temp=dataR[k+b];</p><p>　　dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+dataI[k+b]*sin_tab[p];</p>

67、<p>　　dataI[k]=dataI[k]-dataR[k+b]*sin_tab[p]+dataI[k+b]*cos_tab[p];</p><p>　　dataR[k+b]=TR-dataR[k+b]*cos_tab[p]-dataI[k+b]*sin_tab[p];</p><p>　　dataI[k+b]=TI+temp*sin_tab[p]-dataI[k+b]*co

68、s_tab[p];</p><p>　　} /* END for (3) */</p><p>　　} /* END for (2) */</p><p>　　} /* END for (1) */</p><p>　　for ( i=0;i<SAMPLENUMBER/2;i++ )</p><p><b&

69、gt;　　{ </b></p><p>　　w[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i]);</p><p><b>　　}</b></p><p>　　} /* END FFT */</p><p><b>　　main()</b><

70、/p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　InitForFFT();</p><p>　　MakeWave();</p><p>　　for ( i=0;i<SAMPLENUMBER;i++ )</p&

71、gt;<p><b>　　{</b></p><p>　　fWaveR[i]=INPUT[i];</p><p>　　fWaveI[i]=0.0f;</p><p>　　w[i]=0.0f;</p><p><b>　　}</b></p><p>　　FFT(f

72、WaveR,fWaveI);</p><p>　　for ( i=0;i<SAMPLENUMBER;i++ )</p><p><b>　　{</b></p><p>　　DATA[i]=w[i];</p><p><b>　　}</b></p><p>　　while

73、 ( 1 );// break point</p><p><b>　　}</b></p><p>　　void InitForFFT()</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　f

74、or ( i=0;i<SAMPLENUMBER;i++ )</p><p><b>　　{</b></p><p>　　sin_tab[i]=sin(PI*2*i/SAMPLENUMBER);</p><p>　　cos_tab[i]=cos(PI*2*i/SAMPLENUMBER);</p><p><b&

75、gt;　　}</b></p><p><b>　　}</b></p><p>　　void MakeWave()</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for ( i=0

76、;i<SAMPLENUMBER;i++ )</p><p>　　{admain();</p><p>　　INPUT[i]=Voltage1[ConversionCount]+Voltage2[ConversionCount]*3;</p><p><b>　　}</b></p><p><b>　　}&

77、lt;/b></p><p><b>　　六.系統(tǒng)仿真</b></p><p>　?。?）啟動CCS，在CCS中建立一個C源文件和一個命令文件，并將這兩個文件添加到工程，再編譯并裝載程序：</p><p>　　閱讀Dsp原理及應用中fft 用dsp實現(xiàn)的有關(guān)程序。</p><p>　　雙擊，啟動CCS的仿真平臺的配

78、著選項。</p><p>　　（3）啟動ccs2后建立工程文件FFT.pjt</p><p>　?。?）建立源文件FFT.c與鏈接文件FFT.cmd</p><p>　　（5）將這兩個文件加到FFT.pjt這個工程中。</p><p>　　（6）創(chuàng)建out文件</p><p>　?。?）加載out文件</p>

79、;<p><b>　　（8）加載數(shù)據(jù)</b></p><p>　?。?）觀察輸入輸出波形</p><p><b>　　七. 總結(jié)</b></p><p>　　本實驗通過學習快速傅里葉變換(FFT)的原理，然后在CCS平臺下編程對其進行模擬仿真，對快速傅里葉變換(FFT)有個一個較深刻的理解。并且熟悉了DSP，

80、CCS平臺，達到了課程教學的目的。但由于初學DSP，許多東西不明白，以后還需對DSP努力學習研究。</p><p>　　通過這次DSP課程設計，加深對DFT算法原理和基本性質(zhì)的理解，熟悉了FFT的算法原理和FFT子程序的算法流程和應用，掌握了DSP中FFT的設計和編程思想，以及用FFT對連續(xù)信號和時域信號進行頻譜分析的方法，和使用CCS的波形觀察器觀察波形和頻譜情況。</p><p>　　

81、這次課程設計，使我增長了知識，同時也增強了我動手解決問題的能力，鍛煉我做事細心、用心、耐心的能力。同時也讓我意識到平時的課程文化的學習固然非常重要，但是在與實際相聯(lián)系的過程中還是有許多問題的，所以在以后的學習生活中，我要努力學習，培養(yǎng)自己獨立思考的能力，要加強理論文化與實際操作的聯(lián)系。</p><p><b>　　參考文獻：</b></p><p>　　1.DSP原理

82、及應用其 鄒彥,唐冬,寧志剛,王毓銀 電子工業(yè)出版社</p><p>　　2.TMS320C5000系列DSP系統(tǒng)設計與開發(fā)實例 汪春梅,孫洪波,任治剛 電子工業(yè)出版社</p><p>　　3.DSP芯片的原理與開發(fā)應用(第三版) 張雄偉,陳亮,徐光輝 電子工業(yè)出版社</p><p>　　4.實時數(shù)字信號處理 SEN M.KU