基于FPGA的級聯(lián)結(jié)構(gòu)FFT處理器的優(yōu)化設(shè)計

張竺君 錢建平

摘 要:為了減少級聯(lián)結(jié)構(gòu)FFT處理器對緩沖存儲器需求量,提出一種基于FPGA用基[CD*2]16和基[CD*2]2、基[CD*2]4、基[CD*2]8組合的混合基算法實(shí)現(xiàn)FFT處理器的設(shè)計方案。在1 024點(diǎn)FFT處理器的實(shí)現(xiàn)過程中,用優(yōu)化的基[CD*2]4蝶形運(yùn)算核搭建了級聯(lián)結(jié)構(gòu)的基[CD*2]16蝶形運(yùn)算核,并將對同一個地址進(jìn)行讀和寫的雙端口RAM和乒乓結(jié)構(gòu)的單端口RAM結(jié)合使用,從而在不增加邏輯單元使用和保證運(yùn)算速度的情況下,大大減少了存儲單元的使用量。

關(guān)鍵詞:快速傅里葉變換;FPGA;基[CD*2]16算法;混合基算法;級聯(lián)結(jié)構(gòu)

中圖分類號:TP274

0 引 言

數(shù)字信號處理主要研究采用數(shù)字序列或符號序列表示信號,并用數(shù)字計算方法對這些序列進(jìn)行處理,以便把信號變換成符合某種需要的形式。在現(xiàn)代數(shù)字信號處理中,最常用的變換方法就是離散傅里葉變換(DFT),然而,它的計算量較大,運(yùn)算時間長,在某種程度上限制了它的使用范圍。快速傅里葉變換(FFT)的提出使DFT的實(shí)現(xiàn)變得接近實(shí)時,DFT的應(yīng)用領(lǐng)域也得以迅速拓展。它在圖像處理、語音分析、雷達(dá)、聲納、地震、通信系統(tǒng)、遙感遙測、地質(zhì)勘探、航空航天、生物醫(yī)學(xué)等眾多領(lǐng)域都獲得極其廣泛的應(yīng)用。隨著〧PGA技術(shù)的高速發(fā)展以及EDA技術(shù)的成熟,采用〧PGA芯片實(shí)現(xiàn)FFT已經(jīng)顯示出巨大的潛力。

目前用FPGA實(shí)現(xiàn)的FFT處理器結(jié)構(gòu)大致分為四種:遞歸結(jié)構(gòu)、級聯(lián)結(jié)構(gòu)、并行結(jié)構(gòu)和陣列結(jié)構(gòu)[2[CD*2]6]。遞歸結(jié)構(gòu)只利用一個碟形運(yùn)算單元對數(shù)據(jù)進(jìn)行規(guī)律的循環(huán)計算,使用硬件資源較少,但運(yùn)算時間較長。級聯(lián)結(jié)構(gòu)每一級均采用一個獨(dú)立的碟形運(yùn)算單元來處理,相對遞歸結(jié)構(gòu)速度上有所提高,不足之處是增加了延時用的緩沖存儲器使用量。并行結(jié)構(gòu)對一級中的蝶形單元并行實(shí)現(xiàn),陣列結(jié)構(gòu)是將每一級的蝶形運(yùn)算單元全部并行實(shí)現(xiàn),這兩種結(jié)構(gòu)有很高的運(yùn)算速度,但消耗的資源過大,一般不采用。為了提高運(yùn)算速度,特別是為了適應(yīng)多批數(shù)據(jù)處理,一般采用級聯(lián)結(jié)構(gòu)實(shí)現(xiàn)FFT處理器。

1 FFT整體結(jié)構(gòu)設(shè)計

在FFT算法中,目前大多使用基[CD*2]2和基[CD*2]4算法實(shí)現(xiàn)級聯(lián)結(jié)構(gòu)的FFT處理器,除此之外,也可采用┗鵞CD*2]8和基[CD*2]16算法來實(shí)現(xiàn)。隨著基數(shù)的增大,對于相同點(diǎn)數(shù)的離散數(shù)列,處理器所分的級數(shù)越少,對緩沖存儲器的需求也越小,因此考慮采用基[CD*2]16算法來實(shí)現(xiàn)FFT處理器,但基[CD*2]16算法只能實(shí)現(xiàn)離散數(shù)列點(diǎn)數(shù)是16的玴次冪的FFT[7]。從而,引入混合基思想來改進(jìn)基[CD*2]16算法。

設(shè)玿(n)為N點(diǎn)有限長序列,其DFT為

設(shè)r1=16琾,r2=N/16琾=2,4,8,式(2)先將原非16的p次冪的N點(diǎn)獸FT分解為16琾點(diǎn)的獸FT;再分解為N/16琾點(diǎn)的獸FT。首先對輸入信號進(jìn)行16琾點(diǎn)的獸FT運(yùn)算,然后將結(jié)果乘以一個旋轉(zhuǎn)因子W﹏0k0璑,最后將計算出的數(shù)據(jù)進(jìn)行一次N/16琾У鉌FT運(yùn)算,得到的結(jié)果即為所需要的玁點(diǎn)FFT運(yùn)算結(jié)果。這樣處理,既能減少分解的級數(shù),又能使計算離散數(shù)列點(diǎn)數(shù)只需是2的整數(shù)次冪即可。以1 024點(diǎn)為例,只需分解成兩級┗鵞CD*2]16運(yùn)算模塊和一級基[CD*2]4運(yùn)算模塊即可實(shí)現(xiàn),其FFT處理器結(jié)構(gòu)圖如圖1所示。在此結(jié)構(gòu)圖的前端增加/減少┗鵞CD*2]16運(yùn)算模塊或?qū)⒆詈笠患壔鵞CD*2]4運(yùn)算模塊改為基[CD*2]2或基[CD*2]8運(yùn)算模塊,就可以實(shí)現(xiàn)其他離散數(shù)列的點(diǎn)數(shù)只需是2的整數(shù)次冪的FFT運(yùn)算。

2 蝶形運(yùn)算核的實(shí)現(xiàn)

2.1 基[CD*2]16蝶形運(yùn)算核

如果直接將基[CD*2]16蝶形運(yùn)算公式轉(zhuǎn)換到硬件中實(shí)現(xiàn)基[CD*2]16運(yùn)算核,其結(jié)構(gòu)將十分復(fù)雜的‐[9,10]。因此,采用易實(shí)現(xiàn)的頻域抽選基[CD*2]4算法來實(shí)現(xiàn)頻域抽選基[CD*2]16蝶形運(yùn)算核。由基[CD*2]4蝶行運(yùn)算單元實(shí)現(xiàn)的基[CD*2]16蝶行運(yùn)算單元如圖2所示。

采用并行流水結(jié)構(gòu)實(shí)現(xiàn)的基[CD*2]16運(yùn)算核,一個數(shù)據(jù)時鐘可處理16個數(shù)據(jù)。而每次蝶形運(yùn)算在一個數(shù)據(jù)時鐘內(nèi)只需要計算出一個結(jié)果,這將造成資源浪費(fèi)。因此,采用級聯(lián)結(jié)構(gòu)實(shí)現(xiàn)的基[CD*2]16蝶形運(yùn)算核,用兩個┗鵞CD*2]4蝶形運(yùn)算核分別復(fù)用4次來實(shí)現(xiàn)每一級中的四個蝶行運(yùn)算,中間用┮桓霆串行出入/輸出的寄存器進(jìn)行連接,其結(jié)構(gòu)框圖如圖3所示。

2.2 基[CD*2]4蝶形運(yùn)算核

基[CD*2]4蝶形運(yùn)算核的結(jié)構(gòu)如圖4所示,其中加減模塊為兩級流水結(jié)構(gòu),一次可以計算4個數(shù)據(jù)。蝶形運(yùn)算的四個串行輸入數(shù)據(jù)經(jīng)串/并轉(zhuǎn)換器轉(zhuǎn)換為四路并行數(shù)據(jù),進(jìn)入加減運(yùn)算單元。計算出的4個并行結(jié)果進(jìn)入并/串轉(zhuǎn)換器后,串行輸入復(fù)數(shù)乘法器和旋轉(zhuǎn)因子相乘然后輸出結(jié)果。因為圖1中最后一級的數(shù)據(jù)只需要進(jìn)行加減運(yùn)算不需要再乘以旋轉(zhuǎn)因子,所以圖1中的┗鵞CD*2]4蝶形運(yùn)算核是沒有復(fù)數(shù)乘法器的,數(shù)據(jù)從并/串轉(zhuǎn)換器中直接輸出給緩沖存儲器。

2.3 復(fù)數(shù)乘法器

雖然現(xiàn)在的高端產(chǎn)中已經(jīng)集成了可以完成乘法的DSP資源,但也是有限的。因此高效復(fù)數(shù)乘法器的設(shè)計對該設(shè)計來講仍然非常的重要。復(fù)數(shù)乘法的標(biāo)準(zhǔn)式如下:

式中:A,B分別為輸入數(shù)據(jù)的實(shí)部和虛部,C和D分別為旋轉(zhuǎn)因子的實(shí)部和虛部。按照這種標(biāo)準(zhǔn)表達(dá)式,執(zhí)行一次復(fù)數(shù)乘法需要進(jìn)行4次實(shí)數(shù)乘法,2次實(shí)數(shù)加法和2次實(shí)數(shù)減法。將上述公式重新整理為:R=(C-D)?〣+狢(A-B),I=(C-D)A-C(A-B)в嘔后的復(fù)數(shù)乘法器需要進(jìn)行3次實(shí)數(shù)乘法,2次實(shí)數(shù)加法和3次實(shí)數(shù)減法,相比傳統(tǒng)結(jié)構(gòu)多了一個減法器,少了一個乘法器。在FPGA中,加減法模塊所占用的相對裸片面積要小于相同位數(shù)的乘法器模塊。這樣的優(yōu)化還是很有價值的,在FFT吞吐量不變的情況下,可減少25%的乘法器使用量,在乘法器數(shù)量一定的情況下可高FFT吞吐量。

3 存儲器單元

傳統(tǒng)的級聯(lián)結(jié)構(gòu)的FFT處理器的緩沖存儲器都是采用乒乓結(jié)構(gòu),基本思想就是用兩塊相同的RAM交替讀出或?qū)懭霐?shù)據(jù)。即其中一塊RAM在寫入數(shù)據(jù)時,另一塊RAM用于讀出數(shù)據(jù)。當(dāng)用于寫入數(shù)據(jù)的RAM寫滿時交換讀寫功能。將乒乓結(jié)構(gòu)中RAM的內(nèi)部存儲單元地址用二進(jìn)制數(shù)a9a8a7a6a5a4a3a2a1a0表示。以寫滿其中以塊玆AM為一個周期,用一個二進(jìn)制計數(shù)器玬9m8m7m6m5m4m3m2m1m0生成的順序?qū)懭?混序讀取的乒乓結(jié)構(gòu)玆AM的操作地址如表1所示。[HJ1]第一塊緩こ宕媧⑵韉詼塊緩こ宕媧⑵韉諶塊緩こ宕媧⑵韉謁目榛邯こ宕媧⑵

表1中第一,二,四塊存儲器的寫操作地址和讀操作地址是可以互換的,也就是將數(shù)據(jù)混序?qū)懭?順序讀取。因此,根據(jù)這個規(guī)律采用一塊可同時讀寫的雙端口RAM來實(shí)現(xiàn)第一,二,四塊存儲器。其基本思想就是對同一個地址進(jìn)行讀和寫。以用一塊雙端口RAM實(shí)現(xiàn)第一塊存儲器的為例,在第一個周期內(nèi)雙端口RAM按照地址m9m8m7m6m5m4m3m2m1m0進(jìn)行寫操作,即數(shù)據(jù)是按照自然順序儲存的。在第二個周期按照地址m0m1m2m3m4m5m6m7m8m9同時進(jìn)行讀寫操作,讀出的數(shù)據(jù)按照倒位序排列,寫入的數(shù)據(jù)按照倒位序儲┐嫻摹＊在第三個周期按照地址m9m8m7m6m5m4m3m2m1m0同時進(jìn)行讀寫操作,讀出的數(shù)據(jù)按照倒位序排列,寫入的數(shù)據(jù)是按照自然順序儲存的。依次類推下去,讀出的數(shù)據(jù)都是按照倒位序排列。同樣第二塊和第四塊存儲器的存儲地址也具有這樣類似的循環(huán)規(guī)律。因此只有第三塊存儲器需要用乒乓結(jié)構(gòu)的RAM實(shí)現(xiàn),與傳統(tǒng)所有存儲器都用乒乓結(jié)構(gòu)RAM實(shí)現(xiàn)相比,節(jié)省了3/8的存儲單元。

設(shè)計中用Matlab軟件直接生成旋轉(zhuǎn)因子,并將其轉(zhuǎn)化為16位有符號定點(diǎn)數(shù)寫入MIF文件。然后用ROM直接調(diào)用MIF文件,將旋轉(zhuǎn)因子預(yù)置在ROM中。

4 仿真結(jié)果

選用Altera公司生產(chǎn)的Cyclone Ⅱ的EP2C35F484C7芯片上進(jìn)行驗證,在Quartyus Ⅱ7.2軟件中進(jìn)行編譯和仿真。通過對高基核的優(yōu)化處理,該[LL]設(shè)計對邏輯單元消耗量和傳統(tǒng)用基[CD*2]4算法實(shí)現(xiàn)相近,僅為4 399,但由于本文采用了高基低基組合的混合基算法,在處理1 024點(diǎn)的離散數(shù)列時,處理器所分的級數(shù)僅為3級,相對傳統(tǒng)的低基數(shù)算法,其實(shí)現(xiàn)減少了對緩沖存儲器塊數(shù)的需求;并通過對緩沖存儲器的優(yōu)化設(shè)計,又比全部用乒乓結(jié)構(gòu)RAM實(shí)現(xiàn)的傳統(tǒng)方法節(jié)省了3/8的存儲單元,因此占用的存儲資源僅為154 048 b。仿真波形如圖5所示,該仿真結(jié)果和Matlab計算結(jié)果基本一致,存在一定的誤差是由于有限字長效應(yīng)引起的。

5 結(jié) 語

在100 MHz的時鐘下工作,完成一次1 024點(diǎn)的FFT從輸入初始數(shù)據(jù)到運(yùn)算結(jié)果完全輸出僅需要54.48 μs,且連續(xù)運(yùn)算時,處理一組1 024點(diǎn)FFT的時間僅為10.24 μs,達(dá)到了高速信號處理的要求。

參 考 文 獻(xiàn)

[1]蔡可紅.基于FPGA的FFT設(shè)計與實(shí)現(xiàn)[D].南京:南京理工大學(xué),2006.

[2]韓穎.高速專用FFT處理器的設(shè)計與實(shí)現(xiàn)[D].北京:北京理工大學(xué),2003.

[3]陸旦前,陳建平,陳曉勇.FFT算法的一種FPGA設(shè)計[J].微電子技術(shù),2007(6):178[CD*2]180.

[4]鮑慶龍,劉平.基于FPGA的高速FFT算法實(shí)現(xiàn)[J].微處理機(jī),2007(2):16[CD*2]19.

[5]樊光輝,許茹,王德清.基于FPGA的高速流水線FFT算法實(shí)現(xiàn)[J].電子工程師,2008,34(3):38[CD*2]40.

[6]賀衛(wèi)東,段哲民,龔誠.基于FPGA的大點(diǎn)數(shù)FFT算法研究[J].電子測量技術(shù),2007,30(11):14[CD*2]16.

[7]謝彥林.可變點(diǎn)流水線結(jié)構(gòu)FFT處理器的設(shè)計及其 FPGA 實(shí)現(xiàn)[D].西安:西安電子科技大學(xué),2007.

[8]程佩青.數(shù)字信號處理教程[M].2版.北京:清華大學(xué)出版社,2004.

[9]劉小明.超高速快速傅里葉變換的實(shí)現(xiàn)[D].合肥:合肥工業(yè)大學(xué),2006.

[10]蘇彥鵬.張漢富.韓磊.基于FPGA的4K點(diǎn)基[CD*2]16 FFT模塊的實(shí)現(xiàn)[J].電子與封裝,2007,7(9):8[CD*2]11.