頻分分路中高速FFT的實(shí)現(xiàn)

摘    要：本文介紹了多相陣列FFT在星上多載波數(shù)字化分路中的應(yīng)用，并針對(duì)星上處理的實(shí)時(shí)高速處理要求，提出了一種FFT的實(shí)現(xiàn)方案，并用一片FPGA芯片驗(yàn)證了其正確性和可行性。
關(guān)鍵詞：FFT；FPGA；頻分分路

多載波信號(hào)的數(shù)字化分路是衛(wèi)星通信星上處理技術(shù)的關(guān)鍵技術(shù)之一，數(shù)字化分路技術(shù)主要有并行濾波器組分路、樹(shù)形濾波器組分路和多相陣列FFT分路三種。在通道數(shù)較多時(shí)，多相陣列FFT有效地使用了抽取技術(shù)，且FFT算法具有很高的計(jì)算效率，本文所討論的就是該方法中FFT的實(shí)現(xiàn)。

FFT方案的確定
本文所實(shí)現(xiàn)的是32點(diǎn)復(fù)數(shù)FFT，F(xiàn)FT運(yùn)算輸入為含有32路合路信號(hào)信息的連續(xù)串行數(shù)據(jù)流，數(shù)據(jù)率為40M波特，每32個(gè)數(shù)據(jù)為一組，每隔32個(gè)時(shí)鐘周期又是一組新的數(shù)據(jù)，F(xiàn)FT運(yùn)算的輸出也是32個(gè)數(shù)據(jù)為一組的連續(xù)串行數(shù)據(jù)流，對(duì)應(yīng)頻分分路后的32路信號(hào)的數(shù)據(jù)信息。輸入/輸出數(shù)據(jù)的數(shù)據(jù)率和FFT內(nèi)部的時(shí)鐘計(jì)算頻率數(shù)值是相等的，這要求FFT的前端部分必須在32個(gè)時(shí)鐘周期內(nèi)完成對(duì)一組數(shù)據(jù)的處理，以保證不造成其后一組數(shù)據(jù)的“丟失”。星上多載波數(shù)字化分路是實(shí)時(shí)超高速、大規(guī)模運(yùn)算場(chǎng)合，所以FFT運(yùn)算的處理時(shí)間是首要因素，結(jié)合這些要求，本設(shè)計(jì)采用時(shí)域抽取的基2算法，在硬件結(jié)構(gòu)上采用級(jí)聯(lián)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。

硬件實(shí)現(xiàn)
運(yùn)算架構(gòu)
總體運(yùn)算框圖如圖1所示。
輸入的串行數(shù)據(jù)流(復(fù)數(shù)數(shù)據(jù))經(jīng)過(guò)倒序模塊輸出兩路并行數(shù)據(jù)，經(jīng)過(guò)五級(jí)蝶形運(yùn)算后，輸出一路串行的復(fù)數(shù)數(shù)據(jù)。每級(jí)的蝶形運(yùn)算由一個(gè)蝶形運(yùn)算單元完成，前一級(jí)蝶形運(yùn)算的輸出直接送給后一級(jí)運(yùn)算，這樣對(duì)整個(gè)FFT模塊來(lái)說(shuō)，當(dāng)進(jìn)行第一輪數(shù)據(jù)運(yùn)算時(shí)，前一級(jí)的運(yùn)算開(kāi)始后，后一級(jí)要等待一段時(shí)間才能開(kāi)始運(yùn)算。從第二輪數(shù)據(jù)運(yùn)算開(kāi)始，每級(jí)蝶形運(yùn)算都有數(shù)據(jù)在進(jìn)行運(yùn)算，一直處于“忙”狀態(tài)，資源得到了充分利用。倒序模塊較為簡(jiǎn)單，這里不作敘述。
各級(jí)蝶形運(yùn)算的實(shí)現(xiàn)
蝶形運(yùn)算單元是每級(jí)運(yùn)算的核心單元，如圖2所示，其信號(hào)關(guān)系如下：
X＝A+B*                              (1)
 Y＝A-B*                      (2)
式中為旋轉(zhuǎn)因子，第一級(jí)運(yùn)算的旋轉(zhuǎn)因子只有一種形式，為=1，第二級(jí)運(yùn)算的旋轉(zhuǎn)因子有兩種形式，為、，后者等于－j，容易推知這兩級(jí)蝶形運(yùn)算主要是完成復(fù)數(shù)加減運(yùn)算。實(shí)現(xiàn)框圖如圖3所示。
下面分析第一級(jí)運(yùn)算的時(shí)序(見(jiàn)圖4)，這里著重分析從第一組數(shù)據(jù)輸入到第一組數(shù)據(jù)輸出的時(shí)序操作，后面各級(jí)的分析類(lèi)同。計(jì)數(shù)模塊主要用于表示時(shí)鐘的次序，讓一個(gè)信號(hào)量sel從0到31循環(huán)計(jì)數(shù)。第一個(gè)時(shí)鐘(sel=0)將第一組輸入數(shù)據(jù)din1、din2映射到底層模塊進(jìn)行運(yùn)算，可得到結(jié)果dout1、dout2，第二個(gè)時(shí)鐘(sel=1)負(fù)責(zé)運(yùn)算第二組數(shù)據(jù)din3、din4，可得到結(jié)果dout3、dout4，同時(shí)頂層模塊將底層模塊送上來(lái)的第一組結(jié)果dout1、dout2保存。依此類(lèi)推，在第四個(gè)(sel=3)時(shí)鐘，頂層模塊已經(jīng)保存了前兩組運(yùn)算結(jié)果dout1、dout2、dout3、dout4，正是第二級(jí)第一次蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)(dout1、dout3)的來(lái)源，這時(shí)候即可輸出第一級(jí)的第一組輸出dout1、dout3。
與第一級(jí)不同的是，第二級(jí)運(yùn)算模塊雖然也是只進(jìn)行加減運(yùn)算，但是根據(jù)前面的分析，這一級(jí)旋轉(zhuǎn)因子有1和-j兩種形式，所以相應(yīng)加減運(yùn)算也有兩種。對(duì)應(yīng)地，在這一級(jí)的底層模塊運(yùn)算分兩種不同的方式，故在頂層模塊加一個(gè)控制字，底層模塊根據(jù)該控制字來(lái)判斷進(jìn)行哪種運(yùn)算，這一點(diǎn)實(shí)現(xiàn)簡(jiǎn)單，這里不再贅述。
第二級(jí)的計(jì)數(shù)模塊和第一級(jí)是一樣的，所以對(duì)于第二級(jí)來(lái)說(shuō)，在sel=4時(shí)才有第一組輸入數(shù)據(jù)，第二級(jí)運(yùn)算的時(shí)序分析類(lèi)似于第一級(jí)，從第五個(gè)時(shí)鐘(sel=4)將本級(jí)第一組輸入數(shù)據(jù)din1、din2映射到底層模塊運(yùn)算，得到結(jié)果dout1和dout2，sel=5將第一組運(yùn)算結(jié)果dout1、dout2映射給頂層保存。依此類(lèi)推，sel=8時(shí)，頂層模塊已保存了三組運(yùn)算結(jié)果dout1、dout2、dout3、dout4、dout5、dout6，從此時(shí)鐘開(kāi)始輸出本級(jí)的第一組輸出數(shù)據(jù)dout1、dout5(第三級(jí)的第一次蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù))。
從第三級(jí)開(kāi)始，旋轉(zhuǎn)因子中有復(fù)數(shù)形式出現(xiàn)，如第三級(jí)的旋轉(zhuǎn)因子為、、、，其中、是復(fù)數(shù)數(shù)據(jù)，所以后三級(jí)蝶形運(yùn)算涉及到復(fù)數(shù)乘法，其實(shí)現(xiàn)框圖如圖5所示。                            
第三級(jí)運(yùn)算的時(shí)序分析：由第二級(jí)的時(shí)序分析可知，sel=9時(shí)本級(jí)即可開(kāi)始運(yùn)算，所以第一組旋轉(zhuǎn)因子應(yīng)該在sel=8時(shí)代入，由于有復(fù)數(shù)乘法，所以要在頂層模塊就得到蝶形運(yùn)算的第一組結(jié)果，與前面兩級(jí)相比需要多幾個(gè)時(shí)鐘周期。在sel=15時(shí)，頂層模塊得到第一組蝶形運(yùn)算結(jié)果。同樣地，為了使本級(jí)的輸出適合下一級(jí)蝶形運(yùn)算，需要等待好幾組運(yùn)算結(jié)果后才能輸出本級(jí)的第一組輸出數(shù)據(jù)。sel=20時(shí)，第三級(jí)輸出第一組數(shù)據(jù)。
第四級(jí)和第五級(jí)的時(shí)序分析類(lèi)似第三級(jí)，只是第五級(jí)的輸出是一路數(shù)據(jù)(整個(gè)FFT運(yùn)算的最終結(jié)果)，這里不再贅述。
數(shù)據(jù)精度控制
由(1)、(2)兩式容易得出如下不等式：
                  
(3)
從(3)式可以看出，各級(jí)蝶形運(yùn)算后輸出的值一般是逐級(jí)增大的，所以在運(yùn)算中需要擴(kuò)位。如前所述，第一級(jí)和第二級(jí)的蝶形運(yùn)算主要是加減運(yùn)算，其輸出數(shù)據(jù)只需擴(kuò)展一位。而從第三級(jí)開(kāi)始，旋轉(zhuǎn)因子開(kāi)始有復(fù)數(shù)出現(xiàn)，而且其實(shí)部和虛部都是小數(shù)，在硬件實(shí)現(xiàn)中是不能表示小數(shù)的，在計(jì)算代入的時(shí)候都是放大若干倍后的整數(shù)，運(yùn)算完要縮小一定的倍數(shù)，即某些運(yùn)算環(huán)節(jié)的數(shù)據(jù)需要進(jìn)行一定的截位處理(縮小)。顯然，進(jìn)行截位處理會(huì)給運(yùn)算帶來(lái)誤差，截位處理的原則是前面級(jí)的運(yùn)算作較少的截位處理，盡量將較長(zhǎng)的截位處理放在最后一級(jí)進(jìn)行，保證整個(gè)FFT運(yùn)算的精度達(dá)到要求。
設(shè)計(jì)優(yōu)化
在FPGA設(shè)計(jì)中，首先要保證指標(biāo)達(dá)到要求，在此前提下，盡可能優(yōu)化設(shè)計(jì)，減少設(shè)計(jì)占用資源。在旋轉(zhuǎn)因子的量化上，在盡可能少的數(shù)據(jù)位數(shù)和使運(yùn)算保持盡可能高的精度這兩點(diǎn)上做一下權(quán)衡，盡可能節(jié)省硬件資源。
在蝶形運(yùn)算中，對(duì)于輸入數(shù)據(jù)與旋轉(zhuǎn)因子，要在某一個(gè)時(shí)鐘得到其運(yùn)算結(jié)果，需要4個(gè)實(shí)數(shù)乘法器和2個(gè)實(shí)數(shù)加法器，做一下變換得到如下結(jié)果：
                             
(4)
                             
(5)
即可以用3個(gè)實(shí)數(shù)乘法器和5個(gè)實(shí)數(shù)加法器實(shí)現(xiàn)復(fù)乘，在FPGA的硬件實(shí)現(xiàn)中，一個(gè)陣列乘法器所需要的資源遠(yuǎn)遠(yuǎn)大于加法器，所以用(4)、(5)來(lái)實(shí)現(xiàn)復(fù)乘以節(jié)省資源。
因?yàn)镼uartus II軟件本身對(duì)VHDL語(yǔ)言的綜合能力不強(qiáng)，所以設(shè)計(jì)完成后，可以先用Synplify軟件對(duì)設(shè)計(jì)進(jìn)行編譯綜合，然后將相應(yīng)的vqm文件在Quartus II 軟件下編譯綜合和適配，可以達(dá)到占用較少的芯片資源和較高的最高時(shí)鐘頻率fmax。

仿真驗(yàn)證及結(jié)論
本設(shè)計(jì)選用一片Altera公司的Stratix系列EP1S20芯片實(shí)現(xiàn)，它內(nèi)嵌大量的DSP塊(包括硬件乘法器/硬件累加器和流水線結(jié)構(gòu))，適合于高速數(shù)字信號(hào)處理和各類(lèi)算法的實(shí)現(xiàn)。本設(shè)計(jì)的編譯結(jié)果為：邏輯資源(LEs)占用32％，DSP塊資源占用65％，最高時(shí)鐘頻率fmax=85.3MHz。圖6為Quartus II軟件環(huán)境下的時(shí)序仿真結(jié)果，輸入是經(jīng)過(guò)倒序處理的兩路12bit的復(fù)數(shù)數(shù)據(jù)data1re、data1im和data2re、data2im，輸出為16bit的一路復(fù)數(shù)數(shù)據(jù)doutputre、doutputim，第一輪運(yùn)算從第一組數(shù)據(jù)輸入到第五級(jí)輸出第一組FFT運(yùn)算結(jié)果只延時(shí)了44個(gè)時(shí)鐘周期，此后便是連續(xù)輸出的串行數(shù)據(jù)流。由仿真可知該設(shè)計(jì)達(dá)到了實(shí)時(shí)高速處理要求，實(shí)現(xiàn)了預(yù)期目標(biāo)。■

 參考文獻(xiàn)
1 褚振勇,翁木云．FPGA設(shè)計(jì)及應(yīng)用. 西安：西安電子科技大學(xué)出版社，2002
2 戴明楨．?dāng)?shù)字信號(hào)處理的硬件實(shí)現(xiàn). 北京：航空工業(yè)出版社，1998
3 侯伯亨，顧新．VHDL硬件描述語(yǔ)言與數(shù)字邏輯電路設(shè)計(jì).西安：西安電子科技大學(xué)出版社，2000
4 丁玉美，高西全．?dāng)?shù)字信號(hào)處理. 西安電子科技大學(xué)出版社, 2001

(收稿日期：2003-07-22)