基于FPGA的24點離散傅里葉變換結構設計

孫重磊

(西安無線電技術研究所通信技術研究室，陜西西安 71000)

由于具有高集成度、高速、可編程等優點，現場可編程門陣列(Field Programmable Gate Array，FPGA)已經廣泛用于多種高速信號實時處理領域中［1－2］。離散傅里葉變換(Discrete Fourier Transform，DFT)，尤其對應的快速傅里葉變換(Fast Fourier Transform，FFT)，是數字信號處理中的一種基本變換?；贔PGA的FFT設計和實現是眾多應用中的一個重要環節，是眾多FPGA芯片廠商和研究工作者一直致力研究的內容。

目前，Altera和Xilinx公司都提供了可塑性很強的FFT IP核［3－4］，只要改動相應的參數設置，就可以應用于不同產品中。國內不少大學及研究所也已經采用FPGA芯片設計開發具有自主知識產權的 FFT［5－6］。然而，目前絕大多數基于 FPGA的 FFT主要采用Cooley－Tukey映射算法實現基2和基4結構的點FFT。這在實際應用中存在以下問題:1)某些場合中所采用的DFT變換點數不一定滿足，例如24點、48點等DFT無法采用上述FFT結構實現;2)采用 Cooley－Tukey映射算法將高點數的DFT分解成若干個低點數DFT過程中，采用多級流水線結構實現FFT，但每一級輸出結果需要乘以相應旋轉因子后再進入下一級運算，從而增加了復數乘法器資源的使用。

以Xilinx公司Virtex IV芯片為硬件平臺，結合Xilinx公司ISE10.1軟件提供的FFT IP核，提出一種適合FPGA實現的基于Good－Thomas算法［7］的24點DFT結構。相對于已有的FFT結構，設計的DFT結構不僅能夠充分利用FFT IP核優良特性，還能大大節約復數乘法器資源的使用。同時，該結構還能擴展至變換長度N滿足N=3×2n的DFT。

1 24點DFT實現原理

1.1 Good－Thomas映射算法

基于Cooley－Tukey映射算法和Good－Thomas映射算法［7］的FFT均可以將長度為N=N1N2的DFT分解成N2個N1點DFT和N1個N2點DFT級聯的形式。尤其基于Cooley－Tukey映射的FFT是最為通用的FFT算法，能夠適應于任意N1和N2長度下的DFT。相對基于 Cooley－Tukey映射的 FFT，基于 Good－Thomas映射的FFT只能適應于N1和N2互質情況下的DFT，但N1點DFT與N2點DFT之間的中間結果不需要采用旋轉因子進行調制，從而能夠大幅節約復數乘法器的使用。

假設輸入序列x(n)長度為N=N1N2，其中N1和N2互質，則基于Good－Thomas映射的FFT實現步驟如下:

步驟1 根據式(1)對輸入序列進行索引變換，將輸入序列分解成N2組長度為N1的序列

其中，mod(·)表示求余運算，0≤n1≤N1－1，0≤n2≤N2－1。

步驟2 針對每一個n2，將n1看作變量，對輸入序列 x(n)=x(n1，n2)計算 N1點 DFT，得到(n2，k1)

其中，0≤k1≤N1－1。

步驟3 針對每一個k1，將n2看作變量，對序列計算 N2點 DFT，得到 X(k1，k2)

其中，0≤k2≤N2－1。

步驟4 根據式(4)，對上述得到的序列X(k1，k2)進行輸出序列索引變換

從以上步驟可以看出，基于Good－Thomas映射的FFT，雖然與基于Cooley－Tukey映射的FFT實現原理相似，但輸入/輸出索引映射不同，而且沒有旋轉因子。

1.2 24點DFT實現結構

根據基于Good－Thomas映射的FFT適應條件，長度N=24的DFT可以按照N1=8和N2=3進行計算，其中，根據式(1)，輸入序列按照n=mod(3n1+8n2，24)進行索引映射，如表1所示;根據式(4)，輸出結果按照k=mod(9k1+16k2，24)進行索引映射，如表2所示。

表1 輸入索引映射表

表2 輸出索引映射表

根據表1和表2的索引結果，圖1給出了24點DFT實現結構示意圖。如圖1所示，24點DFT變換分兩級實現，第一級由3個8點DFT構成，第二級由8個3點DFT構成，兩級之間不需要旋轉因子調制。

圖1 基于Good－Thomas索引映射的24點DFT實現結構示意圖

2 基于FPGA的24點DFT設計

為簡化設計，假設所設計24點DFT模塊輸入/輸出信號均為24路并行信號。如圖1所示，采用Good－Thomas映射算法，可將24點DFT分解成3個8點DFT和8個3點DFT模塊構成。由于ISE10.1軟件提供的FFT IP核模塊輸入/輸出信號均為串行形式［4］，并且每一個時刻3個8點FFT IP核模塊輸出的數據恰為1個3點DFT的輸入信號。因此，為進一步節約資源，提出一種適合FPGA實現的24點DFT實現結構，如圖2所示。相對于圖1，改進后的24點DFT只需要3個8點FFT IP核模塊和1個3點DFT模塊，從而能夠大幅節約資源。同時，只需相應修改FFT IP核模塊相應參數以及串并轉換和并串轉換的路數，就可以實現長度為N=3×2n點的DFT。

圖2 改進后的24點DFT實現結構示意圖

如圖2所示，除了FFT IP核模塊，3點DFT模塊也是實現24點及N=3×2n點DFT關鍵模塊。如果根據3點DFT變換的定義直接實現，則至少需要4個復數乘法器。為減少乘法器的使用，根據式(5)～式(7)，3點DFT可以按照如圖3所示的結構［8］實現，其中，x(0)，x(1)和 x(2)表示3點 DFT輸入信號，Y(0)，Y(1)和Y(2)表3點DFT運算結果。在圖3中，數據乘以0.5可以用右移1位的方式實現，而乘以復數時可以采用兩個實數乘法器實現，因此設計的3點DFT僅需要兩個實數乘法器，從而節約了乘法器資源。同時，該結構采用流水線操作方式，也提高了實現效率。

圖3 3點DFT實現結構示意圖

3 仿真驗證

在ISE10.1環境下，采用VHDL完成了24點DFT模塊的開發，并采用Modelsim 6.2 b軟件進行仿真驗證。同時，為驗證設計的24點DFT模塊的正確性，將Modelsim仿真結果與Maltab定點仿真程序結果進行了對比。輸入信號包括24路并行數據信號、1路時鐘信號和1路復位信號，輸出信號包括24路并行數據信號、1路輸出數據有效信號。圖4給出了某一路輸出信號的Matlab定點仿真結果與Modelsim仿真結果對比圖，其中紅色表示Modelsim仿真結果數據，藍色表示Matlab定點仿真結果。從圖4可以看出，該路Modelsim仿真結果與Matlab定點仿真結果一樣。其他路輸出信號Modelsim仿真結果與Matlab定點仿真結果也一樣。從而得出設計的DFT模塊完全正確。該模塊共占用6個Block RAM，14個乘法器，時序仿真結果表明最高工作頻率可達200 MHz，該模塊已經成功應用于某一數字分路項目。

4 結束語

基于Good－Thomas映射算法，并結合ISE10.1軟件提供的FFT IP核，提出了一種易于FPGA實現的24點DFT設計結構，設計的24點DFT模塊主要由3個8點FFT IP核模塊和1個3點DFT模塊構成，并且只需要14個實數乘法器。同時，24點DFT模塊采用流水線結構，最高工作時鐘頻率可達200 MHz。該結構還具有良好的擴展性，只需修改FFT IP核模塊相應的變換點數參數，就可以實現長度為點的DFT。

圖4 某一路輸出信號Matlab定點仿真結果與Modelsim仿真結果對比圖

［1］ 朱明程，董爾令.可編程邏輯器件及應用［M］.西安:西安電子科技大學出版社，2004.

［2］ 張有志.可編程邏輯器件(PLD)原理與應用［M］.北京:中國鐵道出版社，1996.

［3］ Altera Corporation.FFT megacore function user guide［M］.USA:Altera Corporation，2010.

［4］ Xilinx Corporation.Fast fourier transform V6.0［M］.USA:Xilinx Corporation，2008

［5］ 劉朝暉，韓月秋.用FPGA實現FFT的研究［J］.北京理工大學學報，1999，19(2):234 －238.

［6］ 樊寧波，田斌.頻分分路中高速FFT的實現［J］.電子設計應用，2004，(2):40 －42.

［7］ Uwe Meyer－Baese.數字信號處理的 FPGA實現［M］.劉凌，胡永生，譯.北京:清華大學出版社，2003.

［8］ Xilinx Corporation.Discrete fourier transform V3.0 ［M］.USA:Xilinx Corporation，2008.