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

在每一步，5 000個(gè)輸入電文與5 000個(gè)本地電文點(diǎn)對(duì)點(diǎn)相乘，相乘結(jié)果加到一起。包含本地碼與輸入碼所有可能的乘積需要5 000步，乘積中最高幅值被記錄下，若大于門(mén)限值，就是我們的期望值。
從基本原理上講，這種方法與滑動(dòng)相關(guān)法是等同的，都是通過(guò)滑動(dòng)碼片來(lái)尋找最大值。不同的是，循環(huán)相關(guān)法每一次滑動(dòng)后不用逐一相乘后相加，而是將時(shí)域信號(hào)進(jìn)行快速傅里葉變換(FFT)轉(zhuǎn)換成頻域信號(hào)，在頻域中求循環(huán)相關(guān)運(yùn)算，直接求出了5 000次滑動(dòng)中每一次滑動(dòng)的相關(guān)值。在硬件實(shí)現(xiàn)中，可以利用自帶的IP核直接進(jìn)行FFT運(yùn)算，這大大節(jié)約了資源。FFT的運(yùn)算量分析在后文中將進(jìn)行介紹。
1．2．2 具體步驟
采用如上所述的基于FFT的循環(huán)相關(guān)捕獲方法，假定捕獲的頻率搜索范圍是±10 kHz，步進(jìn)1 kHz，總共有21個(gè)頻率分量。本地碼lsi可表示為：

式中：下標(biāo)s代表衛(wèi)星編號(hào)，下標(biāo)i=1，2，…，21，Cs是衛(wèi)星s的C／A碼，fi=fc，-10，-9，…，9，10 kHz。這21組數(shù)據(jù)代表了間隔1 kHz的21個(gè)頻率。將他們與輸入信號(hào)進(jìn)行相關(guān)運(yùn)算，如果本地產(chǎn)生信號(hào)的C／A碼和頻率都正確的話，當(dāng)C／A碼相位對(duì)準(zhǔn)時(shí)，輸出達(dá)到峰值。
對(duì)輸入數(shù)據(jù)進(jìn)行捕獲操作的具體步驟如下：
(1)對(duì)1 ms的輸人數(shù)據(jù)x(n)進(jìn)行FFT變換，將輸入數(shù)據(jù)變換到頻域X(k)，n=k=0～4 999；
(2)取X(k)的復(fù)共軛，值為X*(k)；
(3)用式(2)生成21個(gè)本地碼lsi(n)，i=1，2，…，21。每個(gè)lsi(n)都有5 000個(gè)數(shù)據(jù)點(diǎn)。
(4)對(duì)lsi(n)取FFT，轉(zhuǎn)換為頻域中的Lsi(k)。
(5)將Lsi(k)與X*(k)逐點(diǎn)相乘，結(jié)果為Rsi(k)。
(6)求Rsi(k)的FFT逆變換，變換到時(shí)域rsi(n)，求絕對(duì)值|rsi(n)|，總共有105 000(5 000×21)個(gè)|rsi(n)|。
(7)在輸入電文200 ns的時(shí)間分辨率和載波頻率為1 kHz分辨率的條件下，|rsi(n)|最大值中的第n位和第i個(gè)載波頻率給出了C／A碼的初始點(diǎn)。
圖3給出了基于FFT的捕獲流程示意圖。

2 不同捕獲方法的計(jì)算量比較
從理論上講，滑動(dòng)相關(guān)法與基于FFT的循環(huán)相關(guān)捕獲法都是利用數(shù)據(jù)點(diǎn)進(jìn)行相關(guān)計(jì)算并比較求得最大值。其不同之處在于計(jì)算量的差距上，采用基于FFT的循環(huán)相關(guān)法計(jì)算量大大的減少，下面對(duì)其進(jìn)行分析。
2．1 傳統(tǒng)滑動(dòng)相關(guān)法
使用傳統(tǒng)滑動(dòng)相關(guān)法進(jìn)行捕獲，考慮21個(gè)多普勒頻率分量，由于它們進(jìn)行相同的操作，只對(duì)這21組數(shù)據(jù)的某一組進(jìn)行討論。
輸入數(shù)據(jù)和C／A碼各含有5 000個(gè)數(shù)據(jù)點(diǎn)，根據(jù)滑動(dòng)相關(guān)法的原理，要將C／A碼滑動(dòng)5 000次，每滑動(dòng)一次碼片都要將C／A碼與數(shù)據(jù)進(jìn)行5 000點(diǎn)的復(fù)乘，這樣，在每個(gè)頻率分量上要進(jìn)行5 000×5 000次乘法運(yùn)算，則21個(gè)頻率分量共進(jìn)行：
S=5 000×5 000×21=5．25×108 (3)
次運(yùn)算。由此可見(jiàn)，這種方法在硬件實(shí)現(xiàn)中非常浪費(fèi)資源。
2．2 基于FFT的循環(huán)相關(guān)法
2．2．1 FFT算法計(jì)算量簡(jiǎn)介
采用快速FFT／IFFT運(yùn)算，可以顯著降低運(yùn)算的復(fù)雜度，在這里簡(jiǎn)單介紹一下如何計(jì)算IFFT的運(yùn)算量。FFT的運(yùn)算量與此相同，不做贅述。
對(duì)于常用的基2IFFT算法來(lái)說(shuō)，其復(fù)數(shù)乘法的次數(shù)僅為(N／2)log N。隨著N的增加，算法復(fù)雜度之間的差距越明顯，IDFT的計(jì)算復(fù)雜度會(huì)隨著N的增加而呈現(xiàn)二次方增長(zhǎng)，IFFT的計(jì)算復(fù)雜度的增加速度只是稍微快于線形變化。
對(duì)于計(jì)算點(diǎn)數(shù)比較多的系統(tǒng)，可以采用基4FFT算法。在4點(diǎn)的IFFT運(yùn)算中，只存在與{1，-1，j，-j)的相乘運(yùn)算，因此不需要采用完整的乘法器來(lái)實(shí)施這種乘法，只需要通過(guò)簡(jiǎn)單地加、減以及交換實(shí)部和虛部的運(yùn)算(當(dāng)與-j，j相乘時(shí))來(lái)實(shí)現(xiàn)這種乘法。在基4算法中，IFFT變換可以被分為多個(gè)4點(diǎn)的IFFT變換，這樣就只需要在兩個(gè)級(jí)別之間執(zhí)行完整的乘法操作。因此，N點(diǎn)的基4IFFT算法中只需要執(zhí)行(3／8)·N·(log N-2)次復(fù)數(shù)乘法或相位旋轉(zhuǎn)，以及N·log N次復(fù)數(shù)加法。