基于FPGA的24點(diǎn)離散傅里葉變換結(jié)構(gòu)設(shè)計(jì)

孫重磊

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

由于具有高集成度、高速、可編程等優(yōu)點(diǎn)，現(xiàn)場(chǎng)可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)已經(jīng)廣泛用于多種高速信號(hào)實(shí)時(shí)處理領(lǐng)域中［1－2］。離散傅里葉變換(Discrete Fourier Transform，DFT)，尤其對(duì)應(yīng)的快速傅里葉變換(Fast Fourier Transform，F(xiàn)FT)，是數(shù)字信號(hào)處理中的一種基本變換。基于FPGA的FFT設(shè)計(jì)和實(shí)現(xiàn)是眾多應(yīng)用中的一個(gè)重要環(huán)節(jié)，是眾多FPGA芯片廠商和研究工作者一直致力研究的內(nèi)容。

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

以Xilinx公司Virtex IV芯片為硬件平臺(tái)，結(jié)合Xilinx公司ISE10.1軟件提供的FFT IP核，提出一種適合FPGA實(shí)現(xiàn)的基于Good－Thomas算法［7］的24點(diǎn)DFT結(jié)構(gòu)。相對(duì)于已有的FFT結(jié)構(gòu)，設(shè)計(jì)的DFT結(jié)構(gòu)不僅能夠充分利用FFT IP核優(yōu)良特性，還能大大節(jié)約復(fù)數(shù)乘法器資源的使用。同時(shí)，該結(jié)構(gòu)還能擴(kuò)展至變換長(zhǎng)度N滿足N=3×2n的DFT。

1 24點(diǎn)DFT實(shí)現(xiàn)原理

1.1 Good－Thomas映射算法

基于Cooley－Tukey映射算法和Good－Thomas映射算法［7］的FFT均可以將長(zhǎng)度為N=N1N2的DFT分解成N2個(gè)N1點(diǎn)DFT和N1個(gè)N2點(diǎn)DFT級(jí)聯(lián)的形式。尤其基于Cooley－Tukey映射的FFT是最為通用的FFT算法，能夠適應(yīng)于任意N1和N2長(zhǎng)度下的DFT。相對(duì)基于 Cooley－Tukey映射的 FFT，基于 Good－Thomas映射的FFT只能適應(yīng)于N1和N2互質(zhì)情況下的DFT，但N1點(diǎn)DFT與N2點(diǎn)DFT之間的中間結(jié)果不需要采用旋轉(zhuǎn)因子進(jìn)行調(diào)制，從而能夠大幅節(jié)約復(fù)數(shù)乘法器的使用。

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

步驟1 根據(jù)式(1)對(duì)輸入序列進(jìn)行索引變換，將輸入序列分解成N2組長(zhǎng)度為N1的序列

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

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

其中，0≤k1≤N1－1。

步驟3 針對(duì)每一個(gè)k1，將n2看作變量，對(duì)序列計(jì)算 N2點(diǎn) DFT，得到 X(k1，k2)

其中，0≤k2≤N2－1。

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

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

1.2 24點(diǎn)DFT實(shí)現(xiàn)結(jié)構(gòu)

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

表1 輸入索引映射表

表2 輸出索引映射表

根據(jù)表1和表2的索引結(jié)果，圖1給出了24點(diǎn)DFT實(shí)現(xiàn)結(jié)構(gòu)示意圖。如圖1所示，24點(diǎn)DFT變換分兩級(jí)實(shí)現(xiàn)，第一級(jí)由3個(gè)8點(diǎn)DFT構(gòu)成，第二級(jí)由8個(gè)3點(diǎn)DFT構(gòu)成，兩級(jí)之間不需要旋轉(zhuǎn)因子調(diào)制。

圖1 基于Good－Thomas索引映射的24點(diǎn)DFT實(shí)現(xiàn)結(jié)構(gòu)示意圖

2 基于FPGA的24點(diǎn)DFT設(shè)計(jì)

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

圖2 改進(jìn)后的24點(diǎn)DFT實(shí)現(xiàn)結(jié)構(gòu)示意圖

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

圖3 3點(diǎn)DFT實(shí)現(xiàn)結(jié)構(gòu)示意圖

3 仿真驗(yàn)證

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

4 結(jié)束語

基于Good－Thomas映射算法，并結(jié)合ISE10.1軟件提供的FFT IP核，提出了一種易于FPGA實(shí)現(xiàn)的24點(diǎn)DFT設(shè)計(jì)結(jié)構(gòu)，設(shè)計(jì)的24點(diǎn)DFT模塊主要由3個(gè)8點(diǎn)FFT IP核模塊和1個(gè)3點(diǎn)DFT模塊構(gòu)成，并且只需要14個(gè)實(shí)數(shù)乘法器。同時(shí)，24點(diǎn)DFT模塊采用流水線結(jié)構(gòu)，最高工作時(shí)鐘頻率可達(dá)200 MHz。該結(jié)構(gòu)還具有良好的擴(kuò)展性，只需修改FFT IP核模塊相應(yīng)的變換點(diǎn)數(shù)參數(shù)，就可以實(shí)現(xiàn)長(zhǎng)度為點(diǎn)的DFT。

圖4 某一路輸出信號(hào)Matlab定點(diǎn)仿真結(jié)果與Modelsim仿真結(jié)果對(duì)比圖

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

［2］ 張有志.可編程邏輯器件(PLD)原理與應(yīng)用［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實(shí)現(xiàn)FFT的研究［J］.北京理工大學(xué)學(xué)報(bào)，1999，19(2):234 －238.

［6］ 樊寧波，田斌.頻分分路中高速FFT的實(shí)現(xiàn)［J］.電子設(shè)計(jì)應(yīng)用，2004，(2):40 －42.

［7］ Uwe Meyer－Baese.數(shù)字信號(hào)處理的 FPGA實(shí)現(xiàn)［M］.劉凌，胡永生，譯.北京:清華大學(xué)出版社，2003.

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