《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 基于FPGA的FFT算法硬件實(shí)現(xiàn)
基于FPGA的FFT算法硬件實(shí)現(xiàn)
電子科技
童慶為 陳建春
摘要: 設(shè)計(jì)了一種基于FPGA的1024點(diǎn)16位FFT算法,采用了基4蝶形算法和流水線處理方式,提高了系統(tǒng)的處理速度,改善了系統(tǒng)的性能。提出了先進(jìn)行前一級4點(diǎn)蝶形運(yùn)算,再進(jìn)行本級與旋轉(zhuǎn)因子復(fù)乘運(yùn)算的結(jié)構(gòu)。合理地利用了硬件資源。對系統(tǒng)劃分的各個模塊使用VerilogHDL進(jìn)行編碼設(shè)計(jì)。對整個系統(tǒng)整合后的代碼進(jìn)行功能驗(yàn)證之后,采用QuartusⅡ與Matlab進(jìn)行聯(lián)合仿真,其結(jié)果是一致的。該系統(tǒng)既有DSP器件實(shí)現(xiàn)的靈活性又有專用FFT芯片實(shí)現(xiàn)的高速數(shù)據(jù)吞吐能力,在數(shù)字信號處理領(lǐng)域有廣泛應(yīng)用。
關(guān)鍵詞: 開發(fā)工具 FPGA FFT算法
Abstract:
Key words :

FFT(快速傅里葉變換)是一種非常重要的算法,在信號處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等方面都有著廣泛的應(yīng)用。在高速數(shù)字信號處理中,F(xiàn)FT的處理速度往往是整個系統(tǒng)設(shè)計(jì)性能的關(guān)鍵所在。FPGA(現(xiàn)場可編程門陣列)是一種具有大規(guī)??删幊涕T陣列的器件,不僅具有ASIC(專用集成電路)快速的特點(diǎn),更具有很好的系統(tǒng)實(shí)現(xiàn)的靈活性?;贔PGA的設(shè)計(jì)可以滿足實(shí)時數(shù)字信號處理的要求,在市
場競爭中具有很大的優(yōu)勢。因此,F(xiàn)PGA為高速FFT算法的實(shí)現(xiàn)提供了一個很好的平臺。

1 FFT算法的硬件實(shí)現(xiàn)
1.1 系統(tǒng)框圖

    本設(shè)計(jì)利用流水線技術(shù)來提高系統(tǒng)的性能,系統(tǒng)框圖,如圖1所示。其中,地址產(chǎn)生單元生成RAM讀寫地址,寫使能信號以及相關(guān)模塊的啟動、控制信號,是系統(tǒng)的控制核心;4點(diǎn)蝶形運(yùn)算單元的最后一級輸出不是順序的;旋轉(zhuǎn)因子產(chǎn)生單元生成復(fù)乘運(yùn)算中的旋轉(zhuǎn)因子的角度數(shù)據(jù);旋轉(zhuǎn)因子ROM中預(yù)置了每一級運(yùn)算中所需的旋轉(zhuǎn)因子。


    在FPGA設(shè)計(jì)中,為提高系統(tǒng)的運(yùn)行速度,而將指令分為幾個子操作,每個子操作由不同的單元完成,這樣,每一級的電路結(jié)構(gòu)得到簡化,從而減少輸入到輸出間的電路延時,在較小的時鐘周期內(nèi)就能夠完成這一級的電路功能。在下一個時鐘周期到來時,將前一級的結(jié)果鎖存為該級電路的輸入,這樣逐級鎖存,由最后一級完成最終結(jié)果的輸出。也就是說,流水線技術(shù)是將待處理的任務(wù)分解為相互有關(guān)而又相互
獨(dú)立、可以順序執(zhí)行的子任務(wù)來逐步實(shí)現(xiàn)。本設(shè)計(jì)中,4點(diǎn)蝶形運(yùn)算單元、旋轉(zhuǎn)因子復(fù)乘模塊以及最后的精度截取模塊采用流水線技術(shù)來處理。
1.2 基4蝶形運(yùn)算算法原理
   
    式(1)為基4蝶形運(yùn)算單元的一般表達(dá)式,其中,,N為FFT運(yùn)算的點(diǎn)數(shù),本設(shè)計(jì)中為1 024,p為旋轉(zhuǎn)因子W的相位角,其規(guī)律將在1.4節(jié)討論。X(0)、X(1)、X(2)、X(3)為原始數(shù)據(jù),順序輸入RAM后蝶形倒序輸出,與旋轉(zhuǎn)因子復(fù)乘再進(jìn)行4點(diǎn)蝶形運(yùn)算,而X1(0)、X1(1)、X1(2)、X1(3)即為第1級蝶形運(yùn)算的結(jié)果。此時RAM存儲的原始數(shù)據(jù)已經(jīng)清空,將第1級蝶形運(yùn)算結(jié)果再存回RAM中,按照一定的地址輸出后,與第2級的旋轉(zhuǎn)因子復(fù)乘、4點(diǎn)蝶形運(yùn)算,得到第2級蝶形運(yùn)算結(jié)果,依此類推。由于蝶形運(yùn)算為同址操作,所以第2級的RAM寫地址即為第一級的RAM讀地址,每一級的RAM讀地址規(guī)律將在1.3節(jié)中討論。
    1024點(diǎn)的基4-FFT共需要5級蝶形運(yùn)算,每級需要計(jì)算256個蝶形,其傳統(tǒng)實(shí)現(xiàn)框圖如圖2所示。

 


    考慮到第一級蝶形運(yùn)算不需要旋轉(zhuǎn)因子,所以第一級的旋轉(zhuǎn)因子復(fù)乘模塊可以省略,但本設(shè)計(jì)的硬件結(jié)構(gòu)需要循環(huán)利用,一般情況下,可以對第一級數(shù)據(jù)進(jìn)行×1運(yùn)算,再進(jìn)行4點(diǎn)蝶形運(yùn)算。不過,考慮到我們并不關(guān)心每一級蝶形運(yùn)算后的結(jié)果,本文提出了一種蝶形運(yùn)算的新結(jié)構(gòu):即先進(jìn)行前一級的4點(diǎn)蝶形運(yùn)算,再進(jìn)行本級的與旋轉(zhuǎn)因子復(fù)乘運(yùn)算,如圖3所示。


    可以看出,圖3減少了一個旋轉(zhuǎn)因子復(fù)乘模塊,不但節(jié)約了一次乘法運(yùn)算時間,也省略了第一級旋轉(zhuǎn)因子,更好地利用了硬件結(jié)構(gòu)。
    首先,在QuartusⅡ環(huán)境中對4點(diǎn)蝶形運(yùn)算時序仿真,采用流水線設(shè)計(jì),連續(xù)輸入連續(xù)輸出,仿真結(jié)果如圖4所示。


    由圖4可以看出,輸出比輸入延時6個時鐘,這在系統(tǒng)的控制核心地址產(chǎn)生單元的設(shè)計(jì)中需要考慮到。
1.3 地址產(chǎn)生與時序控制
   
對于1 024.點(diǎn)基4 FFT運(yùn)算,需要5級蝶形運(yùn)算,每一級運(yùn)算都要有寫地址和讀地址,根據(jù)FFT同址運(yùn)算的特點(diǎn)可知,當(dāng)前的寫地址即是上一級蝶形運(yùn)算的讀地址。因此完成FFT運(yùn)算需要設(shè)計(jì)6級RAM地址。其中第1級的寫地址即是數(shù)據(jù)輸入的順序地址,不予討論。最后一級讀地址為數(shù)據(jù)正序輸出所需的地址。其余4級為1 024點(diǎn)數(shù)據(jù)對應(yīng)的FFT蝶形運(yùn)算。
    第一級讀取節(jié)點(diǎn)地址的順序應(yīng)該是:(0,256,512.768),(1,257,513,769),……,(255,511.767,1 023)。易觀察其讀地址的規(guī)律如下:設(shè)讀取次序的二進(jìn)制編碼為bit[9:0];則讀地址的二進(jìn)制編碼為{bit[1:O],bit[9:2]},并且依次可以推出第2、3、4級的讀地址二進(jìn)制編碼分別為{bit[9:8],bit[1:0],bit[7:2]},{bit[9:6],bit[1:0],bit[5:2]}、{bit[9:4],bit[1:0],bit[3:2]},而最后一級輸出數(shù)據(jù)的地址二進(jìn)制編碼則為:{bit[1:0],bit[3:2],bit[5:4],bit[7:6],bit[9:8]}。圖5給出了第1級讀地址和第2級讀地址的部分?jǐn)?shù)據(jù),也可以看出第2級的寫地址即是第1級的讀地址。


    圖1中的地址產(chǎn)生單元作為系統(tǒng)的控制核心,不僅要生成每一級的RAM讀寫地址,還要產(chǎn)生RAM寫使能信號、輸出有效信號以及4點(diǎn)蝶形運(yùn)算單元和旋轉(zhuǎn)因子產(chǎn)生單元的啟動信號,由于時序電路還需要考慮器件延時,例如上文提到的4點(diǎn)蝶形運(yùn)算輸出比輸入延時6個時鐘,以及RAM存取數(shù)據(jù)輸出比輸入延時1個時鐘,這些都需要在控制核心中考慮到。
1.4 旋轉(zhuǎn)因子產(chǎn)生
   
對于1 024點(diǎn)FFT蝶形運(yùn)算,需要1 024個旋轉(zhuǎn)角度(即2π的1 024等份),其中第一級不需要復(fù)乘運(yùn)算,第6級只是將數(shù)據(jù)進(jìn)行整序沒有運(yùn)算單元,其他4級都需要旋轉(zhuǎn)因子。本設(shè)計(jì)采用將旋轉(zhuǎn)因子預(yù)置于ROM中,通過查找表方法得出每一級運(yùn)算的所需的旋轉(zhuǎn)因子。根據(jù)旋轉(zhuǎn)因子的可約性,后幾級運(yùn)算所需的旋轉(zhuǎn)因子都可以在第一級運(yùn)算的旋轉(zhuǎn)因子中找到,因此無需另外存儲。旋轉(zhuǎn)因子在ROM中的存儲規(guī)律是:旋轉(zhuǎn)因子相位角p處存儲旋轉(zhuǎn)因子W=*****。定義一個10 bit的計(jì)數(shù)器count[9:0],則第2、3、4、5級ROM的相位角規(guī)律按照Verilog語法可表示為

    為了節(jié)省資源,本設(shè)計(jì)只在ROM單元中存儲了前256個旋轉(zhuǎn)因子數(shù)據(jù),即第一象限因子其余象限的因子可通過象限轉(zhuǎn)換后得到,這樣就大大節(jié)省了存儲單元的硬件資源。圖6為旋轉(zhuǎn)因子產(chǎn)生單元在QuartusⅡ環(huán)境中仿真結(jié)果的部分?jǐn)?shù)據(jù)。



2 系統(tǒng)仿真結(jié)果
   
輸入數(shù)據(jù)為s=1 024×cos(2π×f_in×t),其中f_in=50 M,F(xiàn)s=80 MHz,n=40,t=0:1/Fs:(n-1)/Fs,利用QuartusⅡ軟件對系統(tǒng)在100 MHz的時鐘環(huán)境下進(jìn)行了仿真,將仿真輸出結(jié)果轉(zhuǎn)換成tbl文件并利用Matlab軟件讀取后,得到如圖7所示的頻譜數(shù)據(jù)圖(實(shí)部數(shù)據(jù)部分)。


    圖8所示為Maflab自帶FFT函數(shù)對于輸入相同1 024點(diǎn)數(shù)據(jù)的FFT計(jì)算結(jié)果(同樣為實(shí)部數(shù)據(jù)部分)。
    通過比較可以看到,本設(shè)計(jì)的仿真結(jié)果與Matlab的仿真結(jié)果基本一致,可以正確高效地計(jì)算出1 024點(diǎn)FFT數(shù)據(jù)。

3 結(jié)束語
   
本設(shè)計(jì)全部由Verilog HDL語言實(shí)現(xiàn),采用自頂向下的設(shè)計(jì)方法,完成了一種基于FPGA的1 024點(diǎn)16位FFT算法,共需要5級運(yùn)算,每級需要計(jì)算256個蝶形。提出了將蝶形運(yùn)算先進(jìn)行前一級的蝶形加減運(yùn)算,再進(jìn)行本級的與旋轉(zhuǎn)因子復(fù)乘運(yùn)算的結(jié)構(gòu)。由前所述,平均每個蝶形運(yùn)算需要4個時鐘周期,所以理論上完成1 024點(diǎn)FFT的總時鐘周期為N=256×4×5=5 120;假設(shè)使用的時鐘為100MHz,那么將耗時T=5 120×(1/100)=51.2μs,這與仿真結(jié)果51.32μs基本一致。

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。