快速傅立葉變換（FFT）的實現一、實驗目的在數字信號處理系統中，FFT作為一個非常重要的工具經常使用，甚至成為DSP運算能力的一個考核因素。FFT是一種高效實現離散付氏變換的算法。離散付氏變換的目的是把信號由時域變換到頻域，從而可以在頻域分析處理信息，得到的結果再由付氏逆變換到時域。本實驗的目的在于學習FFT算法，及其在TMS320C54X上的實現，并通過編程掌握C54X的存儲器管理、輔助寄存器的使用、位倒序尋址方式等技巧，同時練習使用CCS的探針和圖形工具。另外在BIOS子目錄下是一個使用DSP/BIOS工具實現FFT的程序。通過該程序，你可以使用DSP/BIOS提供的分析工具評估FFT代碼執行情況。二、實驗原理1） 基2按時間抽取FFT算法對于有限長離散數字信號{x[n]}，0≤n≤-1N，其離散譜{x[k]}可以由離散付氏變換（DFT）求得。DFT的定義為：X(k)x[n]eNk0,1,...,N1n0可以方便的把它改寫為如下形式：N1nkX(k) x[n]WnNkk0,1,...,N1n0不難看出，WN是周期性的，且周期為N，即(nmN)(klN) nkWN WNm,l0,1,2...WN的周期性是DFT的關鍵性質之一。為了強調起見，常用表達式WN取代W以便明確其周期是N。實數FFT運算對于離散傅立葉變換(DFT)的數字計算，FFT是一種有效的方法。一般假定輸入序列是復數。當實際輸入是實數時，利用對稱性質可以使計算DFT非常有效。一個優化的實數FFT算法是一個組合以后的算法。原始的2N個點的實輸入序列組合成一個N點的復序列，之后對復序列進行N點的FFT運算，最后再由N點的復數輸出拆散成2N點的復數序列，這2N點的復數序列與原始的2N點的實數輸入序列的DFT輸出一致。使用這種方法，在組合輸入和拆散輸出的操作中，FFT運算量減半。這樣利用實數FFT算法來計算實輸入序列的DFT的速度幾乎是一般復FFT算法的兩倍。本實驗就用這種方法實現了一個256點實數FFT(2N=256)運算。a.實數FFT運算序列的存儲分配如何利用有限的DSP系統資源，合理的安排好算法使用的存儲器是一個比較要的問題。參見FFT實驗程序的CMD文件：MEMORYPAGE0：IPROG：origin=0x3080,len=0x1F80VECT：origin=0x3000,len=0x80EPROG：origin=0x38000,len=0x8000PAGE1：USERREGS：origin=0x60,len=0x1cBIOSREGS：origin=0x7c,len=0x4IDATA：origin=0x80,len=0xB80EDATA：origin=0xC00,len=0x1400}SECTIONS{.vectors：{}>VECTPAGE0.sysregs：{}>BIOSREGSPAGE1.trcinit：{}>IPROGPAGE0.gblinit：{}>IPROGPAGE0.bios：{}>IPROGPAGE0frt：{}>IPROGPAGE0.text：{}>IPROGPAGE0.cinit：{}>IPROGPAGE0.pinit：{}>IPROGPAGE0.sysinit：{}>IPROGPAGE0.data{}>EDATAPAGE1.bss：{}>IDATAPAGE1.far：{}>IDATAPAGE1.const：{}>IDATAPAGE1.switch：{}>IDATAPAGE1.sysmem：{}>IDATAPAGE1.cio：{}>IDATAPAGE1.MEM$obj：{}>IDATAPAGE1.sysheap：{}>IDATAPAGE1}從上面的連接定位CMD文件可以了解到，程序代碼安排在0x3000開始的存儲器中。其中0x3000-0x3080存放中斷向量表。FFT程序使用的正弦表、余弦表數據（.data段）安排在0xc00開始的地方。變量（.bss段定義）存放在0x80開始的地址中。另外，本256點實數FFT程序的輸入數據緩沖為0x2300-0x23ff，FFT后功率譜的計算結果存放在0x2200-0x22ff中。b.基二實數FFT運算的算法該算法主要分為四步：第一步，輸入數據的組合和位倒序第二步，N點復數FFT第三步，分離復數FFT的輸出為奇部分和偶部分

第四步，產生最后的N=256點的復數FFT結果計算所求信號的功率由于最后所得的FFT數據是一個復數，為了能夠方便的在虛擬頻譜儀上觀察該信號的特征，我們通常對所得的FFT數據進行處理——取其實部和虛部的平方和，即求得該信號的功率。power：.asgAR2,AX.asgAR3,OUTPUT_BUFpshmst0；保存寄存器的值pshmst0；保存寄存器的值pshmar0pshmbkSTM#d_output_addr,OUTPUT_BUF；AR3指向輸出緩沖地址STM#K_FFT_SIZE*2-1,BRC；塊循環計數器設置為255RPTBDpower_end-4；帶延遲方式的重復執行RPTBDpower_end-4；帶延遲方式的重復執行指令STM#fft_data,AX；STM#fft_data,AX；AR2指向AR[0]SQUR*AX+,A；SQUR*AX+,A；A：=AR2SQURA*AX+,A；SQURA*AX+,A；A：=AR2+AI2STHA,7,*OUTPUT_BUF；將STHA,7,*OUTPUT_BUF；將A中的數據存入輸出緩沖中，ANDM#7FFFH,*OUTPUT_BUF+；避免輸出數據過大在虛擬示波器；中顯示錯誤popmbk；保存各個寄存器值popmar0popmst0power_end：RET注意，在上面的程序中將數據放回輸出緩沖準備輸出時使用了指令：STHA,7,*OUTPUT_BUF對accA左移7位是為了讓顯示的數據值在一個合適的范圍內有利于觀察顯示的圖形，由于所有的數據都左移了7位，所以從總體上看整個波形的性質還是一樣的。同時，由于有的數據太大，為了避免顯示數據的溢出而導致在虛擬示波器中觀察到的波形錯誤所以我們使用了指令：ANDM#7FFFH,*OUTPUT_BUF+來取出有效的數據位數。三、實驗內容1）啟動CCS，在Project菜單相項中打開FFT目錄下的fft.pjt文件。2）用鼠標展開左面項目欄，打開fft.asm源程序使用Bulid命令完成編譯、連接，并使用LoadProgram將生成的fft.out裝入5402片內存儲器。將光標移動到“callget_input行”，并設置一個探針點。將光標移動到下一行“nop語”句，使用工具設置一個斷點。在File菜單中打開選項“FileI/O，使”用“AddFile在”FFT目錄下打開數據文件fft.dat，然后修改“Address參”數為0x2300，修改“Length參”數為256。這表示程序執行到探針點時，將從fft.dat文件中讀出256個數據，并將數據放入0x2300開始的存儲器中。你可以選擇“WrapAround”，循環使用該數據文件。選擇“AddProbePoint，”將探針點與數據文件連接起來。選擇探針點，然后在“Connect選”項中選擇需要使用的數據文件名，再選擇“Replace，”按確定鍵完成。這時將返回圖7所示的對話框。你可以看到“Probe項”被自動修改為“Connected”，表示探針已經與數據文件成功相連。完成探針設置后，可以使用F5或“Run”命令啟動程序運行。程序執行到探針點時自動從數據文件讀出256個點的數據放入輸入緩沖0x2300。在“View菜”單項下選擇“Graph->Time/Frequency，”打開一個圖形工具以便顯示輸入數據波形。將“StartAddress”改為0x2300，將“AcquisitionBufferSize改”為128，將“DSPDataType”改為“1-6bitsignedinteger，這”樣即可顯示128個輸入點波形。

調整窗口顯示大小，將光標移動到源程序的“b_c_int00這”行，使用Debug中的“RuntoCursor項”，程序將執行到這行并停下。這時FFT程序已經計算完成。再打開一個波形顯示窗口，這次僅僅將“StartAddress改為”0x2200，便可以顯示計算完成后的譜波形。選擇“Debug下”的“Animate運”行程序，這時程序將循環運行，不斷從數據文件fft.dat中讀出數據，并計算其頻譜。這時你可以看到連續的輸入/輸出波形。

選擇原始數據波形窗口，單擊鼠標右鍵，進入“Properties屬性”對話框。你可以將“DisplayType”改為“FFTMagnitude”，這時輸入數據將顯示其頻譜，對比兩個圖形，看看譜線的位置一樣嗎？清除所有斷點、探針點，關閉CCS的源程序窗口和上面的工程文件fft.pjt，然后在Project菜單下打開BIOS目錄下fft.pjt文件。這時一個使用DSP/BIOS工具實現FFT的例子。為了使用DSP/BIOS的工具分析工具，我們將FFT的源程序做了一點修改。將FFT子程序做為一個中斷函數，并在DSP/BIOS的周期模塊中調用。所以在DSP/BIOS的配置文件中增加一個周期模塊PRD0，并且設置每1ms執行一次，即每1ms執行一次FFT子程序。。這時的主程序僅僅完成一次數據輸入，然后返回 DSP/BIOS。以后DSP/BIOS將每隔1ms啟動一次周期函數，完成一次FFT。在File菜單中用LoadProgram裝入BIOS目錄下的demo5402.out文件。參照前面的函數中的“callwait_input設”置一個探針點，并建立數據文件連接。這時應該將輸入數據讀到0x2900開始的存儲器中。在FFT子程序process中設置一個斷點，啟動程序運行。程序將在第一次進入周期函數執行FFT子程序時停下來。使用

圖形工具觀察輸入信號波形（啟始地址0x2900）。將FFT子程序執行完，然后再使用圖形工具觀察FFT后的波形（啟始地址0x2800）。15） 清除所有斷點，以便程序連續運行。使用Tools菜單下的DSP/BIOS選項打開“RTAContr