摘 要：提出一種利用并行算法來實現(xiàn)FFT（快速傅里葉變換）及其逆變換IFFF（快速傅里葉逆變換）的設(shè)計方法。該處理器可由用戶動態(tài)配置成64、256、1024點復(fù)數(shù)FFT或其逆變換IFFT。
關(guān)鍵詞：FPGA，F(xiàn)FT，IFFT
1 引言
高速實時數(shù)字信號處理對系統(tǒng)性能要求很高，因此，幾乎所有的通用DSP都難以實現(xiàn)這一要求�？删幊踢壿嬈骷试S設(shè)計人員利用并行處理技術(shù)實現(xiàn)高速信號處理算法，并且只需單個器件就能實現(xiàn)期望的性能。在數(shù)據(jù)通信這樣的應(yīng)用中，常常需要進行高速、大規(guī)模的FFT及其逆變換IFFT運算。當通用的DSP無法達到速度要求時，唯一的選擇是增加處理器的數(shù)目，或采用定制門陣列產(chǎn)品�，F(xiàn)在，隨著微電子技術(shù)的發(fā)展，采用現(xiàn)場可編程門陣列（FPGA）進行數(shù)字信號處理發(fā)展迅速。采用現(xiàn)場可編程器件不僅加速了產(chǎn)品上市時間，還可滿足現(xiàn)在和下一代便攜式設(shè)計所需要的成本、性能、尺寸等方面的要求，并提供系統(tǒng)級支持。本文研究了基于FPGA的FFT及其逆變換IFFT處理器的硬件電路實現(xiàn)方法。在系統(tǒng)時鐘頻率為100MHz時，1024點復(fù)位FFT的計算時間只需要10μs左右。
2 基4 FFT/IFFT算法
序列x(n),n=0,...,N-1的離散傅里葉變換為：
這說明IFFT可以由FFT求出。因此，F(xiàn)FT和IFFT處理器可以用統(tǒng)一的硬件結(jié)構(gòu)來實現(xiàn)。
對于FFT，設(shè)序列x(n)的長度為N=4p(p為整數(shù))，則基4頻率抽取蝶菜運算單元方程為：
3 FFT/IFFT的硬件實現(xiàn)
我們采用Xilinx公司的Virtex-II系列FPGA來實現(xiàn)FFT/IFFT處理器。
3.1 蝶形運算單元結(jié)構(gòu)
基4頻率抽取FFT計算一共包括了log4(N)級運算，其中，在每一級中包含了N/4個基4蝶形運算，蝶形運算器如圖1所示。
Virtex-II系列FPGA有內(nèi)嵌18bit×18bit 補碼乘法器以及大容量用戶可配置RAM，非常適合做大規(guī)模算術(shù)運算。圖1所示的蝶形運算器可以在一個時鐘周期內(nèi)完成一次基4蝶形運算。其中，操作數(shù)A、 B、C、D存放在RAM中，三個18位放置因子W1、W2、W3存放在ROM中。由于運算結(jié)果可能會超過原數(shù)據(jù)，所以要進行量化移位[1][2]。
3.2 并行運算結(jié)構(gòu)
通用DSP的蝶算單元通常是從內(nèi)存中順序讀入四個操作數(shù)A、B、C、D，因而計算速度受到了很大限制。而使用FPGA可充分利用并行計算技術(shù)在一個時鐘周期內(nèi)并行讀取四個操作數(shù)，以便完成一次基4蝶形運算。我們采用四對RAM×2（分別存放實部和虛部）來存儲蝶算中的操作數(shù)A、B、C、D。如圖2所示，處理器在每個時鐘周期從RAM中讀出數(shù)據(jù)A、B、C、D送入蝶形運算器（圖1）。運算結(jié)果AO、BO、CO、DO在下一個時鐘周期寫回原地址。
圖2中的四對RAM×2的地址A0，A1，A2，A3分別對應(yīng)公式（3）中的n,n+4p-s-1,n+2×4p-s-1,n+3×4p-s-1。A0，A1，A2，A3可以按下述方法產(chǎn)生：
設(shè)a,b為兩個遞減計數(shù)器，它們組成一個大的計數(shù)器Counter=a×4p-1+b。如圖3所示。
ROTATEn(x,m)表示把x(n位二進制)循環(huán)左移m位。則圖2中四個操作數(shù)地址為：
式（4）中每個地址對應(yīng)一個RAM×2的入口地址。設(shè)操作數(shù)地址A的四進制表達式為A=（Kp-1...K1K0）4。定義Mk為A的所有四進制位數(shù)和除以4的余數(shù)
式（5）中，mod為求余運算。
可以證明地址A0，A1，A2，A3的Mk值互不相同，取值范圍是0，1，2，3。因此我們采取如圖2所示的并行存儲結(jié)構(gòu)：所有Mk=0的操作數(shù)都存放在RAMA中，Mk=1的操作數(shù)都存放在RAM B中，Mk=2的操作數(shù)都存放在RAM C中，Mk=3的操作數(shù)都存放在RAM D中。通過以上地址映射，我們可以在一個時鐘周期并行讀取四個操作數(shù)地址，完成蝶形運算。
3.3 放置因子的生成
為了加快FFT/IFFT運算速度，我們采用查表的方式來得到放置因子W1，W2，W3（圖1），我們采用3對ROM×2（實部和虛部）來存放復(fù)數(shù)W1，W2，W3，三個ROM的入口地址都為c�？梢宰C明，把圖3中的計數(shù)器b的低2(p-a-1)位都置為0所得到的值即為c的值。即：
3.4 FFT/IFFT芯片整體結(jié)構(gòu)
FFT/IFFT芯片整體結(jié)構(gòu)如圖4所示。在式（2）中討論過，我們可以用FFT來計算IFFT，只需要先求出輸入序列的共軛X*(k)，然后進行正常的蝶形運算，在輸出時再進行一次求共軛運算。所謂復(fù)位的共軛是對它的虛部取反，實部不變。因此，我們可以把處理器動態(tài)地配置成FFT或其逆變換IFFT。為了充分利用I/O帶寬、連續(xù)地進行FFT/IFFT。為了充分利用I/O帶寬、連續(xù)地進行FFT/IFFT。我們采用了乒乓緩沖存儲結(jié)構(gòu)，如圖4所示。由于FFT/IFFT計算采用的是同址計算，每次蝶形運算結(jié)果要寫回原地址中，所以，RAM X和RAM Y有輸入和工作兩種模式。這里，我們把RAM X和RAM Y配置成乒乓結(jié)構(gòu)，當RAM X處于工作模式時，RAM Y處于輸入狀態(tài)。當一次64/256/1024點FFT/IFFT完成后，RAM X和RAM Y將自動切換到另一個狀態(tài)。這樣，輸入序列就可以連續(xù)地輸入到FFT/IFFT處理器中進行變換，以達到實時處理的要求。輸出結(jié)果存放在RAM Z中，可以由用戶讀出。
4 測試結(jié)果
這個電路采用Verilog HDL完成設(shè)計，采用Virtex-II XC2V250實現(xiàn)。使用Vilinx ISE4.2i完成整套流程，圖5是部分仿真波形（modelsim+sdf）。在系統(tǒng)時鐘為100MHz時，完成一次1024點復(fù)數(shù)FFT/IFFT需要12.8μs。相比之下，TI公司的TMS320C67（主頻167MHz）需要120μs，AD公司的ADSP21160（主頻100MHz）需要90μs。可見，基于FPGA的FFT/IFFT處理器由于其硬件上的并行性，速度遠遠快于一般的通用DSP。
5 結(jié)束語
FPGA具有成千上萬的查找表和觸發(fā)器，因此，F(xiàn)PGA平臺可以利用更低的成本達到此通用DSP更快的速度。采用FPGA技術(shù)，還可以獲得高性能，滿足成本要求，并享有快速有效地對新設(shè)計進行優(yōu)化的靈活性。針對這一特性，本文研制了一種基于并行算法的FFT/IFFT處理器，可以廣泛應(yīng)用在高速信號處理系統(tǒng)中。
參考文獻
1 W.R.Knight and R.Kaiser.A Simple Fiexed-Point Error Bound for the Fast Fourier Transform.IEEE Trans.Acoustics,Speech and Signal Proc.,Dec,1979 Vol.27,No.6:615～620
2 L.R.Rabiner and B.Gold.Theoty and Application of Digital Signal Processing.Prentice-Hall Inc.,Englewood Cliffs,New Jersey,USA,1975
3 M C Pease.Organization of Large Scale Fourier Process-ors.Journal of ACM.1969,16(3):474～482
4 Per Holmberg.采用FPGA創(chuàng)建高性能DSP應(yīng)用.電子產(chǎn)品世界,2001(7)
