擴(kuò)頻信號(hào)基于FFT碼捕獲的計(jì)算量分析

基4蝶型算法可以用于高效的計(jì)算大規(guī)模的IFFT。圖5說明了利用基4蝶型算法實(shí)施16點(diǎn)的IFFT，其中包括2級運(yùn)算，每級內(nèi)包含4個(gè)基4蝶型運(yùn)算，在兩級之間存在中間過渡級別，用于對16個(gè)中間過渡結(jié)果實(shí)施相位旋轉(zhuǎn)ωi，其中ωi=exp(j2πi／N)。在N=16的情況下，當(dāng)i=0，2，4，8，12時(shí)，與ωi相乘就可以簡化為與{1，-1，j，-j)相乘。

2．2．2 計(jì)算量分析
根據(jù)1．2．2節(jié)中介紹的循環(huán)相關(guān)捕獲的具體步驟以及FFT算法的計(jì)算量，對基于FFT的循環(huán)相關(guān)捕獲法計(jì)算量分析如下。
首先，根據(jù)式(2)將21個(gè)頻率分量下的C／A碼與射頻相乘，需要運(yùn)算次數(shù)為：
S1=21·N (4)
另外，N點(diǎn)基4FFT的運(yùn)算量為(3／8)·N·(log N-2)，考慮21個(gè)多普勒頻率分量以及FFT和IFFT雙向變換，計(jì)算量為：
S2=2·21·(3／8)·N·(log N-2) (5)
因此，總的計(jì)算量為：
S=S1+S2=21·N·[(3／4)(log N-2)+1] (6)
這里數(shù)據(jù)點(diǎn)數(shù)N=5 000，則總計(jì)算量為915 180次，與滑動(dòng)相關(guān)法相比，少了3個(gè)數(shù)量級。

3 結(jié)語
本文從擴(kuò)頻信號(hào)捕獲的角度出發(fā)，描述了傳統(tǒng)捕獲方法和基于FFT的快速捕獲方法的原理和步驟，并對不同捕獲方法的計(jì)算量進(jìn)行了分析和比較。在文中可以看到，基于FFT的循環(huán)相關(guān)捕獲法其計(jì)算量比傳統(tǒng)方法少了3個(gè)數(shù)量級以上，該方法在硬件實(shí)現(xiàn)中，與傳統(tǒng)滑動(dòng)相關(guān)法相比大大節(jié)省了資源，減少了耗時(shí)，是一種比較好的捕獲方法。