快速傅里葉變換(FFT)課程設計

快速傅里葉變換(FFT)的DSP實現(馬燦明計算機學院計算機應用技術2110605410)摘要:本文對快速傅里葉變換(FFT)原理進行簡單介紹后，然后介紹FFT在TMS320C55xx定點DSP上的實現，FFT算法采用C語言和匯編混合編程來實現，算法程序利用了CCS對其結果進行了仿真。關鍵字：FFT，DSP，比特反轉1.引言傅里葉變換是將信號從時域變換到頻域的一種變換形式，是信號處理領域中一種重要的分析工具。離散傅里葉變換〔DFT〕是連續(xù)傅里葉變換在離散系統(tǒng)中的表現形式。由于DFT的計算量很大，因此在很長一段時間內使其應用受到很大的限制。20世紀60年代由Cooley和Tukey提出了快速傅里葉變換〔FFT〕算法，它是快速計算DFT的一種高效方法，可以明顯地降低運算量，大大地提高DFT的運算速度，從而使DFT在實際中得到了廣泛的應用，已成為數字信號處理最為重要的工具之一。DSP芯片的出現使FFT的實現變得更加方便。由于多數的DSP芯片都能在單指令周期內完成乘法—累加運算，而且還提供了專門的FFT指令〔如實現FFT算法所必需的比特反轉等〕，使得FFT算法在DSP芯片上實現的速度更快。本節(jié)首先簡要介紹FFT算法的根本原理，然后介紹FFT算法的DSP實現。2.FFT算法的簡介快速傅里葉變換〔FFT〕是一種高效實現離散傅里葉變換〔DFT〕的快速算法，是數字信號處理中最為重要的工具之一，它在聲學，語音，電信和信號處理等領域有著廣泛的應用。2.1離散傅里葉變換DFT對于長度為N的有限長序列x(n)，它的離散傅里葉變換〔DFT〕為〔1〕式中，，稱為旋轉因子或蝶形因子。從DFT的定義可以看出，在x(n)為復數序列的情況下，對某個k值，直接按〔1〕式計算X(k)只需要N次復數乘法和〔N-1〕次復數加法。因此，對所有N個k值，共需要N2次復數乘法和N(N-1)次復數加法。對于一些相當大有N值〔如1024點〕來說，直接計算它的DFT所需要的計算量是很大的，因此DFT運算的應用受到了很大的限制。2.2快速傅里葉變換FFT旋轉因子WN有如下的特性。。對稱性：。周期性：利用這些特性，既可以使DFT中有些項合并，減少了乘法積項，又可以將長序列的DFT分解成幾個短序列的DFT。FFT就是利用了旋轉因子的對稱性和周期性來減少運算量的。FFT的算法是將長序列的DFT分解成短序列的DFT。例如：N為偶數時，先將N點的DFT分解為兩個N/2點的DFT，使復數乘法減少一半：再將每個N/2點的DFT分解成N/4點的DFT，使復數乘又減少一半，繼續(xù)進行分解可以大大減少計算量。最小變換的點數稱為基數，對于基數為2的FFT算法，它的最小變換是2點DFT。一般而言，FFT算法分為按時間抽取的FFT〔DITＦＦＴ〕和按頻率抽取的ＦＦＴ〔DIFFFT〕兩大類。ＤIFFFT算法是在時域內將每一級輸入序列依次按奇／偶分成２個短序列進行計算。而DIFFFT算法是在頻域內將每一級輸入序列依次奇／偶分成２個短序列進行計算。兩者的區(qū)別是旋轉因子出現的位置不同，得算法是一樣的。在DIFFFT算法中，旋轉因子出現在輸入端，而在DIFFFT算法中它出現在輸入端。假定序列x(n)的點數N是2的冪，按照DIFFFT算法可將其分為偶序列和奇序列。偶序列：奇序列：那么x(n)的DFT表示為由于，那么〔3〕式可表示為式中，和分別為和的N/2的DFT。由于對稱性，那么。因此，N點可分為兩局部：前半局部：〔4〕后半局部：〔5〕從式〔4〕和式〔5〕可以看出，只要求出0~N/2-1區(qū)間和的值，就可求出0~N-1區(qū)間的N點值。以同樣的方式進行抽取，可以求得N/4點的DFT，重復抽取過程，就可以使N點的DFT用上組2點的DFT來計算，這樣就可以大減少運算量?；?DIFFFT的蝶形運算如圖(a)所示。設蝶形輸入為和，輸出為和，那么有〔6〕〔7〕在基數為2的FFT中，設N=2M，共有M級運算，每級有N/2個2點FFT蝶形運算，因此，N點FFT總共有個蝶形運算。-1圖(a)基2DIFFFT的蝶形運算例如：基數為2的FFT，當N=8時，共需要3級，12個基2DITFFT的蝶形運算。其信號流程如圖(b)所示。x(0)x(0)WN0x(4)x(1)-1WN0x(2)x(2)-1WN0WN2x(6)x(3)-1-1WN0x(1)x(4)-1WN0WN1x(5)x(5)-1-1WN0WN2x(3)x(6)-1-1WN0WN2WN3x(7)x(7)-1-1-1圖(b)8點基2DIFFFT蝶形運算從圖(b)可以看出，輸入是經過比特反轉的倒位序列，稱為位碼倒置，其排列順序為。輸出是按自然順序排列，其順序為。3.FFT算法的DSP實現DSP芯片的出現使FFT的實現方法變得更為方便。由于大多數DSP芯片都具有在單指令周期內完成乘法—累加操作，并且提供了專門的FFT指令，使得FFT算法在DSP芯片實現的速度更快。FFT算法可以分為按時間抽取FFT(DIFFFT)和按頻率抽取FFT(DIFFFT)兩大類，輸入也有實數和復數之分，一般情況下，都假定輸入序列為復數。下面以N復數點FFT算法為例，介紹用DSP芯片實現的方法。3.1FFT運算的實現用TMS320C55XX的C語言和匯編混合編程實現FFT算法主要分為三步:實現輸入數據的比特反轉輸入數據的比特反轉實際上就是將輸入數據進行位碼倒置,以便在整個運算后的輸出序列是一個自然序列。在用匯編指令進行位碼倒置是，使用位碼倒置尋址可以大大擔高程序執(zhí)行速度和使用存儲器的效率。在這種尋址方式下，AR0存放的整數N是FFT點的一半，一個輔助存放器指向一個數據存放的章元。當使用位碼倒置尋址將AR0加到輔助存放器時，地址將以位碼倒置的方式產生。實現N點復數FFTN點復數FFT算法的實現可分為三個功能塊，即第一級蝶形運算，第二蝶形運算，第三級至級蝶形運算。對于任何一個2的整數冪N=2M，，總可以通過M次分解最后成為2點的DFT計算。通過這樣的M次分解，可構成M〔即〕級迭代運算完成。輸出FFT結果3.2FFT算法程序主要由exp7b.c,w_table.c,fft.asm,bit_rev.asm四個程序組成.exp7b.c：主調用子程序用來調用其他程序,實現統(tǒng)一接口。w_table.c：旋轉因子程序，用來計算旋轉因子。bit_rev.asm：位碼倒置程序，用來實現輸入數據的比特反轉。fft.asm：FFT算法主程序，用來完成N點FFT運算。4.小結：本實驗通過學習快速傅里葉變換(FFT)的原理，然后在CCS平臺下編程對其進行模擬仿真，對快速傅里葉變換(FFT)有個一個較深刻的理解。并且熟悉了DSP，CCS平臺，到達了課程教學的目的。但由于初學DSP，許多東西不明白，以后還需對DSP努力學習研究，到達一個高水平。參