基于FPGA的高速定點(diǎn)FFT算法的實(shí)現(xiàn)

徐 娜,楊鼎才

摘 要:針對(duì)高速實(shí)時(shí)信號(hào)處理的要求,提出一種基于現(xiàn)場(chǎng)可編程門陣列(FPGA)實(shí)現(xiàn)64點(diǎn)高速定點(diǎn)快速傅里葉變換(FFT)算法的方法。該方法從運(yùn)算速度和實(shí)現(xiàn)復(fù)雜度兩方面綜合考慮,采用基于按時(shí)間抽取的Radix-4算法的三級(jí)流水線結(jié)構(gòu),每級(jí)將乘法器的旋轉(zhuǎn)因子輸入端固定為常數(shù)值,而不是作為變量從ROM中讀取,從而減少ROM的讀取時(shí)間。另外,為了避免溢出,還采用塊浮點(diǎn)結(jié)構(gòu)表示數(shù)據(jù),節(jié)省了大量的硬件資源。從實(shí)驗(yàn)結(jié)果看,可以滿足對(duì)數(shù)據(jù)高速實(shí)時(shí)處理的要求。

關(guān)鍵詞:現(xiàn)場(chǎng)可編程門陣列;Radix-4算法;流水線結(jié)構(gòu);塊浮點(diǎn)結(jié)構(gòu)

中圖分類號(hào):TP368.1文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)12-106-02

Implementation of High Speed Fixed-piont Fast Fourier Transform Algorithm Based on FPGA

XU Na,YANG Dingcai

(Information Science and Engineering Institute,Yanshan University,Qinhuangdao,066004,China)

Abstract:To meet the requirement of high data processing, an implementation method of 64 points high speed fixed-point FFT algorithm based on FPGA is discussed.Considering both the speed and the complexity,this method uses three- stage pipeline structures based on Radix-4 algorithm by DIT.The input of rotating factor is fixed to constant,rather than variables,which can reduce the reading time from ROM.Moreover,in order to avoid overflowing,it also uses block-floating-piont structure that can save many hardware resources.It is able to meet the requirement of high speed and real-time through the experimental results.

Keywords:FPGA;Radix-4 algorithm;pipeline structure;block-floating-piont structure

0 引 言

快速傅里葉變換(FFT)作為計(jì)算和分析工具,在眾多學(xué)科領(lǐng)域(如信號(hào)處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等)有著廣泛的應(yīng)用。在高速數(shù)字信號(hào)處理領(lǐng)域,如雷達(dá)信號(hào)處理,FFT的處理速度往往是整個(gè)系統(tǒng)設(shè)計(jì)性能的關(guān)鍵所在。

針對(duì)高速實(shí)時(shí)信號(hào)處理的要求,軟件實(shí)現(xiàn)方法顯然滿足不了其需要。近年來現(xiàn)場(chǎng)可編程門陣列(FPGA)以其高性能、高靈活性、友好的開發(fā)環(huán)境、在線可編程等特點(diǎn),使得基于FPGA的設(shè)計(jì)可以滿足實(shí)時(shí)數(shù)字信號(hào)處理的要求,在市場(chǎng)競(jìng)爭(zhēng)中具有很大的優(yōu)勢(shì)。

在FFT算法中,數(shù)據(jù)的寬度通常都是固定的寬度。然而,在FFT的運(yùn)算過程中,特別是乘法運(yùn)算中,運(yùn)算的結(jié)果將不可避免地帶來誤差。因此,為了保證結(jié)果的準(zhǔn)確性,采用定點(diǎn)分析是非常必要的。

1 FFT算法原理

FFT算法的基本思想就是利用權(quán)函數(shù)的周期性、對(duì)稱性、特殊性及周期N的可互換性,將較長(zhǎng)序列的DFT運(yùn)算逐次分解為較短序列的DFT運(yùn)算。針對(duì)N=2的整數(shù)次冪,FFT算法有基-2算法、基-4算法、實(shí)因子算法和分裂基算法等。這里,從處理速度和占用資源的角度考慮,選用基-4按時(shí)間抽取FFT算法(DIT)。

對(duì)于N=4γ,基-4 DIT具有l(wèi)og4 N=γ次迭代運(yùn)算,每次迭代包含N/4個(gè)蝶形單元。蝶形單元的運(yùn)算表達(dá)式為:

A′=(A+CW2P)+(BWP+DW3P)

B′=(A-CW2P)-j(BWP-DW3P)

C′=(A+CW2P)-(BWP+DW3P)

D′=(A-CW2P)+j(BWP-DW3P)

其信號(hào)流如圖1。式中:A,B,C,D和A′,B′,C′,D′均為復(fù)數(shù)據(jù);W=e-j2π/N。進(jìn)行1次蝶形運(yùn)算共需3次復(fù)乘和8次復(fù)加運(yùn)算。N=64點(diǎn)的基-4DIT信號(hào)流其輸入數(shù)據(jù)序列是按自然順序排列的,輸出結(jié)果需經(jīng)過整序。64點(diǎn)數(shù)據(jù)只需進(jìn)行3次迭代運(yùn)算,每次迭代運(yùn)算含有N/4=16個(gè)蝶形單元。

2 FFT算法的硬件實(shí)現(xiàn)

2.1 流水線方式FFT算法的實(shí)現(xiàn)

為了提高FFT工作頻率和節(jié)省FPGA資源,采用3級(jí)流水線結(jié)構(gòu)實(shí)現(xiàn)64點(diǎn)的FFT運(yùn)算。流水線處理器的結(jié)構(gòu)如圖2所示。

圖1 -4 DIT蝶形單元信號(hào)流圖

圖2 流水線結(jié)構(gòu)

每級(jí)均由延時(shí)單元、轉(zhuǎn)接器(SW)、蝶形運(yùn)算和旋轉(zhuǎn)因子乘法4個(gè)模塊組成,延時(shí)節(jié)拍由方框中的數(shù)字表示。各級(jí)轉(zhuǎn)接器和延時(shí)單元起到對(duì)序列進(jìn)行碼位抽取并將數(shù)據(jù)拉齊的作用。每級(jí)延時(shí)在FPGA內(nèi)部用FIFO實(shí)現(xiàn),不需要對(duì)序列進(jìn)行尋址即可實(shí)現(xiàn)延時(shí)功能。數(shù)據(jù)串行輸入,經(jīng)過3級(jí)流水處理后,串行輸出。

轉(zhuǎn)接器有一定的工作規(guī)律。例如,當(dāng)?shù)?級(jí)變換做完進(jìn)入轉(zhuǎn)接器SW1前,先對(duì)后三路數(shù)據(jù)進(jìn)行一定節(jié)拍的延時(shí),延遲節(jié)拍分別為4,8,12。為了說明規(guī)律,把輸入轉(zhuǎn)接器的四路數(shù)據(jù)按照前后次序進(jìn)行分組,每4個(gè)時(shí)鐘節(jié)拍為1組,共16組,如圖3(左)所示。在數(shù)據(jù)流串行經(jīng)過轉(zhuǎn)接器SW1時(shí),第0組中的數(shù)據(jù)保持不變,第1組中的數(shù)據(jù)與第4組中的數(shù)據(jù)交換;5不變,2和8交換,3和12交換,6和9交換;10不變,7和13交換,11和14交換,15不變。交換完畢后,前三路數(shù)據(jù)經(jīng)過延遲節(jié)拍分別為12,8,4的FIFO存儲(chǔ)器輸出,位置關(guān)系如圖3所示。

圖3 SW1前后各組位置關(guān)系

上述轉(zhuǎn)換規(guī)律對(duì)于SW2也是適用的,只是轉(zhuǎn)接器前后的延時(shí)節(jié)拍和分組的大小有所不同。

2.2 存儲(chǔ)單元

為了實(shí)現(xiàn)算法的流水線設(shè)計(jì),存儲(chǔ)器RAM設(shè)計(jì)為64×16 b的雙端口RAM,即在時(shí)鐘信號(hào)和寫控制信號(hào)同時(shí)為低電平時(shí),從輸入總線寫入RAM;在時(shí)鐘信號(hào)和讀控制信號(hào)同時(shí)為高電平時(shí),從 RAM輸出數(shù)據(jù)。

ROM為17×16 b的ROM,儲(chǔ)存經(jīng)過量化后的旋轉(zhuǎn)因子,旋轉(zhuǎn)因子為正弦函數(shù)和余弦函數(shù)的組合。根據(jù)旋轉(zhuǎn)因子的對(duì)稱性和周期性,在利用ROM存儲(chǔ)旋轉(zhuǎn)因子時(shí),可以只存儲(chǔ)旋轉(zhuǎn)因子的一部分。

2.3 運(yùn)算結(jié)構(gòu)

Radix-4蝶形運(yùn)算單元是整個(gè) FFT處理器中的核心部件。在用Radix-4運(yùn)算器計(jì)算時(shí)需要并行輸入數(shù)據(jù),如果能以并發(fā)數(shù)據(jù)輸入的話,則同步性和控制度較好,但實(shí)際上常要進(jìn)行串并之間的轉(zhuǎn)換。存儲(chǔ)RAM按單節(jié)拍輸出16 b位寬數(shù)據(jù),選擇器不停旋轉(zhuǎn)送入到確定的位置,每4點(diǎn)全部到位后R-4使能有效;然后4個(gè)時(shí)鐘節(jié)拍得到有效結(jié)果數(shù)據(jù),再通過選擇器旋轉(zhuǎn)送入到對(duì)應(yīng)存儲(chǔ)RAM中。

復(fù)數(shù)運(yùn)算中,對(duì)應(yīng)復(fù)數(shù)的實(shí)部和虛部RAM用同一個(gè)地址發(fā)生器。地址發(fā)生器在進(jìn)行RAM地址發(fā)生時(shí)采用兩套地址,第一套是計(jì)數(shù)器按時(shí)鐘節(jié)拍順序產(chǎn)生的,用于輸入數(shù)據(jù)的存儲(chǔ);第二套是由數(shù)據(jù)寬度為16 b的ROM產(chǎn)生的,ROM中存放的數(shù)據(jù)為下級(jí)運(yùn)算所需倒序的序列地址,發(fā)生地址給RAM,然后RAM按倒序地址輸出下級(jí)需要進(jìn)行運(yùn)算的數(shù)據(jù)。

2.4 塊浮點(diǎn)結(jié)構(gòu)

數(shù)字信號(hào)處理系統(tǒng)可分為定點(diǎn)制、浮點(diǎn)制和塊浮點(diǎn)制,它們?cè)趯?shí)現(xiàn)時(shí)對(duì)系統(tǒng)資源的要求不同,工作速度也不同,有著不同的適用范圍。定點(diǎn)制算法簡(jiǎn)單,速度快,但動(dòng)態(tài)范圍有限,需要用合適的溢出控制規(guī)則(如定比例法)適當(dāng)壓縮輸入信號(hào)的動(dòng)態(tài)范圍。浮點(diǎn)表示法動(dòng)態(tài)范圍大,可避免溢出,但系統(tǒng)實(shí)現(xiàn)復(fù)雜,硬件需求量大,速度慢。

為了提高精度,并減少復(fù)雜度和存儲(chǔ)量,采用塊浮點(diǎn)結(jié)構(gòu)。塊浮點(diǎn)算法是以上兩種表示法的結(jié)合。這種表示方法是,一組數(shù)共用同一個(gè)階碼,這個(gè)階碼是這組數(shù)中最大數(shù)的階碼。塊浮點(diǎn)算法無需進(jìn)行額外的指數(shù)運(yùn)算,僅對(duì)尾數(shù)進(jìn)行運(yùn)算即可,其與定點(diǎn)運(yùn)算一樣方便,但需要在每級(jí)運(yùn)算結(jié)束后進(jìn)行本級(jí)運(yùn)算溢出最大位數(shù)判斷,以對(duì)數(shù)據(jù)塊進(jìn)行塊指數(shù)調(diào)整。在調(diào)整時(shí)僅保留一位符號(hào)位,因而能夠充分利用有限位長(zhǎng)。這樣處理比定點(diǎn)方法擴(kuò)大了動(dòng)態(tài)范圍,并且提高了精度,比浮點(diǎn)運(yùn)算在速度上有了提高。

塊浮點(diǎn)結(jié)構(gòu)如圖4所示。

圖4 塊浮點(diǎn)結(jié)構(gòu)

3 結(jié) 語

著重討論基于FPGA的64點(diǎn)高速FFT算法的實(shí)現(xiàn)方法。采用高基數(shù)結(jié)構(gòu)和流水線結(jié)構(gòu),大大提高了FFT處理器的運(yùn)行速度。同時(shí)塊浮點(diǎn)結(jié)構(gòu)的引入,也大幅減少了浮點(diǎn)操作占用FPGA器件的資源數(shù)目,兼顧了FPGA高精度、低資源、低功耗的特點(diǎn)。從實(shí)驗(yàn)結(jié)果看,該方法可以滿足高速實(shí)時(shí)處理數(shù)字信號(hào)的要求。

參考文獻(xiàn)

[1]朱冰蓮,劉學(xué)剛.FPGA實(shí)現(xiàn)流水線結(jié)構(gòu)的FFT處理器[J].重慶大學(xué)學(xué)報(bào),2004,27(9):33-36.

[2]胡廣書.數(shù)字信號(hào)處理理論、算法與實(shí)現(xiàn)[M].2版.北京:清華大學(xué)出版社,2005.

[3]陳麗安,張培銘.定點(diǎn)DSP塊浮點(diǎn)算法及其實(shí)現(xiàn)技術(shù)[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版,2004;32(6):689-693.

[4]求是科技.VHDL應(yīng)用開發(fā)技術(shù)與工程實(shí)踐[M].北京:人民郵電出版社,2005.

[5]孔利東.基于FPGA到數(shù)據(jù)采集與處理技術(shù)的研究[D].武漢:武漢理工大學(xué),2007.

[6]譚征,張曉林.一種基于FPGA的超高速FFT處理器設(shè)計(jì)[J].遙測(cè)遙控,2005,26(6):46-49.

[7]任淑艷,關(guān)叢榮.應(yīng)用VHDL語言的FFT算法實(shí)現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報(bào),2003,8(6):24-26.

[8]田豐,鄧建國.FFT算法的一種FPGA實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù),2005,28(8):97-100.

[9]孫志堅(jiān),劉學(xué)梅.在FPGA中實(shí)現(xiàn)高速FFT算法的研究[J].青島建筑工程學(xué)院學(xué)報(bào),2005,26(2):84-86.

[10]王誠,吾繼華.Altera FPGA/CPLD設(shè)計(jì)(基礎(chǔ)篇)[M].北京:人民郵電出版社,2005.