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

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

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

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

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

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

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

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