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

何健標

(深圳職業技術學院電信學院通信系　深圳　518055)

?

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

何健標

(深圳職業技術學院電信學院通信系深圳518055)

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

關鍵詞快速傅里葉變換; 多路延時轉接器; 流水線; 現場可編程邏輯門陣列

Class NumberTP391

1引言

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

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

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

2基2算法原理

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

(1)

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

(2)

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

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

(3)

根據旋轉因子的定義，有:

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

圖1　8點FFT分解算法圖

3實現結構

流水線結構一般采用FFT處理器串行輸入數據采樣率作為整個電路模塊的時鐘，因此對于N點FFT而言，基2運算模塊在一幀FFT數據周期內有N個電路時鐘周期，可以計算N次基2蝶形計算，因此FFT處理器的基2蝶形運算器的數量L可得:

L=(Nlog2N)/N=log2N

(9)

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

圖2　基于流水線結構的FFT處理器實現結構

4可配置基2運算模塊

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

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

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

2) 控制部分是基2運算模塊的靈魂，負責輸入數據緩存的地址控制和旋轉因子的生成。其中輸入雙口RAM的地址控制包括A/B組緩存寫入地址的控制和讀取地址的控制，其中輸入寫入緩存采用依次順序寫入的方式，與基2運算模塊所處的位置無關，地址發生器是一個計數器；而輸入緩存的數據讀取與基2運算模塊的位置信息有關。FFT處理器采用模塊結構化設計，每一級基2運算模塊的電路結構都是一樣的，不同位置的基2運算模塊的位置信息通過位置參數配置給電路，讀取地址產生器根據位置參數生成雙口RAM的讀取地址，從而實現緩存數據的重新排序。控制部分的另一功能是旋轉因子生成，所有的旋轉因子都保存在FPGA片內ROM中，但不同位置的基2運算模塊需要的旋轉因子序列是不一樣的，而旋轉因子ROM的地址控制器根據位置參數的配置不同的地址步進，從而實現旋轉因子序列的生成。

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

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

5結語

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

參 考 文 獻

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

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

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

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

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

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

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

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

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

[10] 范進,金聲震,孫才紅.超高速FFT處理器的設計與實現[J].光學精密工程,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日

基金項目：“南山區移動互聯技術公共服務平臺”(項目編號：KC2014ZDZJ0023A)資助。

作者簡介：何健標，男，博士，工程師，研究方向：包括通信與信息系統、數字信號處理。

中圖分類號TP391

DOI：10.3969/j.issn.1672-9730.2016.05.031