李大習(xí)

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

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

1 原理分析

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

1.1 基2 算法基本原理

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

則可將DFT 化為

1.2 基4 算法基本原理

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

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

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

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

圖1 FFT 算法IP 核功能組成

如圖1 所示，該IP 主要包括RAM、ROM、地址產(chǎn)生模塊、移位模塊、選擇數(shù)據(jù)排序模塊、可配置蝶形運(yùn)算單元、精度調(diào)整模塊和輸出數(shù)據(jù)排序模塊，Din_R 和Din_I 是FFT 輸入數(shù)據(jù)的實(shí)部和虛部，Dout_R 和Dout_I 是FFT 變換結(jié)果的實(shí)部和虛部。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 蝶形運(yùn)算兩種配置方式，供用戶選擇。輸入數(shù)據(jù)實(shí)部和虛部分開存儲，需4 個RAM，為實(shí)現(xiàn)對連續(xù)流輸入可連續(xù)流輸出，其模塊構(gòu)成如圖2 所示。

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

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

2.2 可配置蝶形單元模塊

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

圖3 可配置蝶形運(yùn)算模塊圖

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

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

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

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

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

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

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

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

圖7 200 MHz 4 096 點(diǎn)基4FFT 運(yùn)算仿真結(jié)果

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

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

表1 FFT 運(yùn)算效率比較

4 結(jié)束語

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

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

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

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

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

［5］ 李仕專，李維濤，姜全賢，等.一種基于并行計算的快速FFT IP 核設(shè)計［J］.計算機(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］ 李欣，劉峰，龍騰.定點(diǎn)FFT 在TS201 上的高效實(shí)現(xiàn)［J］.北京理工大學(xué)學(xué)報，2010，30(1):88－91.

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