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

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

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