擴頻信號基于FFT碼捕獲的計算量分析

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

2．2．2 計算量分析
根據1．2．2節中介紹的循環相關捕獲的具體步驟以及FFT算法的計算量，對基于FFT的循環相關捕獲法計算量分析如下。
首先，根據式(2)將21個頻率分量下的C／A碼與射頻相乘，需要運算次數為：
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)
這里數據點數N=5 000，則總計算量為915 180次，與滑動相關法相比，少了3個數量級。

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