頻分分路中高速FFT的實現

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

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

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

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

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

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

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