李大習

(江蘇自動化研究所 計算機事業(yè)部，江蘇 連云港 222061)

在現(xiàn)代聲納、雷達、通信、圖像處理等領(lǐng)域中，數(shù)字信號處理系統(tǒng)經(jīng)常要進行高速、高精度的FFT 運算。現(xiàn)場可編程邏輯陣列(FPGA)是一種可定制集成電路，具有面向數(shù)字信號處理算法的物理結(jié)構(gòu)。用FPGA實現(xiàn)FFT 處理器具有硬件系統(tǒng)簡單、功耗低的優(yōu)點，同時具有開發(fā)時間較短、成本較低的優(yōu)勢?；贔PGA實現(xiàn)的數(shù)字信號處理系統(tǒng)具有較高的實時性和嵌入性，并能方便地實現(xiàn)系統(tǒng)集成與功能擴展［1］?；贔PGA 的硬件實現(xiàn)FFT 通常有兩種方法:(1)并行方法，其采用多個蝶形處理器并行運算，能對較高的數(shù)據(jù)采樣率進行運算，但其硬件規(guī)模較大，當在FPGA 上要實現(xiàn)較大點數(shù)的FFT 時較為困難。(2)串行方法，采用一個蝶形處理器完成運算，使用的邏輯資源較少，但運算速度較慢［2］。本文在串行方法的基礎(chǔ)上實現(xiàn)了一種在FPGA 上實現(xiàn)的可配置FFT IP 核，具有輸入點數(shù)可配置(實現(xiàn)0 ～4 096 點自由配置)、數(shù)據(jù)位寬可配置、分解基可配置的特性。

1 原理分析

自從基2 快速算法出現(xiàn)以來，人們?nèi)栽诓粩鄬で蟾斓乃惴ā；? FFT 算法比最初的基2 FFT 算法更快，但從理論上講，用較大的基數(shù)還可進一步減少運算次數(shù)，但要以程序(或硬件)變得更復雜為代價［3］。提高FFT 處理速度的4 個主要技術(shù)途徑是采用流水線結(jié)構(gòu)、并行運算、增加蝶形處理單元數(shù)目和高基數(shù)結(jié)構(gòu)［4］。

1.1 基2 算法基本原理

點數(shù)N 是2 的整數(shù)次冪，將x(n)先按n 的奇偶分成兩組

則可將DFT 化為

1.2 基4 算法基本原理

與基2 算法類似，對于N 點有限長序列x(n)的DFT 按照時域分解展開有［5］

對式(3)進行變量替換得到

2 可配置FFT IP 核硬件結(jié)構(gòu)

現(xiàn)有的FFT IP 核在硬件實現(xiàn)時不具備并行度可配置能力，只提供全循環(huán)、全流水、循環(huán)展開與流水結(jié)合等形式下的某種特定實現(xiàn)［6］，可重用性較差，難以適應(yīng)不同的計算吞吐量和對計算資源和計算時間的需求［7－8］?？膳渲肍FT IP 核技術(shù)實現(xiàn)FFT 算法流水、循環(huán)等并行化參數(shù)的可配置問題，兼顧FFT 轉(zhuǎn)換點數(shù)、輸入輸出數(shù)據(jù)位寬、蝶形運算基數(shù)、輸入輸出FIFO 深度的可配置，滿足不同應(yīng)用條件下IP 復用的需求，適應(yīng)各種環(huán)境和數(shù)據(jù)吞吐量的FFT 運算［9］?？膳渲肍FT IP 核功能組成如圖1 所示。

圖1 FFT 算法IP 核功能組成

如圖1 所示，該IP 主要包括RAM、ROM、地址產(chǎn)生模塊、移位模塊、選擇數(shù)據(jù)排序模塊、可配置蝶形運算單元、精度調(diào)整模塊和輸出數(shù)據(jù)排序模塊，Din_R 和Din_I 是FFT 輸入數(shù)據(jù)的實部和虛部，Dout_R 和Dout_I 是FFT 變換結(jié)果的實部和虛部。RAM1 和RAM2 存儲了FFT 迭代過程中的輸入數(shù)據(jù)，RAM3 和RAM4 存儲了FFT 迭代過程中的計算結(jié)果，RAM1 和RAM2、RAM3 和RAM4 均為乒乓結(jié)構(gòu)。地址產(chǎn)生模塊主要產(chǎn)生向RAM 寫入數(shù)據(jù)和從RAM 讀出數(shù)據(jù)的地址。ROM 中存儲了FFT 需要的旋轉(zhuǎn)因子。

2.1 IP 核整體方案

設(shè)計可配置FFT 處理，其整體結(jié)構(gòu)如圖2 所示，設(shè)計采用基2 蝶形和基4 蝶形運算兩種配置方式，供用戶選擇。輸入數(shù)據(jù)實部和虛部分開存儲，需4 個RAM，為實現(xiàn)對連續(xù)流輸入可連續(xù)流輸出，其模塊構(gòu)成如圖2 所示。

圖2 FFT IP 核構(gòu)成圖

如圖2 所示，外部輸入數(shù)據(jù)的實數(shù)部分Din_R、虛數(shù)部分Din_I，以及輸入數(shù)據(jù)的地址信號ADR，首先進入RAM_ADDR 單元，選擇合適的時鐘周期將不同點數(shù)的原始數(shù)據(jù)送入RAM 單元，當輸入數(shù)據(jù)的實數(shù)和虛數(shù)以及其地址準備好的時候，RDY 輸出1。BIT_SFT單元完成輸入數(shù)據(jù)地址的移位變換，實現(xiàn)奇偶分離。當數(shù)據(jù)地址準備好時，RDY 輸出1，當RAM_ADDR 或BIT_SFT 這兩個單元中的一個單元準備好時，便可觸發(fā)RAM 單元，將外部數(shù)據(jù)寫入到RAM 的指定地址。RAM 中的數(shù)據(jù)符合可配置點數(shù)要求后，進入NUM_IN單元，其中輸出的數(shù)據(jù)DOR/DOI 就是符合基2 蝶形或基4 蝶形運算的數(shù)據(jù)順序。這些原始數(shù)據(jù)進入蝶形運算單元BUTTERFLY，蝶形單元通過U_SELECT 單元選擇蝶形運算的分解基，實現(xiàn)基2 蝶形運算、基4 蝶形運算的可配置功能。其中R4_FFT 是基4 蝶形運算單元，R2_FFT 是基2 蝶形運算單元，蝶形運算過程中所需的旋轉(zhuǎn)因子存儲在ROM_RAT 單元中，根據(jù)選擇不同分解基的蝶形運算，BUTTERFLY 單元產(chǎn)生相應(yīng)的地址，選擇其計算過程中的旋轉(zhuǎn)因子。當?shù)芜\算完成后，結(jié)果數(shù)據(jù)進入U_CNORM 單元，進行順序調(diào)整和精度處理;其中PR 信號是用戶指定的精度信號，PR［1∶0］可提供3 種精度，OVF 信號是數(shù)據(jù)溢出信號，若置1 表明FFT 結(jié)果數(shù)據(jù)超出了表示范圍，則要按照截位處理以保證數(shù)據(jù)準確。當數(shù)據(jù)輸入完成后，結(jié)果數(shù)據(jù)進入NUM_OUT 單元，由于DIT 算法輸出結(jié)果以倒序形式輸出，所有需要NUM_OUT 進行地址調(diào)整，F(xiàn)FT 變換結(jié)束后的結(jié)果實數(shù)部分Dout_R，虛數(shù)部分是Dout_I，地址信號是R_ADDR，以正確的順序和形式輸出。

2.2 可配置蝶形單元模塊

在FFT IP 核的蝶形運算單元設(shè)計中，蝶形單元的運算過程:第一個時鐘周期是將下結(jié)點與旋轉(zhuǎn)因子復乘的實數(shù)乘法進行計算;第二個時鐘周期是將復乘中的實數(shù)進行加減運算;在第三個時鐘周期是計算復乘結(jié)果與上結(jié)點的加減運算，即將蝶形運算單元的結(jié)果輸出。可配置蝶形運算通過在基2 和基4 兩種分解基之間切換來實現(xiàn)，其模塊圖如圖3 所示。

圖3 可配置蝶形運算模塊圖

如圖3 所示，數(shù)據(jù)輸入時能信號EN 信號置1，則整個蝶形運算單元的數(shù)據(jù)輸入模塊NUM_IN、旋轉(zhuǎn)因子模塊ROM_RAT、分解基選擇模塊U_SELECT 進入使能狀態(tài);START 信號置1，則分解基選擇單元U_SELECT 模塊開始進入狀態(tài)機。根據(jù)用戶設(shè)置，如果選擇基2 算法蝶形運算單元，則將輸入數(shù)據(jù)的實部和虛部送入R2_FFT 模塊;如果選擇基4 算法蝶形運算單元，則將輸入數(shù)據(jù)的實部和虛部送入R4_FFT 模塊;如果選擇混合基，則需要在狀態(tài)機中加入判斷條件，準確控制分支。當?shù)芜\算完成時，F(xiàn)FT 運算結(jié)果數(shù)據(jù)的實數(shù)部分Dout_R［nb+2∶0］，虛數(shù)部分Dout_I［nb+2∶0］比輸入數(shù)據(jù)的位數(shù)［nb∶0］擴展了3 位，用于精度調(diào)整模塊進行精度控制。

蝶形運算的旋轉(zhuǎn)因子存儲在ROM_RAT 中，其中存儲了基4 運算和基2 運算的旋轉(zhuǎn)因子，實部和虛部分開存儲，通過外部信號EN 對其使能，為控制ROM存儲空間的占用，不同分解基的旋轉(zhuǎn)因子可公用，通過地址信號ADR 選取控制。

3 仿真、綜合結(jié)果分析與驗證

將設(shè)計的IP 核進行基于ModelSim 的仿真，設(shè)置時鐘頻率為200 MHz，數(shù)據(jù)位寬為36 位，在基2 和基4兩種分解基下，分析1 024 點和4 096 點的運算效率，其仿真圖像如下所示。

圖4 200 MHz 1 024 點基2FFT 運算仿真結(jié)果

圖5 200 MHz 1 024 點基4FFT 運算仿真結(jié)果

圖4 是1 024 點的基2 算法仿真結(jié)果，在這種算法下完成數(shù)據(jù)錄入的時間點為113.1 μs，完成結(jié)果輸出的時間點為123.4 μs，運算時間為10.3 μs。圖5 是1 024點的基4 算法仿真結(jié)果，在該種算法下完成數(shù)據(jù)錄入的時間點51.3 μs，完成結(jié)果輸出的時間點是61.6 μs，運算時間為8.3 μs。

圖6 200 MHz 4 096 點基2FFT 運算仿真結(jié)果

圖7 200 MHz 4 096 點基4FFT 運算仿真結(jié)果

圖6 是4 096 點的基2 算法仿真結(jié)果，在這種算法下完成數(shù)據(jù)錄入的時間點533.1 μs，完成結(jié)果輸出的時間點是574.1 μs，運算時間為40 μs。圖7 是4096點的基4 算法仿真結(jié)果，在該種算法下完成數(shù)據(jù)錄入的時間點為245.7 μs，完成結(jié)果輸出的時間點是286.9 μs，運算時間為41.2 μs。

板級驗證選用Xilinx 公司的Virtex－5 xc5vfx70t器件進行綜合、布局布線和時序分析。將得到的數(shù)據(jù)與其他設(shè)計實現(xiàn)進行比較，其消耗的資源，以及在200 MHz 時鐘情況下不同點數(shù)的FFT 處理器進行一次處理需要的時間，與文獻［10］換算后得到的數(shù)值對比如表1 所示。

表1 FFT 運算效率比較

4 結(jié)束語

本文設(shè)計的可配置FFT IP 核具有靈活性強、容易擴展和設(shè)計可復用的特點，實現(xiàn)分解基可配置、位寬可配置、輸入輸出點數(shù)可配置。從驗證結(jié)果可以看出，本文數(shù)據(jù)的可配置IP 核具有結(jié)構(gòu)簡單及占用硬件資源適當?shù)奶攸c，在FPGA 中以實現(xiàn)高速數(shù)字信號處理，在處理速度和靈活性方面更有優(yōu)勢。隨著處理點數(shù)的增加，其優(yōu)越性將更加明顯。

［1］ 張燕燕，洪龍.Windows 環(huán)境下FFT 多核并行算法的設(shè)計實現(xiàn)［J］.計算機技術(shù)與發(fā)展，2010(9):74－77.

［2］ 胡廣書.數(shù)字信號處理［M］.北京:清華大學出版社，2003.

［3］ 肖江，胡柯良，鄧元勇.基于CUDA 的矩陣乘法和FFT 性能測試［J］.計算機工程，2009，35(10):7－10.

［4］ 張犁，李雙飛，石光明，等.一種FFT 并行處理機的設(shè)計與實現(xiàn)［J］.西安電子科技大學學報:自然科學版，2010，37(4):630－635.

［5］ 李仕專，李維濤，姜全賢，等.一種基于并行計算的快速FFT IP 核設(shè)計［J］.計算機與數(shù)字工程，2010，38(4):139－141.

［6］ 萬紅星，陳禾，韓月秋.一種高速并行FFT 處理器的VLSI結(jié)構(gòu)設(shè)計［J］.電子技術(shù)應(yīng)用，2004(12):45－48.

［7］ GHISSONI S，COSTA E，MONTEIRO J，et al.Combination of constant matrix multiplication and gate－level approaches for area and power efficient hybrid radix－2 dit/fft realization［C］.2011 18th IEEE International Conference on Electronics，Circuits and Systems(ICECS)，2011:567－570.

［8］ MATEUS B F，EDUARDO A，César da Costa，et al.Martins design of power efficient butterflies from Radix－2 DIT FFT using adder compressors with a new XOR gate topology［J］.Analog Integrated Circuits and Signal Processing，2012，73(3):945－954.

［9］ 李欣，劉峰，龍騰.定點FFT 在TS201 上的高效實現(xiàn)［J］.北京理工大學學報，2010，30(1):88－91.

［10］齊華，李勇，郝重陽.一種塊遞推實時FFT 算法模塊設(shè)計與實現(xiàn)［J］.西北工業(yè)大學學報，2009，27(2):240－244.