大分?jǐn)?shù)超高速ff硬件系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

大分?jǐn)?shù)超高速ff硬件系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

在數(shù)字?jǐn)?shù)據(jù)處理的發(fā)展中，許多算法可以應(yīng)用于離散傅里葉變換（dft），這可以節(jié)省數(shù)字信號(hào)（如圖形、聲音、圖像等）。因此，dft是處理圖像消息（如圖形、聲音和圖像）的重要變換工具。快速傅里葉變換(FFT)是DFT的快速算法。FFT算法的硬件實(shí)現(xiàn)一般有3種形式:1)使用通用DSP來(lái)實(shí)現(xiàn);2)用專用DSP來(lái)實(shí)現(xiàn);3)通過(guò)FPGA來(lái)實(shí)現(xiàn)。總體來(lái)講,DSP速度較慢,接口不靈活,而且沒有FFT運(yùn)算所需要的巨量存儲(chǔ)器,需外置特定的接口、控制芯片和RAM,限制了運(yùn)算速度,但DSP開發(fā)相對(duì)簡(jiǎn)單,技術(shù)成熟,開發(fā)費(fèi)用相對(duì)較低,目前大部分FFT硬件是用DSP來(lái)實(shí)現(xiàn)的;FPGA技術(shù)近兩年才達(dá)到可以實(shí)現(xiàn)大點(diǎn)數(shù)FFT的水平,并且體積、速度、靈活性等各種性能都優(yōu)于DSP,但開發(fā)難度大,研制費(fèi)用高。本文將討論基于FPGA的大點(diǎn)數(shù)超高速FFT算法。1fft算法下的乘子法對(duì)N點(diǎn)序列x(n),其DFT變換對(duì)定義為:式中x(n)為時(shí)域點(diǎn);X(k)為頻域點(diǎn);WN為旋轉(zhuǎn)因子。FFT是利用了旋轉(zhuǎn)因子的周期性和對(duì)稱性,對(duì)DFT進(jìn)行簡(jiǎn)化的運(yùn)算。各種FFT算法可分兩大類:一類是針對(duì)N等于2的整數(shù)次冪的算法,如基二算法、基四算法、實(shí)因子算法和分裂基算法等,另一類是針對(duì)N不等于2的整數(shù)次冪的算法,以Winograd為代表的類算法,有重要的理論價(jià)值,但是不適于硬件實(shí)現(xiàn)。FFT按分解方式的不同又可以分為按時(shí)域抽取算法和按頻域抽取算法(DecimationInFrequence,DIF)兩種。兩種算法在本質(zhì)上是完全相同的,在運(yùn)算量和復(fù)雜性等方面都完全一樣,可以任取其中的一種,本文將討論的是基二算法和DIF形式。FFT運(yùn)算的基本單元是蝶形運(yùn)算單元,基二蝶形運(yùn)算單元如圖1所示。其方程式為:解式(2)和式(3)得到基二蝶形運(yùn)算單元輸出結(jié)果表達(dá)式為:從上面的公式可以得出,基二蝶形運(yùn)算只需兩次復(fù)數(shù)乘法,則N=2n個(gè)點(diǎn)的DFT復(fù)數(shù)乘法量由N2次降為N/2*lbN次,復(fù)數(shù)加法由N*(N-)1次降為N*lbN。所以在大點(diǎn)數(shù)DFT運(yùn)算時(shí),使用FFT將極大的降低運(yùn)算量,提高運(yùn)算效率。2fft和sst轉(zhuǎn)換模塊整個(gè)FFT運(yùn)算模塊在FPGA內(nèi)部進(jìn)行配置,本文所討論的基二FFT運(yùn)算模塊配置框圖如圖2所示。圖中,控制模塊用來(lái)產(chǎn)生所有的控制信號(hào),存儲(chǔ)器2和3分別作為時(shí)刻n和n+t時(shí)對(duì)應(yīng)輸入N點(diǎn)數(shù)據(jù)的存儲(chǔ)器,存儲(chǔ)器1作為中間結(jié)果存儲(chǔ)器,用于存儲(chǔ)Butterfly運(yùn)算模塊計(jì)算出的奇數(shù)級(jí)的結(jié)果,旋轉(zhuǎn)因子存儲(chǔ)器中存儲(chǔ)的是N/2點(diǎn)旋轉(zhuǎn)因子。在FFT運(yùn)算過(guò)程中,地址產(chǎn)生是FFT運(yùn)算模塊的關(guān)鍵問(wèn)題之一,存儲(chǔ)器讀數(shù)據(jù)和寫數(shù)據(jù)都要對(duì)應(yīng)相應(yīng)的存儲(chǔ)器地址。在控制模塊中定義一個(gè)時(shí)鐘計(jì)數(shù)器和一個(gè)級(jí)數(shù)計(jì)數(shù)器,級(jí)數(shù)計(jì)數(shù)器隨級(jí)數(shù)的增加自加,在每完成一個(gè)FFT之后清零,時(shí)鐘計(jì)數(shù)器隨每一個(gè)時(shí)鐘自加,在每完成一級(jí)FFT之后清零,通過(guò)這兩個(gè)計(jì)數(shù)器的加減和移位可以產(chǎn)生所有需要的地址。地址產(chǎn)生中的位反序是FFT運(yùn)算的最關(guān)鍵問(wèn)題,DIF形式的FFT輸入數(shù)據(jù)x(n)地址為順序,但由于在運(yùn)算過(guò)程中對(duì)x(n)作奇、偶分開,導(dǎo)致輸出數(shù)據(jù)地址不再是原來(lái)順序。例如對(duì)于8點(diǎn)DIF形式的FFT,其第一級(jí)輸入數(shù)據(jù)地址是正序0,1,2,3,4,5,6,7。最后一級(jí)數(shù)據(jù)輸出數(shù)據(jù)地址為反序0,4,2,6,1,5,3,7。為了得到正確的輸出數(shù)據(jù),必須通過(guò)二進(jìn)制碼位反轉(zhuǎn)將反序變?yōu)檎?。在控制模塊中,數(shù)據(jù)的地址都是由二進(jìn)制數(shù)表示,反序0,4,2,6,1,5,3,7分別由三位二進(jìn)制數(shù)表示為000,100,010,110,001,101,011,111,將每個(gè)數(shù)的第2位和第0位交換,第1位保持不動(dòng),可以得到000,001,010,011,100,101,110,111,即0,1,2,3,4,5,6,7,即將反序變?yōu)檎?。?duì)于其他點(diǎn)數(shù)的FFT,如果數(shù)據(jù)地址由n位表示,位反轉(zhuǎn)的規(guī)則為:第n-1位和第0位交換,第n-2位和第1位交換,第n-3位和第2位交換,……,依此類推就可以將反序轉(zhuǎn)換為正序。逆FFT的實(shí)現(xiàn)同樣可以采用FFT運(yùn)算模塊,首先將輸入數(shù)據(jù)求共軛,再作FFT運(yùn)算,最后將得到的結(jié)果取共軛除以總點(diǎn)數(shù)就是輸入數(shù)據(jù)的IFFT運(yùn)算結(jié)果。因而FFT和IFFT可以由同一硬件模塊完成。由前面基二蝶形運(yùn)算的分析可以得出理論上基二蝶形運(yùn)算只需4個(gè)32位乘法器,但實(shí)際硬件中,需要將旋轉(zhuǎn)因子rW和iW由有符號(hào)小數(shù)歸一化為有符號(hào)整數(shù)。在本文中,是將rW和iW按32位有符號(hào)定點(diǎn)數(shù)歸一化(即乘以231-1=2147483647)后存儲(chǔ)到旋轉(zhuǎn)因子存儲(chǔ)器,比較式(4)~(7)可得出,為保持?jǐn)?shù)據(jù)一致性,在Butterfly運(yùn)算中x′a和y′a也應(yīng)乘以2147483647,因此基二蝶形運(yùn)算共需6個(gè)32位乘法器。STRATIX系列EP1S25芯片提供了80個(gè)8位內(nèi)置乘法器,由8個(gè)8位乘法器可以組成一個(gè)32位乘法器。所以EP1S25一共可以提供10個(gè)32位乘法器。在本設(shè)計(jì)中,FFT運(yùn)算需要6個(gè)32位乘法器,如果需要在頻域進(jìn)行復(fù)數(shù)乘法運(yùn)算則又需要4個(gè)32位乘法器,一共需要10個(gè)32位乘法器,STRATIX系列的EP1S25剛好滿足要求?？紤]到該因素,本設(shè)計(jì)選用了Altera公司的Stratix系列EP1S25芯片。Stratix系列FPGA主要特點(diǎn)包括:高性能體系、大容量存儲(chǔ)資源、高帶寬DSP模塊、支持多種I/O標(biāo)準(zhǔn)、高速接口、時(shí)鐘管理、終端技術(shù)、Nios?軟內(nèi)核嵌入處理器、器件配置和遠(yuǎn)程系統(tǒng)升級(jí)。EP1S25芯片中包含的DSP單元,可以完成較為耗費(fèi)資源的乘法器單元功能。另外,該芯片包含的大量存儲(chǔ)單元,可保證旋轉(zhuǎn)因子的精度。其主要內(nèi)部資源如表1所示。這就是本文選擇這一芯片的主要原因。本文系統(tǒng)在微機(jī)與FPGA間的數(shù)據(jù)通信中采用了32bitPCI總線接口。PCI總線的數(shù)據(jù)通信過(guò)程包括讀傳送、寫傳送、傳送終止等,通過(guò)PCI總線實(shí)現(xiàn)了高速數(shù)據(jù)傳輸,同時(shí)PCI總線協(xié)議也確保了數(shù)據(jù)通信的可靠性和完整性,從而保證了整個(gè)系統(tǒng)的高速性和穩(wěn)定性。整個(gè)FFT系統(tǒng)以FGPA(EP1S25)為核心。先把程序代碼通過(guò)JTAG下載入EPC8(該芯片是用來(lái)配置SRAM工藝FPGA的EEPROM),當(dāng)上電時(shí)EPC8自動(dòng)配置FPGA(EP1S25)由電腦發(fā)出控制信號(hào)是用來(lái)協(xié)調(diào)原始數(shù)據(jù)的輸入和運(yùn)算結(jié)果數(shù)據(jù)的輸出,原始數(shù)據(jù)(由實(shí)部32bit和虛部32bit組成)是由電腦送出,經(jīng)PCI總線由PCI9054傳入FPGA做FFT/IFFT運(yùn)算,當(dāng)運(yùn)算結(jié)束后,運(yùn)算結(jié)果再輸出到PCI9054,由PCI總線送出到電腦。本文系統(tǒng)特點(diǎn)是:1)為提高數(shù)據(jù)精度,系統(tǒng)全部數(shù)據(jù)采用32bit。2)每次處理對(duì)象可以是4096點(diǎn)數(shù)據(jù),實(shí)現(xiàn)了大點(diǎn)數(shù)FFT運(yùn)算。3)實(shí)現(xiàn)了FFT運(yùn)算的快速流水操作。采用乒乓RAM的方式,當(dāng)多組數(shù)據(jù)進(jìn)行FFT運(yùn)算時(shí),可由存儲(chǔ)器2和存儲(chǔ)器3交替接收數(shù)據(jù),如此類推形成乒乓結(jié)構(gòu)的流型運(yùn)算,進(jìn)行FFT運(yùn)算的同時(shí),存儲(chǔ)器也在接收數(shù)據(jù)。即在計(jì)算存儲(chǔ)器3中第n組數(shù)據(jù)的同時(shí),存儲(chǔ)器2則正在接收第n+1組數(shù)據(jù)。這種方式?jīng)Q定了實(shí)現(xiàn)FFT運(yùn)算的最大時(shí)間。對(duì)于4096點(diǎn)操作,其接收時(shí)間為4096個(gè)數(shù)據(jù)周期,這樣FFT的最大運(yùn)算時(shí)間就是4096個(gè)數(shù)據(jù)周期。另外,由于輸入和輸出數(shù)據(jù)是以一定的時(shí)鐘為周期依次輸入或輸出的,而FFT運(yùn)算時(shí)鐘是由FPGA芯片所決定,故可以利用較高的內(nèi)部時(shí)鐘來(lái)提高內(nèi)部FFT運(yùn)算速度,從而節(jié)省了處理數(shù)據(jù)的時(shí)間,提高了整個(gè)FFT運(yùn)算效率。3分析和應(yīng)用硬件測(cè)試結(jié)果3.1fft運(yùn)算穩(wěn)定由FFT運(yùn)算公式可知,一個(gè)方波經(jīng)FFT運(yùn)算后為Sa(w)函數(shù),圖3所示正是由實(shí)際硬件對(duì)一個(gè)數(shù)據(jù)總長(zhǎng)度為512點(diǎn)、脈沖寬度為20點(diǎn)方波進(jìn)行FFT運(yùn)算求模歸一化后的結(jié)果。由硬件試驗(yàn)結(jié)果可說(shuō)明FFT運(yùn)算是正確的。由于系統(tǒng)采用基二FFT運(yùn)算,其核心FPGA及其外圍器件都是高速器件,同時(shí)內(nèi)核計(jì)算采用并行處理,所以系統(tǒng)可實(shí)現(xiàn)大點(diǎn)數(shù)FFT高精度與高速運(yùn)算。3.2散射系數(shù)的成像星載SAR實(shí)時(shí)成像處理過(guò)程實(shí)際上是一個(gè)二維解卷積過(guò)程,因此可以利用該系統(tǒng)進(jìn)行處理,即回波信號(hào)經(jīng)過(guò)模數(shù)轉(zhuǎn)換后,進(jìn)行距離和方位匹配濾波過(guò)程,其數(shù)學(xué)模型為:S(x,r)為回波信號(hào),?σ(x,r)為地表的散射系數(shù)的估值,hr-1(x,r)和ha-1(x,r)分別為距離向和方位向線性調(diào)頻函數(shù),則成像處理的結(jié)構(gòu)功能框圖如圖4所示。一幀原始數(shù)據(jù)(4096*4096個(gè)復(fù)數(shù)點(diǎn))經(jīng)過(guò)本系統(tǒng)硬件距離向、方位向處理,可得到如圖5所示成像結(jié)果,同樣原始數(shù)據(jù)經(jīng)過(guò)軟件處理得到的成像結(jié)果如圖6所示。兩個(gè)結(jié)果幾乎完全一樣,但硬件成像速度遠(yuǎn)遠(yuǎn)快于軟件成像速度,由此證明該FFT處理系統(tǒng)在星載SAR實(shí)