簡化核函數FFT運算復雜度和動態性能的優化

畢廷鋒,周 濤,李 濤

(電子信息控制重點實驗室,成都610036)

1 引 言

電子戰中的數字偵察接收機需要較大的瞬時帶寬和很高的接收靈敏度,這勢必帶來大量數據需要實時處理,而目前的數字硬件處理速度有限,如何對接收機前端帶來的高速率采樣數據進行快速處理是目前電子戰接收機發展中的瓶頸,也是亟待解決的問題。

并行處理通過增加資源面積來換取處理速度的提升,可以做到數據的實時流水,然而其資源開銷較大,對流水處理的控制時序要求也比較高。實時處理的另一種思路是通過改進或優化處理算法本身來提升處理速度,簡化核函數的FFT[1]就是一種針對FFT接收機的有效處理算法,其乘法操作不需要復雜的浮點計算,而是用定點數移位和加減來代替,因此能夠大大提高接收機的處理速度,處理時間顯著減少,文獻[2]中也指出這種處理方法在寬帶數字接收機的快速處理領域具有很強的應用價值。文獻[3]具體介紹了核函數的簡化原理。文獻[4]把4點和12點的簡化核函數應用到了寬帶數字接收機的核心FFT算法里,大大降低了算法的硬件資源消耗。文獻[5]中提出對FFT的每一級采用不同的核函數簡化方式,其單音信號的動態性能改善達到45 dB,但算法實現比較復雜,簡化點數甚至到128點。文獻[6]對簡化核函數的DFT濾波信道的動態性能進行了詳細分析,指出簡化核函數的FFT信道性能要比DFT信道要差,但沒有具體分析簡化核FFT的動態性能。

上述文獻都沒有對簡化核FFT的計算復雜度和動態性能進行比較全面的分析。基于此,本文首先闡述了FFT核函數的簡化原理和6種簡化模型,指出簡化核函數FFT在提高運算速度的同時,會降低接收機的瞬時動態范圍(IDR),這就有必要優化其處理時間和動態性能。由于6種簡化模型的處理時間和動態之間并不是線性的反比關系,這為兩者的優化提供了可能。本文接下來基于Cooley-Tukey算法,分析6種核函數簡化點數的FFT運算量;然后對接收機帶寬內步進單頻信號的瞬間動態做了統計分析,用其平均值和穩定性來評價6種簡化點數的動態性能;最后經過綜合比較,得到運算時間較少、動態性能較優的核函數簡化方式。

2 簡化核函數FFT算法

FFT的旋轉因子ejφ是個浮點值,而且有N種選擇,在實現中涉及到復數的浮點乘法計算,運算量比較大。如果能進一步將旋轉因子縮減為有限個值(<

式(1)表示旋轉因子 ejφ的 4點簡化函數G(ejφ),可見,4 點簡化 G(ejφ)和 ejφ的誤差是比較大的。簡化誤差 G(ejφ)-ejφ是產生頻譜雜散的原因,隨著簡化點數的增加,G(ejφ)越接近ejφ,雜散就會減少。

本質上,旋轉因子的簡化是把單位圓上N個旋轉因子作了矢量量化和近似,變為 N個定點數矢量 。圖1 是 4、8、12、16、24 、32 點簡化原理的示意 ,黑點表示旋轉因子簡化后的取值。

圖 1 旋轉因子的 4、8、12、16、24、32點簡化示意Fig.1 Simplified kernel function of 4,8,12,16,24,32 points

增加簡化點數時,為了使定點矢量更好地近似到量化后的浮點矢量附近,可以把單位圓放大 R倍。便于硬件計算,一般取R為2的冪次。圖1的12、16、24、32點簡化表示了第一象限的取值,其他象限和第一象限對稱,R分別取值2、8、4、8。

由于旋轉因子的量化是一個非線性過程,其次用定點數近似浮點數,頻譜分析結果和標準FFT會存在誤差,產生頻譜雜散,因此,簡化核FFT在提高運算速度的同時,會降低接收機的瞬時動態范圍。由于6種簡化方式所取的定點數不同,對浮點數的近似程度不一樣,使得處理時間和IDR性能并不是線性的反比關系。在上述的6種簡化模型中,并不是簡化點數越少,IDR性能越差。因此,在其中尋找兼顧計算時間和動態性能的簡化方式是可能的。

不同FFT結構的蝶形數目不一樣,它們的計算量也有差別。另外,簡化點數越多,FFT計算量越大。基于快速處理性能的考慮,本文討論的簡化核FFT采用Cooley-Tukey算法,并用較少的簡化點數:4、8、12、16、24、32 點。

3 運算復雜度分析

3.1 旋轉因子簡化后的蝶形乘法

N點Cooley-Tukey FFT的第 v級旋轉因子為它們的取值落在第三象限和第四象限,經過M點簡化,第三象限和第四象限共有M/2個旋轉因子簡化值。因此,在N點FFT計算流程中,每個簡化值約用到N/(M/2)次,即每個簡化值要參與2N/M次復乘運算。

顯然,簡化核FFT保留了標準FFT原有的加法次數,增加的是用來取代乘法運算的移位數和加法數。蝶形輸入對6種簡化旋轉因子的乘法只涉及到對定點數 1、2 、3、4、6、8 的乘法。具體來講,蝶形輸入乘以 1、2、4、8,只需對輸入分別做 0、1、2、3 次二進制移位;而3可以表示為 21+1,6表示為22+21,因此蝶形輸入乘以3和6,需要對輸入分別移位1次和2次,還要分別做1次加法。

另外,如果旋轉因子的矢量半徑放大到R,為了恢復原先采用單位圓旋轉因子時的計算結果,應在蝶形乘法之后除以R。由于6種簡化方式中R均是2的冪次,該除法用移位即可實現。

3.2 6種簡化核FFT的運算量

基于3.1節的分析,假定 x表示簡化后的旋轉因子取值,mx和nx分別表示蝶形輸入與x相乘時需要進行移位和加法的次數,sM表示蝶形計算結果除以放大倍數R需要的移位次數,6種簡化方式的sM值依次是 0、0、2、6、4、6。這樣,可以得到 M 點簡化核FFT的復移位數和復加數的計算公式如下:

其中,式(2)的 NlbN/2是蝶形個數,式(3)的 NlbN是原有的復加數。表1是6種簡化點數所需的移位和加減操作數,都能在硬件實現的一個時鐘周期內完成,因此從總耗時來看,計算一次完整的M點簡化核FFT,16點和32點簡化的運算時間最多,其次是24點,接下來是12點,時間最少的是4點和8點,只對蝶形輸入做加法。

表1 M點簡化核FFT的運算量Table 1The computation complexity of M-point simplified kernel function FFT

4 動態性能分析

FFT作為DFT的快速算法,并沒有嚴格的解析表達式,外加FFT核函數的量化是非線性過程,因此很難用解析方式推導簡化核FFT的運算結果。本文通過仿真來分析不同簡化點數Cooley-Turkey FFT的動態性能。

4.1 簡化核函數的雜散效應

FFT旋轉因子的非線性簡化過程會產生信號峰值外的很多雜散分量,尤其在簡化點數較少時,這會影響到接收機的動態性能。

假設采樣率為10 GHz,信號積累時間N=1 024點。若把主瓣附近幾個頻域分量除去,余下的分量看作雜散,則圖2和圖3是1GHz點頻信號做4點和32點簡化FFT的頻譜,分別和標準FFT做了比較,箭頭指出了簡化核函數后的最大雜散值。

圖2 4點簡化FFT的頻譜Fig.2 The frequency spectrum of 4-point simplified kernel function FFT

圖3 32點簡化FFT的頻譜Fig.3 The frequency spectrum of 32-point simplified kernel function FFT

可見,1 GHz點頻時,4點簡化的雜散峰值約-10 dB,事實上帶寬內其他點頻產生的雜散峰值甚至更大。而簡化點數越多,結果越接近標準FFT,雜散效應減弱,32點簡化的雜散明顯減少,最大雜散值約-26 dB。

4.2 雜散的分布規律

第2節指出,簡化FFT的雜散是由簡化函數的誤差 G(ejφ)-ejφ引起 ,而 G(ejφ)矢量在 4 個象限的取值是對稱的,因此誤差 G(ejφ)-ejφ也呈象限對稱。另外,從傅里葉變換相關角度來講,輸入信號與核函數ejφ的相關在圓周的某一點取得最大值,那么該點核函數表示的頻率就是信號的頻率。因此在全頻段內,G(ejφ)-ejφ呈象限對稱,雜散譜也應該是呈象限對稱的。

對此,在 0～5 GHz帶寬內設置1 000個步進點頻,步進頻率為5 MHz,考察雜散峰值隨著頻率的變化情況,有圖4和圖5所示的變化規律。

圖4 4點、8點、12點的雜散峰值分布規律Fig.4 The peak spur′s distribution of simplified kernel function FFT with 4,8,12 points

圖5 16點、24點、32點的雜散峰值分布規律Fig.5 The peak spur′s distribution of simplified kernel function FFT with 16,24,32 points

可見,雜散峰值的頻域分布呈周期重復,共有4個變化周期,整個帶寬內依次呈鏡像對稱,對應于圓周上的象限對稱,符合理論分析。因此前1/4頻段0～1.25 GHz的雜散情況代表了其他3個頻段。而0～1.25 GHz內不同頻點的雜散峰值在一定范圍內波動,原因分析為:離散傅里葉變換可以看作是一組均勻的梳狀濾波器組,一個點頻信號可以通過某一濾波器,而在其他濾波信道沒有輸出。核函數簡化后的濾波器組不是均勻狀,有周期性起伏,如圖6所示,這樣相同功率的點頻信號位于不同濾波信道內,其雜散峰值就有波動。

圖6 簡化核FFT的濾波信道Fig.6 The filtering channel of simplified kernel function FFT

因此,取前1/4頻段0～1.25G內250個頻點的雜散峰值做統計分析,其平均值和波動性如表2所示。

表2 雜散峰值分布規律的統計結果Table 2 The statistical results of peak spur′s distribution

表2結果中可得:

(1)從瞬時動態的平均值來看,4點簡化的最小,約-10 dB,12點簡化的動態達到約-20 dB,32點達到-26 dB,因此,4點到12點、12點到32點的提升幅度比較明顯,分別改善了10 dB和5 dB;

(2)用標準差衡量動態性能的穩定程度,則8點簡化的穩定性最好,其他簡化方式的波動較大;

(3)綜合平均值和穩定性來看,12點以上的動態性能隨著輸入頻率的波動性較強,8點的動態性能比較穩定,但動態范圍比12點小6 dB,而12點的動態范圍達到約-20 dB,但沒有8點穩定。

4.3 運算復雜度和動態性能的優化

綜合比較6種簡化點數的運算時間和瞬時動態性能:32點簡化的動態約-26 dB,是6種簡化方式中平均動態最好的,但其運算量較大;而8點和12點的運算量較少,兩者之中,8點的動態性能比較穩定,平均值比12點小6 dB;12點的動態較大,但頻域分布的波動性也強。從計算復雜度來看,8點簡化的FFT運算沒有移位操作,僅需要進行NlbN次復加,12點運算還需要移位NlbN次,積累時間 N較小時,兩者的運算量差別不大,當積累時間較長時,8點簡化FFT的運算優勢明顯。

5 結束語

簡化核函數FFT用移位和加法操作取代了乘法計算,顯著地減少了處理時間。簡化點數越少,計算時間越快,但是旋轉因子的簡化會產生頻譜雜散,特別是在簡化點數較少的情況下,影響到FFT的動態性能。由于各種簡化點數所取的定點數不同,對浮點數的近似程度不一樣,導致處理時間和IDR性能并不是線性的反比關系,這為兩者之間的優化提供了可能。本文綜合分析了6種簡化點數下FFT的計算量和瞬時動態性能,通過比較分析,得到在兩者間優化的相關結論,對寬帶數字接收機的性能優化有工程參考價值,并可以應用到電子偵察等快速信號處理領域。

[1]Tsui J.寬帶數字接收機[M].楊小牛,譯.北京:電子工業出版社,2002.Tsui J.Wideband digital receiver[M].Translated by YANG Xiao-niu.Beijing:Publishing House of Electronic Industry,2002.(in Chinese)

[2]周濤.電子戰中的單比特數字化接收技術[J].電子對抗,2006(5):6-10.ZHOU Tao.Technique of Monobit Digital Receiver in Electronic Warfare[J].Electronic Warfare,2006(5):6-10.(in Chinese)

[3]Schamus,et al.Quad-bit Kernel Function Algorithm and Receiver:US,6 690 315 B1[P].2004.

[4]Chen C H,George K,McCormick W,et al.Design and Performance Evaluationof a 2.5-Gsps Digital Receiver[J].IEEE Transactions on Instrumentation and Measurement,2005,54(3):1089-1099.

[5]Sarathy V.High Spurious-Free Dynamic Range Digital WidebandReceiver for Multiple Signal Detection and Tracking[D].Dayton,Ohio:Wright State University,2007:35-45.

[6]Grajal J,Lopez-Risueno R B G,Sanz J M.Analysis and Characterization of a Mono-bit Receiver for Electronic Warfare[J].IEEE Transactions on Aerospace and Electronic Systems,2003,39(1):244-258.