固定幾何結(jié)構(gòu)的FFT算法及其FPGA實(shí)現(xiàn)
1.引言
DFT及其快速算法FFT是信號處理領(lǐng)域的核心組成部分。FFT算法多種多樣,按數(shù)據(jù)組合方式不同一般分時域和頻域,按數(shù)據(jù)抽取方式的不同又可分為基2,基4等。各算法的優(yōu)缺點(diǎn)視不同的制約因素而不同。FFT的實(shí)現(xiàn)方法也多種多樣,可以用軟件實(shí)現(xiàn),也可以用硬件實(shí)現(xiàn),用軟件在PC機(jī)或工作站上實(shí)現(xiàn)則計(jì)算速度很慢。一般多結(jié)合具體系統(tǒng)用硬件實(shí)現(xiàn)。例如用單片機(jī)或DSP實(shí)現(xiàn)。但是速度仍然很慢,難以與快速的A/D器件匹配。在雷達(dá)信號處理領(lǐng)域主要追求的目標(biāo)是速度,即實(shí)時性的要求非常高。針對這種快速信號處理的要求及FPGA器件的特點(diǎn),本文采用的是一種基2固定幾何結(jié)構(gòu)的FFT算法。采用的是Altera公司推出的最新器件Stratix來做硬件仿真。Stratix器件是一款采用高性能結(jié)構(gòu)體系的PLD器件。它結(jié)合了強(qiáng)大內(nèi)核性能,大存儲帶寬,數(shù)字信號處理(DSP)功能,高速I/O性能和模塊化設(shè)計(jì)與一體的PLD。其內(nèi)嵌的DSP模塊具有很高的乘法運(yùn)算速度。在用VHDL編程時可以用MegaWizard的方法指定用DSP模塊生成乘法器,用這種乘法器來做蝶形,用多個蝶形來構(gòu)成FFT運(yùn)算級,通過循環(huán)即可實(shí)現(xiàn)FFT核心運(yùn)算的并行化。用Altera公司的Quartus軟件做邏輯分析和波形分析。Quartus軟件具有很強(qiáng)的硬件仿真和邏輯分析功能,它可將用VHDL編寫的硬件描述綜合到FPGA中。
2.算法介紹
為了說明問題的方便,下面以基2,八點(diǎn)FFT為例加以說明。傳統(tǒng)的基2變幾何結(jié)構(gòu)算法如下(圖一):箭頭上的數(shù)字代表旋轉(zhuǎn)因子 中的k。圖中輸入采用的是按碼位顛倒的順序排放的。輸出是自然順序。這種結(jié)構(gòu)的特點(diǎn)是每個蝶形的輸出數(shù)據(jù)仍然放在原來的輸入的數(shù)據(jù)存儲單元內(nèi),這樣只需要2N個存儲單元(FFT中的數(shù)據(jù)是復(fù)數(shù)形式,每點(diǎn)需要兩個單元存儲)。其缺點(diǎn)是不同級的同一位置蝶形的輸入數(shù)據(jù)的尋址不固定,難以實(shí)現(xiàn)循環(huán)控制。用FPGA編程時難以并行實(shí)現(xiàn),數(shù)據(jù)處理速度慢。當(dāng)FFT的點(diǎn)數(shù)增加時更是如此。通過觀察傳統(tǒng)結(jié)構(gòu)的FFT算法可以發(fā)現(xiàn),如果將第一級中間的兩個蝶形交換,則可以得到如下結(jié)構(gòu)(圖二):
對此結(jié)構(gòu)進(jìn)行進(jìn)一步的變換,將第二級的輸出不送回原處而是將其存儲起來并按順序存放,則第三級中間的兩個蝶形跟著調(diào)換,并把輸入按順序排列,就變成了如下(圖三)所示的固定結(jié)構(gòu)的FFT了。在蝶形變換的同時,其旋轉(zhuǎn)因子也跟著調(diào)換。
出數(shù)據(jù)的順序是不變的,因此每級幾何結(jié)構(gòu)是固定的。用這種結(jié)構(gòu)尋址方便,易于用FPGA編程,實(shí)現(xiàn)內(nèi)部并行的FFT硬件結(jié)構(gòu),從而明顯加快FFT的運(yùn)算速度。
3.FPGA硬件實(shí)現(xiàn)
FPGA器件的特點(diǎn)是可用硬件描述語言對其進(jìn)行靈活編程。利用FPGA廠商提供的軟件可仿真硬件的功能。使硬件設(shè)計(jì)如同軟件設(shè)計(jì)一樣靈活方便??s短了系統(tǒng)研發(fā)周期。利用JTAG接口可對其進(jìn)行ISP(In System Programmable 在系統(tǒng)編程)提高了系統(tǒng)的靈活性。隨著芯片集成度的提高,單片F(xiàn)PGA內(nèi)不僅擁有大量的邏輯單元而且還能集成RAM,ROM,I/O及DSP塊等。從而使SOC(System On_a_Chip 片上系統(tǒng))成為現(xiàn)實(shí)。本文采用的是Altera公司的Stratix系列芯片的EP1s25。用Altera公司的QuartusII2.0軟件做硬件仿真和邏輯分析。并將輸出結(jié)果與Matlab仿真結(jié)果進(jìn)行了比較。系統(tǒng)框圖如下(圖四):
代碼用VHDL硬件描述語言實(shí)現(xiàn)。本系統(tǒng)的結(jié)構(gòu)特點(diǎn)是:1。為提高數(shù)據(jù)精度,系統(tǒng)全部用16位寬。用data_array,write_array和fly_array三個數(shù)組實(shí)現(xiàn)了內(nèi)核的并行處理,可在10個時鐘周期內(nèi)算完32點(diǎn)復(fù)FFT。時鐘周期為25納秒,因此32點(diǎn)FFT只需250納秒。2。實(shí)現(xiàn)了數(shù)據(jù)的流水輸入輸出。在計(jì)算第i組數(shù)據(jù)的同時,第i-1組的數(shù)據(jù)FFT結(jié)果正在串行輸出,第i+1組的數(shù)據(jù)則正在串行輸入。因?yàn)閮?nèi)核計(jì)算是并行的,速度快,所以可以有很高的串行輸入。本系統(tǒng)的A/D采樣頻率可達(dá)200MHz。仿真所用的信號是:
x(t)= (0.5*sin(2*n*pi/4.7)+0.5*sin(2*n*pi/16.3)+0.1*rand(1,32))*1000
輸入數(shù)據(jù)為32點(diǎn)復(fù)數(shù),系統(tǒng)仿真波形如下(局部):
用FPGA輸出的FFT的結(jié)果(圖六)和用Matlab計(jì)算的FFT理論結(jié)果(圖七),其頻譜如下:
此信號是由兩個正弦波疊加一個隨機(jī)函數(shù)構(gòu)成的。信噪比為14db。為切合工程實(shí)際,仿真信號采用的是實(shí)信號,其頻譜具有對稱性,因此圖中只取32點(diǎn)仿真結(jié)果的一半即16點(diǎn)便可。
4.結(jié)論
通過比較可以看出仿真結(jié)果與理論值吻合的很好。Altera公司采用傳統(tǒng)結(jié)構(gòu)的FFT算法其32點(diǎn)的運(yùn)算時間大于1.0us。用DSP做的32點(diǎn)FFT時間也要1.0us以上。本系統(tǒng)的最大優(yōu)勢在于利用FPGA器件豐富的邏輯資源,內(nèi)嵌的RAM,ROM塊及其靈活的可編程特性采用固定幾何結(jié)構(gòu)的FFT算法使運(yùn)算速度較傳統(tǒng)方法有了很大提高。當(dāng)然付出的代價是用這種并行的結(jié)構(gòu)需求的硬件資源很多。隨著芯片集成度的不斷提高,用這種并行結(jié)構(gòu)實(shí)現(xiàn)的FFT運(yùn)算其優(yōu)越性將越來越明顯。而且用這種結(jié)構(gòu)實(shí)現(xiàn)的FFT很容易擴(kuò)展。只需要增加蝶形的個數(shù)和循環(huán)次數(shù)即可。詳細(xì)說明見 VHDL源程序。