摘要：通過對常用快速傅里葉變換算法原理的研究分析，提出了一種簡單有效的FFT算法實現方案，該方案已經在TMS320C64x DSP中實現。將FFT算法程序在CCS3.3中運行，驗證了該方案的可行性、高效性。該方案已應用于LTE—TDD無線綜合測試儀表的開發中。
在數字信號處理中，離散傅里葉變換(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算法作為一個子函數模塊且輸入序列長度不盡相同，所以，方案定義了輸入輸出變量及其調用格式。調用格式：Turbo_Code(int*，int，int，char*，char*，int*)，其中，int分別表示輸入序列的長度和FFT的級數；int*分別表示輸入序列的首地址和輸出序列的首地址；char*分別表示旋轉因子的余弦的首地址和旋轉因子的正弦的首地址。
FFT算法具體實現流程如下：
(1)時間抽取法的FFT中，每個蝶形的輸入、輸出數據節點在一條水平線上，所以每個蝶形的輸出數據可以立即存入原輸入數據所占用的存儲單元。這種原位計算可節省大量的內存，并且理論上減少不同寄存器之間存取數據的時間。
使用C語言編寫主函數，匯編語言編寫FFT算法的實現函數。程序中假設輸入數據最大長度為1024，由于DSP C6455可以直接存取處理32bit，所以在內存中定義了長度為8192bit作為存放輸出序列的內存空間。為了提高運算精確度，輸入數的實部和虛部分別占用一個字，在程序中進行復數相乘操作是采用匯編指令MPYHI。內存定義了長度為2048bit的Tempsequence作為存放倒序序列，并且建立了2張旋轉因子查找表，分別為Wr和Wi。
外循環中，在每次內循環之前從輸入比特序列中取出32bit放入一個寄存器，作為一個內循環的輸入，內循環結束后，取下一個32bit輸入比特更新這個寄存器。
內循環中，計算蝶形過程采用查表的方式。對于每一級，計算出需要的旋轉因子個數以及相同旋轉因子相距的間隔。計算蝶形過程時，首先提取出X(k)，根據相同旋轉因子間隔找到X(k+B)完成蝶形計算。考慮到旋轉因子的對稱性，在內存中存放旋轉因子時只存放一半，剩余的數據根據對稱性進行處理。圖2給出了FFT算法實現計算流程圖。
按時間抽取法的FFT輸入序列是倒序，輸出序列是自然順序；按頻率抽取法的FFT輸入序列是自然順序，輸出序列是倒序的。不管采用哪種方法進行FFT計算，都需要倒序處理。倒序是整個FFT計算的重要部分，進行匯編程序時，按自然順序將輸入數據存入到存儲單元內，通過變址運算，將自然順序的序列按時間抽取法要求進行倒位。
重新排序之前，存儲單元Y中依次存放輸入數據，I表示當前輸入數據比特的順序數的十進制數值，I的取值從0到N-I；J表示當前倒序數的十進制數值。輸入序列的第一個和最后一個數的位置不需要倒序處理，完成倒序的外循環的次數為N-2。為了保證調換數據的正確性，需要檢測一下是否I<J，只有當I<J，才將Y(I)與Y(J)的內容互換。形成倒序數J以后，就可以實現變址功能，按照自然順序存放在存儲單元的數據重新按照倒序排列。圖3給出了實現倒序的匯編流程圖。
3 性能分析與總結
在DSP軟件實現中，通過指令并行，盡量優化程序循環體，減少或消除程序中的’NOP’指令[6]。通過程序仿真運行，得到統計結果如表1所示。
從表中可以看出，當運用TMS320C64×DSP芯片實現時，由于處理器的超高主頻一般為1GHz，一個指令周期耗時為1ns，其運算速率非常快，完全可以滿足實時性信號處理。因此，采用旋轉因子查表法的實現方案不僅簡化了程序實現方法，還減少了模塊程序代碼編寫，節約了系統存儲空間。
本文提出了一種簡單有效的FFT算法實現方案，詳細介紹了算法在DSP的實現方法，并在TMS320C64x芯片上加以實現。程序運行結果表明，該算法能夠滿足TD-LTE系統的需求，具有可行性和高效性。該方案已應用于LTE-TDD無線綜合測試儀表的開發中。
參考文獻
[1] 丁玉美.數字信號處理[M].西安：西安電子科技大學出版社，2002.
[2] 何方白，張德民.數字信號處理[M].北京：高等教育出版社，2009.
[3] 3GPP TS 36.211 v9.0.0.Evolved universal terrestrial radio access(E-UTRA) physical channels and modulation (Release 9)[S].2009-12.
[4] SAIDI A.Decimation-in-time-frequency FFT algorithm[M]. Manuscript，To be published.1993.
[5] Texas Instruments Incorporated.TMS320C64x/C64x+DSP CPU and instruction set referenceguide[EB/OL].Http://www.ti.com.cn，2008.
[6] Texas Instruments Incorporated.TMS320C6000系列DSP編程工具與指南[M].田黎育，何佩琨，朱夢宇，譯.北京：清華大學出版社，2006.
