何健標(biāo)

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

?

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

何健標(biāo)

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

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

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

Class NumberTP391

1引言

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

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

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

2基2算法原理

對(duì)于時(shí)域信號(hào)序列x(n)，其N點(diǎn)離散傅立葉變換公式為

(1)

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

(2)

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

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

(3)

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

(4)

為便于描述，令：

(5)

對(duì)于0≤k

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

(6)

對(duì)于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)

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

圖1　8點(diǎn)FFT分解算法圖

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

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

L=(Nlog2N)/N=log2N

(9)

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

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

4可配置基2運(yùn)算模塊

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

圖3　可配置的基2運(yùn)算模塊

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

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

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

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

5結(jié)語

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

參 考 文 獻(xiàn)

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

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

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

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

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

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

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

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

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

[10] 范進(jìn),金聲震,孫才紅.超高速FFT處理器的設(shè)計(jì)與實(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日

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

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

中圖分類號(hào)TP391

DOI：10.3969/j.issn.1672-9730.2016.05.031