在數字信號處理中，離散傅里葉變換(DFT)是常用的變換方法，它在各種數字信號處理系統中扮演著重要的角色。快速傅里葉變換(FFT)[1-2]是離散傅里葉變換的快速算法，它是根據離散傅里葉變換的奇、偶、虛、實等特性，對離散傅里葉變換的算法進行改進獲得的，兩者都是為了將信號變換到頻域并進行相應的頻譜分析。對于實時性要求很強的信號處理來說，運算速度對整個處理的影響是顯而易見的。因為FFT擁有很高的運算能力，使其在無線通信和數字通信、高速圖像處理、匹配濾波等領域得到極為廣泛的應用。

　　LTE作為準4G技術，以正交頻分復用OFDM和多輸入多輸出MIMO技術為基礎，下行采用正交頻分多址(OFDM)技術，上行采用單載波頻分多址(SC-FDMA)技術，在20MHz頻譜帶寬下能夠提供下行100Mb/s和上行50Mb/s的峰值速率[3]。

　　頻域分析比時域分析更優越，不僅簡單，且易于分析復雜信號[4]。在LTE系統中，FFT算法主要應用于基帶信號生成、信號的接收和檢測等，將時域信號轉移到頻域進行處理。

　　其中，x(n)為復數序列，WNkn和X(K)也為復數，因此每計算一個X(K)值，需要進行N次復數乘法運算和N-1次復數加法運算。而X(K)共有N個點，所以完成整個DFT運算需要進行N2次復數乘法和N(N-1)次復數加法運算，當N很大時，運算量相當可觀。然而對于實時性很強的信號處理來說，如滿足其要求，運算速度就太高了。利用旋轉因子WNkn的對稱性、周期性和可約性，可以使DFT運算中的有些項合并，將長序列的DFT分解為幾個短序列的DFT，從而大大減少運算次數。FFT算法可以分為時間抽取法和頻域抽取法兩大類。頻域抽取法的運算特點與時間抽取法的基本相同，不同之處是頻域抽取法的蝶形運算是先加后乘，時間抽取法的蝶形運算是先乘后加;頻域抽取的輸入序列是自然順序，輸出序列是倒序，而時間抽取法的輸入序列是倒序，輸出序列是自然順序。

　　假設輸入序列x(n)長度為N=2M，M是正整數。如果不滿足這個條件，在序列尾部人為地加上若干零值點，使其達到這一要求。將序列x(n)按n的奇偶分解為兩個N/2點的子序列：

　　2 FFT算法的DSP實現

　　2.1 硬件

　　TMS320C6000系列DSP是TI公司推向市場的高性能DSP，綜合了目前性價比高、功耗低等優點。TMS320C64系列提高了時鐘頻率，在體系結構上采用了VelociTI甚長指令集VLIW(Very Long Instruction Word)結構[5]，芯片內有8個獨立功能單元的內核，每個周期可以并行執行8條32bit指令，最大峰值速度為4800MIPS，2組共64個32bit通用寄存器，32bit尋址范圍，支持8/16/32/40 bit的數據訪問，芯片內集成大容量SRAM，最大可達8Mb。由于出色的運算能力、高效的指令集、大范圍的尋址能力，使其特別適用于無線基站、測試儀表等對運算能力和存儲量要求高的應用場合。

　　2.2 FFT算法的DSP實現

　　FFT算法作為一個子函數模塊且輸入序列長度不