基于FPGA流水線結構并行FFT的設計與實現

王英喆 ，杜 蓉

（1.北京大學 軟件與微電子學院，北京 100871；2.中科院國家空間中心 北京 100190）

離散傅里葉變換DFT在通信、控制、信號處理、圖像處理、生物信息學、計算物理、應用數學等領域中有著廣泛的應用[1]。FFT算法是作為DFT快速算法提出的,它將長序列的DFT分解為短序列的DFT,大大減少了運算量。FFT的FPGA實現同時具有軟件編程的靈活性和ASIC電路的快速性等優點，成為快速實時實現FFT的一種重要手段[2]。文章意在設計一種高速率高吞吐率的FFT處理器，以滿足實時處理要求。

1 數學模型

FFT的基本思想是利用旋轉因子的周期性、對稱性和可約性將一個長度為N的序列的DFT逐次分解為較短的DFT來計算，而總的運算次數比直接DFT運算要少得多，達到提高速度的目的。根據旋轉因子的周期性、對稱性和可約性，我們可以得到如式(1)的一系列有用結果[3-4]。

一般情況下，長度為N的有限長序列x(n)的DFT為：

根據公式(1)(2)得到的基2與基4計算公式如下：

2 結構說明

2.1 流水線結構

硬件結構實現FFT的常用形式有4種：遞歸結構，流水線結構，并行迭代結構和全并行結構[5]。設計采用流水線結構，流水線結構一般在FFT實現的每一級均采用一個運算單元，前一級算結果直接用于下一級運算而無需等到本級運算全部完成，因此，可提高運算速度。遞歸結構的運算的時間較長，并行迭代結構對數據存取帶寬要求很高，全并行結構資源消耗過大，均不適用。

2.2 并行處理

FFT作為時域和頻域轉換的基本運算，是數字頻譜分析的必要前提，超級的運算能力在雷達處理、觀測、跟蹤、定時定位處理、高速圖像處理、保密無線通訊和數字通信、濾波等的應用上極為強烈，而實時系統對FFT的運算速度要求更高[6]。提高FFT速度的一種有效解決方法是并行運算，如采用多個蝶形運算單元并行處理。綜上，設計選取流水結構，4路并行處理結構。

3 硬件設計

3.1 邏輯設計

FFT邏輯框架如圖1，為了構造高速率高吞吐量的FFT，設計4路并行輸入輸出，采用基4與基2混合FFT，FFT512采用基4蝶形算法，其余則采用基2蝶形算法。

圖1 邏輯框圖Fig.1 Logic diagram

流水結構的FFT處理器的基本結構如圖2所示。實際設 計由3個部分組成：運算單元、數據交換單元和重排單元。

圖2 FFT流水線結構Fig.2 Pipelined architecture of FFT

運算單元完成蝶形運算，是處理器的核心，其運算速度直接決定整個FFT處理器的速度。由于4組輸入數據同時進入蝶形運算，所以處理速度為串行的4倍。其中，每個蝶形單元均采用流水線技術設計。運算單元啟動后，每個周期處理4組數據，完成4輸入4輸出的FFT。

數據交換單元是處理器的關鍵，實現對前一級蝶形運算單元輸出數據的交換，以滿足下一級蝶形運算的配對需求。實現方法為每一級的輸入均采用順序輸入，內部用FIFO緩存數據，按照逆序形式配對數據，等待數據到來，將加法結果輸出，減法結果存至FIFO中，待加法結果輸出完畢，繼續輸出減法結果，如此輸出結果即為順序輸出。

數據重排單元負責對最終計算結果進行重新排序，以實現自然序數輸出。512點基4框架圖如圖3所示，在512基4運算完成后，輸出數據的順序并不是所需順序，需要進行調整，由輸入數據與輸入數據的地址特點發現，倒序RAM的讀地址即完成順序輸出。

3.2 時序設計

流水示意圖如圖4所示，詳細說明如下：

圖3 FFT基4框架圖Fig.3 Radix-4 framework of FFT

圖4 流水設計Fig.4 Pipeline design

FFT64模塊的5級流水：第1級，前64組輸入數據的實部、虛部均寄存在FIFO中，當第65組數據到來時，與FIFO 中寄存的第一組數據做蝶形運算，將相減的結果繼續存在FIFO中待用，相加運算將在第二級進行；第2級，前64個周期，做蝶形加法，結果記為add，第65個周期起，從FIFO中讀數給add；第3級，前64個周期，add賦給第一級緩存寄存器，第65個周期起，把add賦給乘法器的輸入端；第4級，前64個周期，把第一級緩存寄存器賦值給第二級緩存寄存器，第65個周期起，做乘法運算；第5級，前64個周期，把第二級緩存寄存器的值賦給輸出端，第65個周期起，把乘法器輸出累加的結果賦給輸出端；

FFT512模塊的6級流水：第1級，當輸入有效信號拉高時，將第一組輸入數據放入第一級緩存器中，寄存第二至四組數據，待接乘法器輸入端。同時，從rom中讀取旋轉因子；第2級，第一路緩存至第二級緩存中，其余三路做乘法運算；第3級，第一路緩存至第三級緩存中，其余三路做復數乘法的加法運算；第4級，四路數據均做緩存；第5級，做如圖3中的第一個蝶形運算。其中，乘以-j運算可以用顛倒相加來完成，如此可以節省乘法器資源；第6級，做如圖3中的第二個蝶形運算，同時將輸出有效信號拉高。

FFT32、FFT16、FFT8、FFT4、FFT2、FFT1 與 FFT_64 流 水原理一致，只是控制位數不同，其分別為 32、16、8、4、2、1。

4 驗證設計

Testbench是一種驗證手段，通常包含3個部分，激勵生成、待測設計、輸出校驗。針對設計搭建的testbench如圖5所示，從文件中讀取向量i_data_real、i_data_imag，經過FFT處理得到結果o_data_real、o_data_imag，并根據end信號將向量寫入相應文檔中，與正確結果進行比對。

圖5 Testbench示意圖Fig.5 Testbench diagram

5 仿真結果

ISE仿真波形如圖6所示，輸出文件經與MATLAB對比驗證正確。圖(1)為整體仿真波形，輸出有效信號拉高后，數據連續輸出。圖(2)為FFT512模塊局部仿真波形，輸入有效信號拉高后，第6個周期輸出有效，與分析的流水級數相吻合。

圖6 FFT仿真波形Fig.6 Simulation waveforms of FFT

6 綜合結果

綜合后得到資源利用情況如表1，我們發現，并行處理帶來面積的增大，如何在實際問題中平衡速度與面積尤為重要。

7 結束語

文章用FPGA實現了512點FFT處理器，采用Verilog硬件描述語言進行RTL級描述，并完成綜合、布局布線。經過ISE仿真，結果與MATLAB仿真輸出結果吻合。處理器先采用時域基2蝶形算法，后采用時域基4蝶形算法，并行處理4個蝶形運算單元，并同時采用流水線結構，大幅度提高了處理器速度，可進行實時FFT運算。在設計中用FIFO存儲中間數據，并將旋轉因子固定為乘法器IP的常數系數，以進一步提高處理器的速度。因為采用并行結構，所以FPGA硬件資源消耗較多，系統功耗也相應增大，如何根據系統實際需求找到速度與資源的平衡至關重要。

表1 FPGA資源利用表Tab.1 FPGA resource utilization table

[1]陸旦前，陳建平，陳曉勇.FFT算法的一種FPGA設計[J].現代電子技術，2007(6):178-187.LU Dan-qian,CHEN Jian-ping,CHEN Xiao-yong.A FPGA Design of FFT Algorithm [J].Modern ElectronicTechnique,2007(6):178-187.

[2]姚國珍.基于MegaCore的FFT模塊在FPGA上的實現[J].山西電子技術，2008(2):53-56.YAO Guozhen.The Implementation of FFT Module in FPGA Based on MegaCore [J].Shanxi Electronic Technology,2008(2):53-56.

[3]高亞軍.基于FPGA的數字信號處理[M].北京：電子工業出版社，2012.

[4]周景龍.基于高速FFT結構的頻域抗干擾算法的FPGA實現[J].微電子學與計算機，2014.31(5):32-35.ZHOU Jing-long.A FPGA Implementation of frequency-domain anti-jamming algorithm based on a structure of highspeed FFT[J].Microelectronics&computer,2014,31(5):32-35.

[5]石長振，楊雪，王貞松.高性能并行FFT處理器的設計與實現[J].計算機工程，2012,38(2):242-247.SHI Chang-zhen,YANG Xue,WANG Zhen-song.Design and realization of high performance parallel FFT processor[J].Computer Engineering,2012,38(2):242-247.

[6]劉萬明，王魯平，楊衛平.基于FPGA的高速定點FFT處理器的設計[J].現代電子技術，2007(22):41-45.LIU Wan-ming,WANG Lu-ping,YANG Wei-ping.Design of high speed fixed-point FFT processor based on FPGA[J].Modern ElectronicTechnique,2007(22):41-45.