基于fpga的大分?jǐn)?shù)二維ff方法

0偽隨機(jī)序列換能力fft是信號(hào)分析和處理中的一個(gè)重要變化。隨著通信、雷達(dá)技術(shù)的發(fā)展,特別是CDMA技術(shù)的興起,偽隨機(jī)序列的捕獲問(wèn)題對(duì)系統(tǒng)的FFT變換能力要求越來(lái)越高。對(duì)于較短的偽隨機(jī)序列,普通的一維FFT方法在pipeline、多通道等技術(shù)的改進(jìn)下可以實(shí)現(xiàn)實(shí)時(shí)處理,然而對(duì)于超長(zhǎng)序列,如GPS的P碼,不僅周期長(zhǎng)而且速率高,如此一來(lái)這些方法便顯得無(wú)能為力了。在這種情況下二維FFT被重視起來(lái),并被一些設(shè)計(jì)者成功地用于解決長(zhǎng)序列的實(shí)時(shí)處理問(wèn)題,然而如果能像一維FFT的多通道技術(shù)一樣,將二維FFT加上并行算法,必然可以大大提高其處理能力。1由n點(diǎn)的fft轉(zhuǎn)換為二維分解長(zhǎng)度為N的有限長(zhǎng)序列x(n)的DFT為:X(k)=Ν-1∑n=0x(n)WknΝ?k=0?1???Ν-1(1)式中:WknΝ=exp{j2πkn/N}為旋轉(zhuǎn)因子。令N=N1N2,將x(n)分解為N2個(gè)長(zhǎng)度為N1序列,令n和k的序號(hào)映射定義為:n=N2n1+n20≤n1≤N1-1,0≤n2≤N2-1(2)k=k1+N1k20≤k1≤N1-1,0≤k2≤N2-1(3)則N點(diǎn)DFT可表示為:X(k)=X(k1+Ν1k2)=Ν2-1∑n2=0Ν1-1∑n1=0x(Ν2n1+n2)×W(Ν2-k1n1)ΝWk1n2ΝWΝ1k2n2ΝWΝ1Ν2k2n1n=Ν2-1∑n2=0{[Ν1-1∑n1=0x(Ν2n1+n2)Wn1k1Ν1Wk1n2Ν}Wn2k2Ν2(4)設(shè)G(n2,k1)=Ν1-1∑n1=0x(Ν2n1+n2)Wn1k1Ν1,則可以看出,大點(diǎn)數(shù)N點(diǎn)FFT被轉(zhuǎn)換為二維處理,由兩個(gè)N1和N2點(diǎn)的一維FFT先后完成,可以大大節(jié)省內(nèi)部存儲(chǔ)器。如果對(duì)大點(diǎn)數(shù)N經(jīng)過(guò)一次分解得到的N1和N2仍然較大,則可以繼續(xù)進(jìn)行二維分解,然而這樣使得控制部分的邏輯變得非常復(fù)雜,不利于FPGA的有效實(shí)現(xiàn)。但N1和N2的快速計(jì)算仍然需要解決,此時(shí)可以考慮使用并行的FFT算法。2xk評(píng)分觀察如圖1所示的標(biāo)準(zhǔn)的16點(diǎn)DIF。第一級(jí)是由間隔8行的兩行計(jì)算而成,第二級(jí)是由間隔4行計(jì)算而成,可以發(fā)現(xiàn)每一級(jí)的相關(guān)項(xiàng)在靠近。在第二級(jí)處可以看到數(shù)據(jù)已經(jīng)成為相互獨(dú)立的4項(xiàng),因此可以考慮相互獨(dú)立的計(jì)算單元來(lái)并行的計(jì)算它們,這就是并行FFT的思想。在計(jì)算通信領(lǐng)域關(guān)于并行FFT已經(jīng)提出了很多算法,其中一種方法就是將要計(jì)算的數(shù)值分組用不同的處理器來(lái)計(jì)算(如對(duì)于16點(diǎn)的情況可以分成4組),但是由于第一級(jí)各組之間并不是獨(dú)立的,所以需要特別的模塊來(lái)控制這種通信。也有一些方法不需要第一級(jí)的數(shù)據(jù)交換,但是在計(jì)算完第一級(jí)后需要對(duì)其結(jié)果進(jìn)行適當(dāng)?shù)奶幚聿拍荛_(kāi)始第二級(jí)的計(jì)算?？紤]將輸出X(k)分為4個(gè)部分,那么N點(diǎn)的DFT可以分解為:X(4k)=Ν-1∑n=0x[n]W(4k)nΝ(5)X(4k+1)=Ν-1∑n=0x[n]W(4k+1)nΝ(6)X(4k+2)=Ν-1∑n=0x[n]W(4k+2)nΝ(7)X(4k+3)=Ν-1∑n=0x[n]W(4k+3)nΝ(8)因?yàn)镕FT的4個(gè)輸出各自需要4個(gè)輸入,因此式(5)～(8)需要相互獨(dú)立的輸入數(shù)據(jù)組。所以再對(duì)X(4k)進(jìn)行分解:X(4k)=Ν-1∑n=0x[n]W(4k)nΝ=Ν/4-1∑n=0x[n]W4knΝ+Ν/2-1∑n=Ν/4x[n]W4knΝ+3Ν/4-1∑n=Ν/2x[n]W4knΝ+Ν-1∑n=3Ν/4x[n]W4knΝ(9)變量代換后有:X(4k)=Ν/4-1∑n=0x[n]W4knΝ+Ν/4-1∑n=0x[n+Ν/4]W4knΝWkΝΝ+Ν/4-1∑n=0x[n+Ν/2]W4knΝW2kΝΝ+Ν/4-1∑n=0x[n+3Ν/4]W4knΝW3kΝΝ(10)因?yàn)閃ΖkΝΝ=1,WΖknΝ=WknΝ/Ζ,其中Z為整數(shù),則式(10)變?yōu)?X(4k)=Ν/4-1∑n=0(x[n]+x[n+Ν/4]+x[n+Ν/2]+x[n+3Ν/4])WknΝ/4(11)同理其余3個(gè)輸出可以變?yōu)?X(4k+1)=Ν/4-1∑n=0(x[n]-jx[n+Ν/4]+x[n+Ν/2]+jx[n+3Ν/4])WknΝ/4WnΝ(12)X(4k+2)=Ν/4-1∑n=0(x[n]-x[n+Ν/4]+x[n+Ν/2]-x[n+3Ν/4])WknΝ/4W2nΝ(13)X(4k+3)=Ν/4-1∑n=0(x[n]+jx[n+Ν/4]-x[n+Ν/2]-jx[n+3Ν/4])WknΝ/4W3nΝ(14)令:a0[n]=x[n]+x[n+N/4]+x[n+N/2]+x[n+3N/4])(15)a1[n]=(x[n]-jx[n+N/4]+x[n+N/2]+jx[n+3N/4])WknΝ/4WnΝ(16)a2[n]=(x[n]-x[n+N/4]+x[n+N/2]-x[n+3N/4])WknΝ/4W2nΝ(17)a3[n]=(x[n]+jx[n+N/4]-x[n+N/2]-jx[n+3N/4])WknΝ/4W3nΝ(18)代入上面的結(jié)果則得到:X(4k)=Ν/4-1∑n=0a0[n]WknΝ/4(19)X(4k+1)=Ν/4-1∑n=0a1[n]WknΝ/4(20)X(4k+2)=Ν/4-1∑n=0a2[n]WknΝ/4(21)X(4k+3)=Ν/4-1∑n=0a3[n]WknΝ/4(22)觀察式(18)～(22)發(fā)現(xiàn)這時(shí)的結(jié)果即是各組的DFT的結(jié)果,并且它們的旋轉(zhuǎn)因子相同,故它們可以各自獨(dú)立的從并行的FFT模塊計(jì)算得出。唯一需要另外計(jì)算的就是{a0[n],a1[n],a2[n],a3[n]},它們其實(shí)可以通過(guò)修正過(guò)旋轉(zhuǎn)因子傳統(tǒng)4點(diǎn)的蝶形運(yùn)算單元計(jì)算,如圖2,它的旋轉(zhuǎn)因子可以從a的表達(dá)式獲得。這個(gè)結(jié)果和混合基FFT方法是相當(dāng)?shù)?。采用并行方法?shí)現(xiàn)FFT的最大好處便在于能夠獲得比傳統(tǒng)方法更大的吞吐量,同時(shí),因?yàn)椴⑿型ǖ拦昧诉壿嫼蛢?nèi)存單元從而獲得了超線性的加速(吞吐量提高K倍而使用的硬件資源卻小于原先的K倍)。本文討論的是4通道并行FFT,實(shí)際上在具體實(shí)現(xiàn)中可以實(shí)現(xiàn)任意通道數(shù)目。很明顯此種并行的思想可以在硬件資源允許的情況下極大的提高吞吐量,它提供了在硬件資源和處理速度之間取舍的途徑。本文的4并行FFT算法用VHDL實(shí)現(xiàn)寫入ALTERA公司的StratixEP1S80并將結(jié)果與單通道的FFT對(duì)比,結(jié)果見(jiàn)表1。所有計(jì)算采用固定點(diǎn)數(shù)18位精度。吞吐量即每秒鐘的采樣數(shù),可以由時(shí)鐘速率乘以并行通道數(shù)目獲得。由表可見(jiàn)4并行的FFT用的硬件資源僅僅是單通道的2～3倍但卻在基本相同的時(shí)鐘速率下運(yùn)算時(shí)間縮短為原先的1/4。3并行fft算法與單通道算法的比較針對(duì)VLSI的多片聯(lián)合并行多通道技術(shù)及針對(duì)FPGA的單片并行多通道技術(shù)已經(jīng)被一些有實(shí)力的公司研究出來(lái),相關(guān)的使用文檔也公開(kāi)發(fā)行,然而它們很少涉及到詳細(xì)的內(nèi)部結(jié)構(gòu)。本文從FFT的理論公式出發(fā),推導(dǎo)