基於FPGA 的高速實時FFT處理器設計

    離散傅里葉變換(DFT) 是數字譜分析必需的變換工具。完成N 點DFT 運算約需N² 次乘法和N^(N-1) 次加法,當N 較大時,運算量非常大,使其實際應用受到極大的限制。快速傅里葉變換(FFT) 採用遞歸型演算法,利用旋轉因子的周期性和對稱性,將長序列DFT 分解為短序列DFT ,使總運算量減小1～2 個數量級,從而大大加快了運算速度。FFT 和快速傅里葉逆變換(IFFT) 在雷達信號處理、圖像處理、譜估計等領域有廣泛的應用。目前,高速FFT 的實現方案總體上分為基於專用集成電路(ASIC) 、現場可編程門陣列(FPGA) 、數字信號處理(DSP) 和通用處理機(GPP) 等幾種。從FFT 的處理速度、面積和功耗方面比較,基於ASIC 實現的性能最好,基於FPGA 實現的次之。因此,在FFT 處理器的小規模應用場合,採用FPGA可以獲得較高的性價比和靈活性。本設計主要應用於雷達系統的寬頻信號處理和成像。

1 FFT演算法分析
    從FFT 演算法的複雜性來看,基4 演算法比基2 演算法減少約20 %的運算量。從硬體實現的難易程度來看,基4 演算法具有比分裂基和更高基較易控制的特點。
    FFT 演算法有按時間抽取(DIT) 和按頻率抽取(DIF) 兩種形式,其區別在於輸入數據和旋轉因子乘、加的順序不同。在DIT 中,蝶形運算的輸入數據和旋轉因子是先乘后加,而在DIF 中,則是先加后乘,兩者並沒有實質區別。因此,本設計採用DIF 的基4 FFT 演算法。
一個N 點序列x(n) 的DFT 定義為:
 
式中：
假定N = 4 ^m ,式(1) 先按時域前、後分開,可寫成:
 
　式(2) 可進一步改寫為:
 
　在頻域X(k) 上將k 分解後進行抽取,分別令k 等於4r,4r+2,4r+1,4r+3(r=0,1,……,N/4-1) 。式(3) 可寫為:
 
　分別令:
 
　式(4) 可進一步簡化為:
 
　由式(5) 可見,完成一個基4 蝶形運算需要進行8個複數加和3 個複數乘,也就是22 個實數加和12 個實數乘。

2 高性能FPGA 的特點
    本設計採用Xilinx 公司2001 年推出的Virtex2 II系列FPGA ,它除了內含大量可配置邏輯模塊(CLB) 、輸入輸出模塊(IOB) 邏輯資源和布線資源外,還具有以下特點:
a) 內部時鐘速度可達420 MHz ,且具有豐富的全局時鐘資源和數字時鐘管理模塊(DCM) ,可以獲得較小的時鐘扭曲。
c) 具有為算術運算而特別設計的硬體結構,如18bit ×18 bit 嵌入式硬體乘法器、快速進位鏈等。
c) 包含豐富的模塊化RAM。
    這些特點簡化了邏輯設計,縮短了設計時間,為實現高速、實時FFT 處理提供了極大的便利。

3 FFT演算法的硬體實現
3.1 系統設計
    從運算速度和硬體實現兩方面綜合考慮,本設計系統框架採用多級串列的同步流水結構,如圖1 所示。
 
　與僅用1 個蝶算單元反覆運算的處理方案相比,流水線處理方式可以獲得更快的運算速度;與并行或陣列處理方式相比,這種結構可降低控制複雜度,節省硬體資源,獲得較小的面積和功耗。
    串列級聯的各級結構除了輸入、輸出級僅在溢出檢測和移位控制上有所不同外,其餘與中間各級的結構完全相同。圖2 給出了中間單級的結構框圖。
 
　
3.2 　運算數據的存取
    由於採用多級串列的流水線(pipeline) 結構,每級的數據輸入、運算和數據輸出是同時進行的。因此,數據的存取可採用單口或雙口RAM ,實現乒乓操作,原理框圖如圖3 所示。
 
　  通過輸入和輸出數據選擇器按節拍相互配合的切換,將經過雙埠RAM(DPRAM) 緩衝的數據流不停頓地送到數據流運算處理模塊,可實現數據的無縫緩衝和處理。
    每級蝶形運算的輸入數據,其地址按一定規律存放在該級ROM 中, 由地址發生器發送出來。每級DPRAM 有一個寫地址和一個讀地址,后一級RAM的寫地址和前一級RAM 的讀地址相同,使得每一級的輸入數據均按自然順序存儲。另外,為節省存儲資源,也可利用蝶形單元同址運算的特點,原址讀出原址寫入同一RAM 進行存儲。
    由上述FFT 的演算法分析可知,在點數N 確定后,一個基4 蝶形運算單元中3 個旋轉因子Wⁿ_N、W²ⁿ_N 和W³ⁿ_N 的值均由n 值確定。n 值的大小由該蝶形運算單元所在的級數、該級的組數及其在該組蝶形運算單元中的具體位置決定。同樣,各級旋轉因子也採用對ROM 進行查表的方式得到。此外,基4 蝶形運算的輸入和輸出均為并行方式,所需的轉換可用串/並和並/串轉換模塊來完成。

3.3 溢出檢測和控制
    根據運算數據的不同表示形式,FFT 運算可分為浮點、塊浮點和定點3 種類型。在定點運算中,需要對輸入進行一定比例的衰減,以防止運算過程的溢出,結果顯然影響到運算精度。採用浮點運算雖然不存在溢出問題,但是電路複雜性顯著增加。
    本設計採用的塊浮點FFT 處理,在每級的輸入數據端,對符號位進行擴充;在每級的輸出數據端,對最高几位進行檢測,以確定是否存在溢出以及溢出的位數,再作出相應的移位處理。這樣,既保證了運算過程的不溢出,又使得硬體結構和控制比浮點運算簡單。
    在一個基4 蝶形運算單元中,由於旋轉因子的實部和虛部的絕對值總是不大於1 ,故乘法運算不會引起輸出數據位數的增加,而輸入數據的加減也最多只有兩次進位。因此,若輸入數據的實部、虛部分別為N 位字長,為防止溢出, 輸出數據要用N+2 位字長表示。溢出檢測可採用狀態機的描述形式對輸出數據的高3 位進行比較,得到溢出控制位,以決定下一級作何種移位處理,移位輸出的N 位字長的數據作為下一級蝶形運算的輸入。同時,對各級的溢出控制位進行求和運算,得到一次N 點FFT 處理結果的塊浮點指數。

3.4 運算數據的同步
    為了保證運算速度,在每級的蝶形運算中都插入了pipeline ,對乘法和加法的中間結果進行寄存。因此,存在數據同步的問題,包括每級蝶形運算的輸入數據和旋轉因子的對齊、蝶形運算中不含旋轉因子的輸出項和包含與旋轉因子相乘的輸出項的對齊,以及不同級之間輸入數據的同步。解決辦法是:前兩種情況,可根據插入的pipeline 個數,插入同樣數量的DFF 延遲對齊;后一種情況,則需通過地址控制發生器發送的地址作相應的延遲處理。

3.5 輸出整序
    由於在設計中採用的是順序輸入、倒序輸出,因此,必須對輸出作整序操作。具體說來,最後一級輸出到RAM 的寫地址要按四進位數作倒序排列,而不再像中間級那樣與前一級DPRAM 的讀地址相同。

3.6 用FFT實現IFFT
    FFT 模塊設計完成後,再要實現IFFT ,無論是在演算法還是硬體實現上都相對比較容易。具體做法是:在輸入端,對輸入的頻域數據取共軛後進行FFT 運算;在輸出端,對輸出數據也作共軛后再除以點數N ,即可得到需要的時域輸出。

4 結束語
    本設計採用了多級串列的同步流水線處理結構,在對各功能模塊進行明確的劃分后,全部採用Verilog HDL 描述。在設計時例化了FPGA 內部的模塊化RAM 和18 bit ×18 bit 的硬體乘法器。綜合工具為Synplicity 公司的Synplify Pro ,模擬工具為Cadence 公司的NC2Sim ,布局布線為Xilinx 公司的ISE。在完成綜合、布局布線和時序模擬后,將位流文件下載到Xilinx 公司的Virtex2 II器件中。經測試,在外部時鐘為100 MHz 時, 完成1024 點、16 位複數點的塊浮點FFT 處理時間為10.2 μs ,處理速度達到實時要求。實踐證明,隨著可編程器件性能的增強,用FPGA 高速、實時地實現複雜的DSP 演算法是完全可行的。當然,在FFT 處理器的大規模應用場合,需要轉向基於ASIC 實現時,本設計也有可借鑒之處。