???????1 快速傅里葉變換的原理

　　非周期性連續時間信號x(t)的傅里葉變換可以表示為

　　式中計算出來的是信號x(t)的連續頻譜。但是，在實際的控制系統中能夠得到的是連續信號x(t)的離散采樣值x(nT)。因此需要利用離散信號x(nT)來計算信號x(t)的頻譜。

　　有限長離散信號x(n)，n=0，1，…，N-1的DFT定義為：

　　可以看出，DFT需要計算大約N2次乘法和N2次加法。當N較大時，這個計算量是很大的。利用WN的對稱性和周期性，將N點DFT分解為兩個N/2點的 DFT，這樣兩個N/2點DFT總的計算量只是原來的一半，即(N/2)2+(N/2)2=N2/2，這樣可以繼續分解下去，將N/2再分解為N/4點 DFT等。對于N=2m 點的DFT都可以分解為2點的DFT，這樣其計算量可以減少為(N/2)log2N次乘法和Nlog2N次加法。圖1為FFT與DFT-所需運算量與計算點數的關系曲線。由圖可以明顯看出FFT算法的優越性。

　　將x(n)分解為偶數與奇數的兩個序列之和，即

　　x1(n)和x2(n)的長度都是N/2，x1(n)是偶數序列，x2(n)是奇數序列，則

　　其中X1(k)和X2(k)分別為x1(n)和x2(n)的N/2點DFT。由于X1(k)和X2(k)均以N/2為周期，且WN k+N/2=-WN k，所以X(k)又可表示為：

　　上式的運算可以用圖2表示，根據其形狀稱之為蝶形運算。依此類推，經過m-1次分解，最后將N點DFT分解為N/2個兩點DFT。圖3為8點FFT的分解流程。

　　FFT算法的原理是通過許多小的更加容易進行的變換去實現大規模的變換，降低了運算要求，提高了與運算速度。FFT不是DFT的近似運算，它們完全是等效的。

　2 快速傅里葉算法在TMS320LF2407上的實現

　　根據FFT算法的特點，處理器要在一個指令周期內完成乘和累加的工作，因為復數運算要多次查表相乘才能實現。其二就是間接尋址，可以實現增/減1個變址量，方便各種查表方法。再次，FFT變換的輸入序列x(n)是按所謂的碼位倒序排列的，處理器要有反序間接尋址的能力。DSP控制器專門設計了特有的反序間接尋址，并能在一個指令周期內完成乘和累加的運算。因此，對數字信號的分析處理，DSP比其它的處理器有絕對的優勢。本文采用TI公司C2000系列TMS320LF2407芯片來實現FFT算法。

　　TMS320LF2407定點DSP是一款專為工業控制、電機控制和數字信號處理等用途而設計的DSP，具備單周期乘加指令，具有FFT反序間接尋址功能，最高運行速度為40MIPS。為了充分利用DSP芯片特有的反序間接尋址等功能，FFT算法程序采用匯編語言編寫，主程序采用C語言，因此程序具有良好的兼容性和可擴展性。

　　主程序流程圖如圖4所示。系統初始化主要完成DSP的系統控制和狀態寄存器、等待狀態發生器控制寄存器、中斷寄存器等的必要設置。

　　本程序采樣函數為：x=sin(20πt)，采樣頻率為640Hz。

　　輸入數據波形如圖5所示。一般情況下，我們只關心信號頻域的幅度譜。幅度譜|X(k)|2的計算：X(k)=XR(k)+jX(k)，|X(k)2|=|Xr(k)|2+|Xi(k)|2。FFT計算結果的信號幅度譜|X(k)|2如圖6所示。

　　輸入信號頻率是10Hz，根據公式f=kfs/N，f是原始信號的頻率，k表示峰值出現的位置，fS是采樣頻率，N是計算的點數，從幅度譜中看出，峰值出現在k=1處，那么，f=1×640/64=10，與原始信號的實際頻率一致，說明計算結果正確。