簡化核函數(shù)FFT運(yùn)算復(fù)雜度和動(dòng)態(tài)性能的優(yōu)化

畢廷鋒,周 濤,李 濤

(電子信息控制重點(diǎn)實(shí)驗(yàn)室,成都610036)

1 引 言

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

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

上述文獻(xiàn)都沒有對簡化核FFT的計(jì)算復(fù)雜度和動(dòng)態(tài)性能進(jìn)行比較全面的分析?；诖?本文首先闡述了FFT核函數(shù)的簡化原理和6種簡化模型,指出簡化核函數(shù)FFT在提高運(yùn)算速度的同時(shí),會(huì)降低接收機(jī)的瞬時(shí)動(dòng)態(tài)范圍(IDR),這就有必要優(yōu)化其處理時(shí)間和動(dòng)態(tài)性能。由于6種簡化模型的處理時(shí)間和動(dòng)態(tài)之間并不是線性的反比關(guān)系,這為兩者的優(yōu)化提供了可能。本文接下來基于Cooley-Tukey算法,分析6種核函數(shù)簡化點(diǎn)數(shù)的FFT運(yùn)算量;然后對接收機(jī)帶寬內(nèi)步進(jìn)單頻信號的瞬間動(dòng)態(tài)做了統(tǒng)計(jì)分析,用其平均值和穩(wěn)定性來評價(jià)6種簡化點(diǎn)數(shù)的動(dòng)態(tài)性能;最后經(jīng)過綜合比較,得到運(yùn)算時(shí)間較少、動(dòng)態(tài)性能較優(yōu)的核函數(shù)簡化方式。

2 簡化核函數(shù)FFT算法

FFT的旋轉(zhuǎn)因子ejφ是個(gè)浮點(diǎn)值,而且有N種選擇,在實(shí)現(xiàn)中涉及到復(fù)數(shù)的浮點(diǎn)乘法計(jì)算,運(yùn)算量比較大。如果能進(jìn)一步將旋轉(zhuǎn)因子縮減為有限個(gè)值(<

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

本質(zhì)上,旋轉(zhuǎn)因子的簡化是把單位圓上N個(gè)旋轉(zhuǎn)因子作了矢量量化和近似,變?yōu)?N個(gè)定點(diǎn)數(shù)矢量 。圖1 是 4、8、12、16、24 、32 點(diǎn)簡化原理的示意 ,黑點(diǎn)表示旋轉(zhuǎn)因子簡化后的取值。

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

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

由于旋轉(zhuǎn)因子的量化是一個(gè)非線性過程,其次用定點(diǎn)數(shù)近似浮點(diǎn)數(shù),頻譜分析結(jié)果和標(biāo)準(zhǔn)FFT會(huì)存在誤差,產(chǎn)生頻譜雜散,因此,簡化核FFT在提高運(yùn)算速度的同時(shí),會(huì)降低接收機(jī)的瞬時(shí)動(dòng)態(tài)范圍。由于6種簡化方式所取的定點(diǎn)數(shù)不同,對浮點(diǎn)數(shù)的近似程度不一樣,使得處理時(shí)間和IDR性能并不是線性的反比關(guān)系。在上述的6種簡化模型中,并不是簡化點(diǎn)數(shù)越少,IDR性能越差。因此,在其中尋找兼顧計(jì)算時(shí)間和動(dòng)態(tài)性能的簡化方式是可能的。

不同F(xiàn)FT結(jié)構(gòu)的蝶形數(shù)目不一樣,它們的計(jì)算量也有差別。另外,簡化點(diǎn)數(shù)越多,FFT計(jì)算量越大?；诳焖偬幚硇阅艿目紤],本文討論的簡化核FFT采用Cooley-Tukey算法,并用較少的簡化點(diǎn)數(shù):4、8、12、16、24、32 點(diǎn)。

3 運(yùn)算復(fù)雜度分析

3.1 旋轉(zhuǎn)因子簡化后的蝶形乘法

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

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

另外,如果旋轉(zhuǎn)因子的矢量半徑放大到R,為了恢復(fù)原先采用單位圓旋轉(zhuǎn)因子時(shí)的計(jì)算結(jié)果,應(yīng)在蝶形乘法之后除以R。由于6種簡化方式中R均是2的冪次,該除法用移位即可實(shí)現(xiàn)。

3.2 6種簡化核FFT的運(yùn)算量

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

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

表1 M點(diǎn)簡化核FFT的運(yùn)算量Table 1The computation complexity of M-point simplified kernel function FFT

4 動(dòng)態(tài)性能分析

FFT作為DFT的快速算法,并沒有嚴(yán)格的解析表達(dá)式,外加FFT核函數(shù)的量化是非線性過程,因此很難用解析方式推導(dǎo)簡化核FFT的運(yùn)算結(jié)果。本文通過仿真來分析不同簡化點(diǎn)數(shù)Cooley-Turkey FFT的動(dòng)態(tài)性能。

4.1 簡化核函數(shù)的雜散效應(yīng)

FFT旋轉(zhuǎn)因子的非線性簡化過程會(huì)產(chǎn)生信號峰值外的很多雜散分量,尤其在簡化點(diǎn)數(shù)較少時(shí),這會(huì)影響到接收機(jī)的動(dòng)態(tài)性能。

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

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

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

可見,1 GHz點(diǎn)頻時(shí),4點(diǎn)簡化的雜散峰值約-10 dB,事實(shí)上帶寬內(nèi)其他點(diǎn)頻產(chǎn)生的雜散峰值甚至更大。而簡化點(diǎn)數(shù)越多,結(jié)果越接近標(biāo)準(zhǔn)FFT,雜散效應(yīng)減弱,32點(diǎn)簡化的雜散明顯減少,最大雜散值約-26 dB。

4.2 雜散的分布規(guī)律

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

對此,在 0～5 GHz帶寬內(nèi)設(shè)置1 000個(gè)步進(jìn)點(diǎn)頻,步進(jìn)頻率為5 MHz,考察雜散峰值隨著頻率的變化情況,有圖4和圖5所示的變化規(guī)律。

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

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

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

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

因此,取前1/4頻段0～1.25G內(nèi)250個(gè)頻點(diǎn)的雜散峰值做統(tǒng)計(jì)分析,其平均值和波動(dòng)性如表2所示。

表2 雜散峰值分布規(guī)律的統(tǒng)計(jì)結(jié)果Table 2 The statistical results of peak spur′s distribution

表2結(jié)果中可得:

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

(2)用標(biāo)準(zhǔn)差衡量動(dòng)態(tài)性能的穩(wěn)定程度,則8點(diǎn)簡化的穩(wěn)定性最好,其他簡化方式的波動(dòng)較大;

(3)綜合平均值和穩(wěn)定性來看,12點(diǎn)以上的動(dòng)態(tài)性能隨著輸入頻率的波動(dòng)性較強(qiáng),8點(diǎn)的動(dòng)態(tài)性能比較穩(wěn)定,但動(dòng)態(tài)范圍比12點(diǎn)小6 dB,而12點(diǎn)的動(dòng)態(tài)范圍達(dá)到約-20 dB,但沒有8點(diǎn)穩(wěn)定。

4.3 運(yùn)算復(fù)雜度和動(dòng)態(tài)性能的優(yōu)化

綜合比較6種簡化點(diǎn)數(shù)的運(yùn)算時(shí)間和瞬時(shí)動(dòng)態(tài)性能:32點(diǎn)簡化的動(dòng)態(tài)約-26 dB,是6種簡化方式中平均動(dòng)態(tài)最好的,但其運(yùn)算量較大;而8點(diǎn)和12點(diǎn)的運(yùn)算量較少,兩者之中,8點(diǎn)的動(dòng)態(tài)性能比較穩(wěn)定,平均值比12點(diǎn)小6 dB;12點(diǎn)的動(dòng)態(tài)較大,但頻域分布的波動(dòng)性也強(qiáng)。從計(jì)算復(fù)雜度來看,8點(diǎn)簡化的FFT運(yùn)算沒有移位操作,僅需要進(jìn)行NlbN次復(fù)加,12點(diǎn)運(yùn)算還需要移位NlbN次,積累時(shí)間 N較小時(shí),兩者的運(yùn)算量差別不大,當(dāng)積累時(shí)間較長時(shí),8點(diǎn)簡化FFT的運(yùn)算優(yōu)勢明顯。

5 結(jié)束語

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

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

[2]周濤.電子戰(zhàn)中的單比特?cái)?shù)字化接收技術(shù)[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.