何健標(biāo)

(深圳職業(yè)技術(shù)學(xué)院電信學(xué)院通信系　深圳　518055)

?

基于FPGA的可配置FFT處理器*

何健標(biāo)

(深圳職業(yè)技術(shù)學(xué)院電信學(xué)院通信系深圳518055)

摘要FFT是常用的數(shù)字信號處理方法，論文提出了一種基于FPGA平臺的可配置FFT處理器設(shè)計方法。該方法采用基2多路延時轉(zhuǎn)接器的流水線結(jié)構(gòu)，由L個可配置的基2運算模塊級聯(lián)組成，不同位置的基2運算模塊根據(jù)位置配置信息控制數(shù)據(jù)緩存的讀取地址實現(xiàn)基2蝶形運算。FFT處理器基于Verilog語言進行模塊化設(shè)計，并在Altera公司的Cyclone IV器件上實現(xiàn)。

關(guān)鍵詞快速傅里葉變換; 多路延時轉(zhuǎn)接器; 流水線; 現(xiàn)場可編程邏輯門陣列

Class NumberTP391

1引言

快速傅立葉變換(FFT)是離散傅立葉變換(DFT)的快速實現(xiàn)方法，廣泛用于功率譜估計[1]、頻譜分析[2]、相關(guān)卷積[3]、圖像數(shù)據(jù)壓縮[4]和多載波調(diào)制解調(diào)[5]等數(shù)字信號處理過程。

目前FFT的實現(xiàn)可采用專用集成電路(Asic)、數(shù)字信號處理器(DSP)[6]和現(xiàn)場可編程邏輯門陣列(FPGA)[7]三種方式，其中Asic方式成本低性能好，但缺乏靈活性，無法針對特定應(yīng)用進行配置；DSP方式實現(xiàn)靈活，但其軟件實現(xiàn)的方式限于串行處理架構(gòu)，不適合高速FFT運算的應(yīng)用；在FPGA芯片上實現(xiàn)FFT運算，可采用基于流水線的高速硬件電路保證計算處理能力，同時通過硬件可編程特性保證設(shè)計的靈活性。

基于FPGA實現(xiàn)FFT運算的硬件結(jié)構(gòu)包括流水線結(jié)構(gòu)、遞歸結(jié)構(gòu)以及全并行結(jié)構(gòu)[8]。遞歸結(jié)構(gòu)所占硬件資源最少，但只有一個運算單元，實時性最差；全并行結(jié)構(gòu)處理速度最快，但硬件資源開銷太大，一般極少采用；流水線結(jié)構(gòu)一般在FFT運算的每一級采用一個運算單元，前一級運算結(jié)果可以直接用于下一級運算，實時性較好且硬件資源的開銷也適中。本文采用流水線結(jié)構(gòu)和基2時間抽取方法實現(xiàn)了一個可配置的FFT處理器。

2基2算法原理

對于時域信號序列x(n)，其N點離散傅立葉變換公式為

(1)

其中X[k]是x(n)對應(yīng)的頻域序列，WN被稱為旋轉(zhuǎn)因子，WN有以下重要性質(zhì):

(2)

當(dāng)點數(shù)N是2的整數(shù)次冪時，對式(1)按基2時域抽取，可得

X[k] =∑N-1n=0x(n)·WknN=∑N/2-1l=0x(2l)·W2lkN

(3)

根據(jù)旋轉(zhuǎn)因子的定義，有:

(4)

為便于描述，令：

(5)

對于0≤k

X[k] =∑N/2-1n=0xeven(n)·WknN/2+∑N/2-1n=0xodd(n)

(6)

對于N/2≤k

X[k] =X[g+N/2]=∑N-1n=0x(n)·W(g+N/2)nN

(7)

將式(6)代入，有:

X[k] =∑N/2-1n=0xeven(n)·WknN/2-∑N/2-1n=0xodd(n)

(8)

顯然，時域信號序列x(n)的N點離散傅立葉變換可以根據(jù)式(6)和式(8)分解成時域奇數(shù)序列xodd(n)和時域偶數(shù)序列xeven(n)的N/2點離散傅立葉變換Xodd[k]和Xeven[k]。依據(jù)類似方法，子序列xodd(n)和xeven(n)還可以繼續(xù)按奇偶序列拆分計算，依次分解后，序列x(n)的N點離散傅立葉變換計算過程可以拆分成多個2點DFT運算過程的組合，這就是基2FFT算法的分解計算過程(圖1是8點FFT分解算法圖)。

圖1　8點FFT分解算法圖

3實現(xiàn)結(jié)構(gòu)

流水線結(jié)構(gòu)一般采用FFT處理器串行輸入數(shù)據(jù)采樣率作為整個電路模塊的時鐘，因此對于N點FFT而言，基2運算模塊在一幀F(xiàn)FT數(shù)據(jù)周期內(nèi)有N個電路時鐘周期，可以計算N次基2蝶形計算，因此FFT處理器的基2蝶形運算器的數(shù)量L可得:

L=(Nlog2N)/N=log2N

(9)

整個FFT處理器由L個可配置基2運算模塊級聯(lián)組成(如圖2)，每個基2運算模塊以串行輸入數(shù)據(jù)采樣率作為電路始終，在N個時鐘周期內(nèi)可完成N次基2蝶形運算。對于長度可配置的FFT處理器[9]，可配置基2運算模塊的數(shù)量靈活可調(diào)，為了便于電路實現(xiàn)靈活可配置的功能，基2運算模塊以基2蝶形計算單元為核心，包括獨立的數(shù)據(jù)緩存模塊和旋轉(zhuǎn)因子合成模塊，不同位置的基2運算模塊通過位置參數(shù)進行配置。

圖2　基于流水線結(jié)構(gòu)的FFT處理器實現(xiàn)結(jié)構(gòu)

4可配置基2運算模塊

FFT處理器的流水線實現(xiàn)結(jié)構(gòu)主要包括: 1) 單路延時轉(zhuǎn)接器結(jié)(Single-path Delay Commutator,SDC); 2) 多路延時轉(zhuǎn)接器結(jié)構(gòu)(Multi-path Delay Commutator,MDC); 3) 單路延時反饋轉(zhuǎn)接器結(jié)構(gòu)(Single-path Delay Feedback,SDF)[10]。本文采用基2的MDC(R2MDC)結(jié)構(gòu)(如圖3所示)，整個基2運算模塊分為緩存、控制和計算三部分。

圖3　可配置的基2運算模塊

1) 緩存部分是四個大小容量一樣的雙口RAM作為輸入數(shù)據(jù)緩存，上述雙口RAM分為2組緩存，每組2個雙口RAM，對應(yīng)于R2MDC結(jié)構(gòu)并行輸入的一對輸入數(shù)據(jù)。2組緩存以乒乓的工作方式輪流存儲上一級基2運算模塊輸出的計算結(jié)果，當(dāng)A組緩存處于輸入數(shù)據(jù)緩存模式時，B組緩存則處于計算模式，在控制模塊的操控下將B組緩存內(nèi)上一級計算結(jié)果按要求調(diào)整順序然后送入計算模塊；當(dāng)A組緩存完成一幀數(shù)據(jù)的輸入后(與此同時B組緩存內(nèi)的所有數(shù)據(jù)也根據(jù)控制信號送入計算模塊)將轉(zhuǎn)入計算模式，在控制模塊的操控下按照特定的時序要求輸出緩存好的數(shù)據(jù)，與此同時B組緩存則轉(zhuǎn)入緩存模式，開始保存上一級基2運算模塊的第二幀計算結(jié)果。

2) 控制部分是基2運算模塊的靈魂，負責(zé)輸入數(shù)據(jù)緩存的地址控制和旋轉(zhuǎn)因子的生成。其中輸入雙口RAM的地址控制包括A/B組緩存寫入地址的控制和讀取地址的控制，其中輸入寫入緩存采用依次順序?qū)懭氲姆绞?，與基2運算模塊所處的位置無關(guān)，地址發(fā)生器是一個計數(shù)器；而輸入緩存的數(shù)據(jù)讀取與基2運算模塊的位置信息有關(guān)。FFT處理器采用模塊結(jié)構(gòu)化設(shè)計，每一級基2運算模塊的電路結(jié)構(gòu)都是一樣的，不同位置的基2運算模塊的位置信息通過位置參數(shù)配置給電路，讀取地址產(chǎn)生器根據(jù)位置參數(shù)生成雙口RAM的讀取地址，從而實現(xiàn)緩存數(shù)據(jù)的重新排序。控制部分的另一功能是旋轉(zhuǎn)因子生成，所有的旋轉(zhuǎn)因子都保存在FPGA片內(nèi)ROM中，但不同位置的基2運算模塊需要的旋轉(zhuǎn)因子序列是不一樣的，而旋轉(zhuǎn)因子ROM的地址控制器根據(jù)位置參數(shù)的配置不同的地址步進，從而實現(xiàn)旋轉(zhuǎn)因子序列的生成。

3) 計算部分執(zhí)行基本的基2蝶形運算過程，該模塊由延遲器、乘法器、加法器和減法器構(gòu)成，并行輸入數(shù)據(jù)從輸入緩存讀取，旋轉(zhuǎn)因子從旋轉(zhuǎn)因子ROM讀取，可以并行計算基2蝶形運算的兩個輸出結(jié)果。在控制模塊根據(jù)位置信息的操控下，上一級基2運算模塊的一幀的輸出(共計N個數(shù)據(jù))，經(jīng)過重新排序后，N個數(shù)據(jù)以2個數(shù)據(jù)一組依次送入計算模塊，經(jīng)過計算模塊以流水線方式計算N/2組數(shù)據(jù)后，本級基2運算模塊的一幀計算結(jié)果也依次送入下一級的基2運算模塊。

根據(jù)上述方法本文采用Verilog-HDL語言設(shè)計了一個1024點基2-FFT處理器，該處理器采用定點16bit數(shù)據(jù)量化，在Altera公司的Cyclone Ⅳ系列器件Ep4ce15f17c8n上綜合實現(xiàn)，通過QuartusⅡ仿真顯示，該FFT處理器的運算結(jié)果與真實值基本相同，計算誤差小于0.8%。整個處理器的處理時延為5120個時鐘周期。

5結(jié)語

本文采用多級流水線結(jié)構(gòu)設(shè)計實現(xiàn)了基于FPGA的FFT處理器。該處理器采用結(jié)構(gòu)化的模塊設(shè)計，由log2N個可配置基2運算模塊級聯(lián)而成，上述基2運算模塊可根據(jù)具體位置通過位置參數(shù)靈活配置，整個設(shè)計使用簡單、設(shè)計靈活的特點。通過Altera公司的QuartusⅡ軟件仿真和Cyclone4硬件平臺測試顯示，該處理器的工作頻率高于100MHz，支持?jǐn)?shù)據(jù)吞吐率達100MBaud，可以滿足絕大多數(shù)信號處理系統(tǒng)的實時處理要求。

參 考 文 獻

[1] 李春林,伍勇.基于FFT與自相關(guān)函數(shù)的快速功率譜估計方法[J].艦船電子工程，2011(31)：92-95.

[2] 江煒寧.數(shù)字下變頻FFT及其在頻譜分析儀中的實現(xiàn)[J].國外電子測量技術(shù)，2007(26)：6-8.

[3] 龔國輝，李思昆.FFT與循環(huán)卷積相結(jié)合的GPS信號C/A碼相位測量算法[J].通信學(xué)報，2005(26)：76-81.

[4] 鄧家斌，胡娟莉.快速傅立葉變換的圖像數(shù)據(jù)壓縮算法[J].電腦知識與技術(shù)，2009(21)：5766-5767.

[5] 曾慶喜，王慶，朱國良,等.一種基于FFT的GPS信號快速捕獲算法[J].艦船電子工程，2008(28)：70-72.

[6] 劉美容.FFT算法的DSP實現(xiàn)[J].微電子學(xué)與計算機,2015(32)：76-79.

[7] 李大習(xí).基于FPGA的可配置FFT IP核實現(xiàn)研究[J].電子科技，2014(27)：46-49.

[8] 何星,張鐵軍,侯朝煥.流水線結(jié)構(gòu)FFT/IFFT處理器的設(shè)計與實現(xiàn)[J].微電子學(xué)與計算機,2007(24):141-147.

[9] 桑紅石,高偉.高效可配置浮點FFT處理器設(shè)計[J].微電子學(xué)與計算機,2012(29):36-40.

[10] 范進,金聲震,孫才紅.超高速FFT處理器的設(shè)計與實現(xiàn)[J].光學(xué)精密工程,2009(17):2241-2246.

Configurable FFT Processor Based on FPGA

HE Jianbiao

(Department of Communication, Shenzhen Polytechnic,Shenzhen518055)

AbstractFFT is the most common method in digital signal processing. In this paper design of reconfigurable FFT processor is implemented based on FPGA. Radix2 multi-path delay commutator and pipeline architecture are adopted in this design, and the FFT processor consists of configurable radix2 calculation modules. Radix2 butterfly calculation is implemented by controlling read address of data caches according location configuration. The FFT processor is described in Verilog language and implemented in Cyclone VI device.

Key Wordsfast fourier transform, multi-path delay commutator, pipeline, field programmable gate array

* 收稿日期：2015年11月12日,修回日期：2015年12月11日

基金項目：“南山區(qū)移動互聯(lián)技術(shù)公共服務(wù)平臺”(項目編號：KC2014ZDZJ0023A)資助。

作者簡介：何健標(biāo)，男，博士，工程師，研究方向：包括通信與信息系統(tǒng)、數(shù)字信號處理。

中圖分類號TP391

DOI：10.3969/j.issn.1672-9730.2016.05.031