一種低運(yùn)算量GNSS接收機(jī)快速捕獲方法

程向紅，徐文杰

（1. 微慣性儀表與先進(jìn)導(dǎo)航技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，南京 210096；2. 東南大學(xué) 儀器科學(xué)與工程學(xué)院，南京 210096）

北斗三號(hào)系統(tǒng)的全面建成使全球衛(wèi)星導(dǎo)航系統(tǒng)（GNSS）在軍事與民用領(lǐng)域的用途更加廣泛，特色服務(wù)的全面部署也使得GNSS的應(yīng)用場(chǎng)景豐富多變，包括交通運(yùn)輸、農(nóng)林漁業(yè)、武器裝備等專業(yè)領(lǐng)域[1]，數(shù)十億的智能設(shè)備均集成有GNSS技術(shù)。信號(hào)捕獲是衛(wèi)星信號(hào)接收機(jī)內(nèi)信號(hào)處理的第一步，只有完成了信號(hào)的捕獲，才可能開(kāi)始信號(hào)跟蹤等一系列信號(hào)處理過(guò)程，最終完成位置速度解算（PVT）功能[2]。捕獲階段三維搜索帶來(lái)的數(shù)千萬(wàn)到幾十億次數(shù)字乘法會(huì)消耗大量的功率及軟硬件資源，接收機(jī)從上電到實(shí)現(xiàn)有效定位，花費(fèi)在信號(hào)捕獲上的時(shí)間是所有首次定位時(shí)間（TTFF）環(huán)節(jié)中最冗長(zhǎng)的一部分[3]；又因?yàn)樵S多支持GNSS的設(shè)備，如智能手機(jī)，具有嚴(yán)格的電池容量限制，這使得接收機(jī)的功耗問(wèn)題也十分凸顯[4]。尤其因衛(wèi)星信號(hào)非常微弱，常需要延長(zhǎng)捕獲數(shù)據(jù)長(zhǎng)度、增加相干積分時(shí)間，使得本就龐大的運(yùn)算量成倍增加，因而降低捕獲階段的算法運(yùn)算量，減少捕獲階段花費(fèi)的時(shí)間與其所占的功耗十分必要。低運(yùn)算量的快速捕獲算法也一直是GNSS接收機(jī)的研究熱點(diǎn)。

信號(hào)捕獲主要是利用碼分多址（CDMA）系統(tǒng)偽隨機(jī)噪聲碼（PRN）具有強(qiáng)自相關(guān)性實(shí)現(xiàn)的。自Van Nee[5]提出基于傅里葉變換（FFT）的并行頻率/碼相位的搜索算法以來(lái)，F(xiàn)FT算法便成為實(shí)現(xiàn)衛(wèi)星信號(hào)快速捕獲的核心，基于離散傅里葉變換（DFT）與信號(hào)卷積的關(guān)系，時(shí)域中相關(guān)函數(shù)的運(yùn)算可以轉(zhuǎn)換為頻域的乘法并利用FFT變換極大地減少運(yùn)算量。Hassanieh[6]提出的稀疏傅里葉變換（SFT）利用捕獲結(jié)果的稀疏性實(shí)現(xiàn)捕獲算法的亞線性處理，減少了運(yùn)算時(shí)間。Gao等[7]基于參數(shù)估計(jì)理論提出了多普勒頻移估計(jì)算法，減小多普勒頻移搜索范圍以加快捕獲過(guò)程。楊峰等[8]根據(jù)壓縮感知理論降低了捕獲運(yùn)算量，并優(yōu)化了重構(gòu)矩陣，使捕獲算法具有良好捕獲效率。Nie等[9]利用慣性導(dǎo)航系統(tǒng)輔助對(duì)星歷進(jìn)行預(yù)估，減少多普勒頻移與碼相位搜索空間以實(shí)現(xiàn)快速捕獲。許睿等[10]利用多級(jí)搜索和降采樣策略，通過(guò)粗捕獲和精捕獲的結(jié)合實(shí)現(xiàn)了無(wú)模糊快速捕獲。衛(wèi)星信號(hào)的捕獲要求在一定的靈敏度下，降低捕獲階段的運(yùn)算量并保證捕獲結(jié)果的精度以滿足跟蹤環(huán)路的要求，上述算法都對(duì)單個(gè)偽碼周期內(nèi)的捕獲過(guò)程進(jìn)行了優(yōu)化，而長(zhǎng)相干積分時(shí)間下就會(huì)造成算法運(yùn)算量的成倍累積。

本文算法策略借鑒數(shù)據(jù)分塊與降采樣的思想，將采集數(shù)據(jù)二維重排，使多普勒頻移搜索粒度細(xì)化的同時(shí)，只使用一個(gè)偽碼周期內(nèi)的數(shù)據(jù)進(jìn)行運(yùn)算，通過(guò)降采樣操作減少三維搜索階段的運(yùn)算點(diǎn)數(shù)，使得整體運(yùn)算量會(huì)隨著相干積分的時(shí)間延長(zhǎng)與降采樣因子的增大而大幅度降低。最后基于真實(shí)信號(hào)的半物理仿真驗(yàn)證了本文方法對(duì)捕獲效率的提升。

1 GNSS信號(hào)捕獲過(guò)程簡(jiǎn)介

射頻前端將天線接收到的信號(hào)進(jìn)行放大、濾波、降噪和混頻處理后得到的中頻（IF）信號(hào)可以描述為：

其中，A為載波信號(hào)幅度值；fIF為中頻載波頻率；fd為多普勒頻移；φ0為初始載波相位；Ts為采樣周期；τ為傳輸過(guò)程中的時(shí)間延遲；n為時(shí)間離散序列編號(hào)；C(nTs-τ)為偽隨機(jī)噪聲碼，其值為±1；SBOC(nTs-τ)為調(diào)制副載波，若未調(diào)制副載波，該項(xiàng)為1；D(nTs-τ)為導(dǎo)航電文；cos[2π(fIF+fd)nTs+φ0]為載波；η[n]為白噪聲。

捕獲是一個(gè)三維搜索過(guò)程，如圖1所示，第一維是衛(wèi)星號(hào)（PRN碼），如果初始上電沒(méi)有任何輔助信息，則從天線接收的信號(hào)中可能存在的GPS衛(wèi)星的PRN碼數(shù)目是32個(gè)，北斗是37個(gè)，此時(shí)必須窮舉嘗試每一個(gè)可能的PRN，若設(shè)備擁有輔助導(dǎo)航信息，則可減少大量搜索時(shí)間。第二維是偽碼相位τ，首先產(chǎn)生本地偽碼，對(duì)本地偽碼設(shè)置不同的相位，利用偽碼的強(qiáng)自相關(guān)性，將本地偽碼和輸入信號(hào)做相關(guān)運(yùn)算，找到正確的偽碼相位，根據(jù)采樣頻率的大小與實(shí)際需求的碼相位精度確定碼相位搜索靈敏度tbin。第三維是多普勒頻移fd，首先產(chǎn)生本地載波，通過(guò)調(diào)節(jié)本地載波的頻率和輸入信號(hào)相乘并積分，由于不可預(yù)測(cè)初始輸入載波的頻率，需要設(shè)置不同的本地載波頻率值來(lái)測(cè)試；通常根據(jù)衛(wèi)星與載體間的相對(duì)運(yùn)動(dòng)狀態(tài)來(lái)確定搜索范圍，通過(guò)相干積分時(shí)間TI來(lái)確定載波頻率搜索步長(zhǎng)fbin，通過(guò)搜索范圍和搜索步長(zhǎng)確定正向及負(fù)向搜索頻率井個(gè)數(shù)k。

圖1 信號(hào)捕獲的三維搜索圖示Fig.1 3D search diagram of signal acquisition

信號(hào)捕獲的最終目的就是要“粗略”捕獲到載體與衛(wèi)星之間相對(duì)高速移動(dòng)帶來(lái)的多普勒頻移fd與用來(lái)區(qū)分衛(wèi)星、提供測(cè)距信息的偽碼相位延遲τ。

2 低運(yùn)算量GNSS快速捕獲算法設(shè)計(jì)

考慮時(shí)長(zhǎng)為L(zhǎng)ms（L≥1且為整數(shù)）的數(shù)據(jù)，假設(shè)在1 ms時(shí)間內(nèi)，總共有N個(gè)采樣點(diǎn)（N由采樣頻率決定），那么在Lms內(nèi)，有NL個(gè)采樣點(diǎn)，L不超過(guò)導(dǎo)航電文比特跳變周期。將這些采樣點(diǎn)分成L個(gè)數(shù)據(jù)塊，每一個(gè)數(shù)據(jù)塊恰好包含1 ms的數(shù)據(jù)采樣，如圖2所示。

圖2 L ms采樣數(shù)據(jù)分塊Fig.2 L ms sampling divided into data blocks

一般信號(hào)中會(huì)有多顆衛(wèi)星信號(hào)，對(duì)其中一顆衛(wèi)星進(jìn)行分析，PRN為k的衛(wèi)星得到的離散采樣數(shù)據(jù)sk(n)表示為：

其中，n為時(shí)間離散序列編號(hào)，n∈[0,NL-1]；fk為信號(hào)載波頻率，受多普勒頻移影響，每顆衛(wèi)星的載波頻率均不同；vk(nTs)是白噪聲。因?yàn)槭?2)中的載波幅度為1，這里將噪聲功率做歸一化處理。

省略噪聲項(xiàng)，僅考慮信號(hào)部分，如果L長(zhǎng)度小于電文比特周期，則Dk可以看做常數(shù)，偽碼信號(hào)Ck(i)是個(gè)周期函數(shù)，對(duì)GPS和北斗B1I信號(hào)的周期都是1 ms，用離散域表示：

sk(n)信號(hào)中共有三個(gè)分量：｛Dk，Ck，ej2πf knTs｝，其中分量Dk和Ck在不同數(shù)據(jù)塊的相同位置都保持不變，把這L個(gè)數(shù)據(jù)塊相同位置的對(duì)應(yīng)點(diǎn)進(jìn)行疊加，有：

式中，S{sk(n)}是sk(n)中的信號(hào)分量，G(L,fk)是一個(gè)新增益函數(shù)，表示為：

將L段數(shù)據(jù)合成一段數(shù)據(jù)，累加后的數(shù)據(jù)相當(dāng)于原始信號(hào)和G(L,fk)相乘且在ej2πf kiNTs=1時(shí)，G(L,fk)取到最大值L，而該函數(shù)值與fk有關(guān)，使直接對(duì)輸入信號(hào)進(jìn)行塊累加并不能保證原始信號(hào)被放大L倍。引入頻率為Δfk的本地載波頻率補(bǔ)償信號(hào)pk(n)=ej2πΔf knTs，如圖3，將pk(n)與sk(n)相乘，得到載波頻率補(bǔ)償后的新信號(hào)yk(n)：

圖3 頻率補(bǔ)償過(guò)程Fig.3 Frequency compensation process

可以看出pk(n)的引入只改變?cè)驾d波信號(hào)頻率，對(duì)Dk和Ck無(wú)任何影響，噪聲分量也只是旋轉(zhuǎn)一定的相位，并無(wú)功率譜密度變化。對(duì)yk(n)進(jìn)行塊累加得：

其中，fk′=fk+Δfk。當(dāng)fk′NTs是一個(gè)整數(shù)時(shí)，e j2πf k'iNTs=1，G(L,f′k)中的L項(xiàng)累加值均為1，累加和取到最大值L。

因?yàn)镹Ts=1 ms，所以fk’ NTs是一個(gè)整數(shù)的條件等價(jià)于mod(1 kHz)=0，此時(shí)，

即累加后的數(shù)據(jù)塊中信號(hào)強(qiáng)度得到了增強(qiáng)，為了實(shí)現(xiàn)數(shù)據(jù)塊累加，必須對(duì)優(yōu)化的Δfk進(jìn)行搜索，搜索過(guò)程可以通過(guò)串行嘗試不同的Δfk以覆蓋[0, 1 kHz]的范圍。受數(shù)據(jù)塊相同位置采樣信號(hào)的載波相位特點(diǎn)的啟發(fā)，通過(guò)FFT算法來(lái)實(shí)現(xiàn)Δfk搜索，并可通過(guò)SFT算法進(jìn)一步降低整體捕獲運(yùn)算量。將圖3中的數(shù)據(jù)二維重排，如圖4分成二維矩陣的形式，圖中一個(gè)粗框內(nèi)表示一個(gè)中頻采樣點(diǎn)，采樣點(diǎn)之間的箭頭表示數(shù)據(jù)流的方向。從矩陣橫向看，數(shù)據(jù)被分成L個(gè)橫塊，每一個(gè)橫塊表示1 ms的采樣數(shù)據(jù)；從縱向看，數(shù)據(jù)被分成N個(gè)豎塊，每一個(gè)豎塊中有L個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)之間的時(shí)間間隔是1 ms。

圖4 中頻采樣數(shù)據(jù)二維排列Fig.4 Two-dimensional arrangement of IF sampling data

圖5 二維混疊排列Fig.5 Two-dimensional aliasing arrangement

其中β=1…L，豎塊中的采樣頻率是1 kHz，如果把載波頻率分成1 kHz的整數(shù)倍和余數(shù)部分，即

其中F為整數(shù)，0 ＜ Δfk＜1 kHz，則第i個(gè)豎塊的采樣點(diǎn)可簡(jiǎn)化為：

對(duì)這L個(gè)采樣點(diǎn)進(jìn)行FFT變換，得到的結(jié)果為：

式中，ωm=2πmfp/L，m=0, 1…L-1，fp=1 kHz，Δωk=2πΔfk，為簡(jiǎn)便表述將下標(biāo)k去除。對(duì)式(12)進(jìn)行化簡(jiǎn)得：

用Y(i,m)替換第i個(gè)豎塊的數(shù)據(jù)，此時(shí)第m個(gè)橫塊的數(shù)據(jù)則為：

A(m)在第m個(gè)橫塊數(shù)據(jù)內(nèi)是一個(gè)與采樣時(shí)刻無(wú)關(guān)的公共項(xiàng)。對(duì)第m個(gè)橫塊使用FFT捕獲的方法就可以得到全部偽碼相位相關(guān)的運(yùn)算結(jié)果，如圖6所示，唯一區(qū)別在于參與相關(guān)運(yùn)算的中頻數(shù)據(jù)中多了一個(gè)公共項(xiàng)因子A(m)，其?？梢员硎緸椋?/p>

圖6 對(duì)橫塊數(shù)據(jù)進(jìn)行FFT并行捕獲Fig.6 FFT parallel capture of horizontal block data

當(dāng)Δω=ωm時(shí)，式(15)取到最大值L，A(m)就可以看做對(duì)fk中1 kHz以下部分的選頻因子，而fk中1 kHz的部分F是由通過(guò)對(duì)橫塊數(shù)據(jù)進(jìn)行FFT捕獲時(shí)通過(guò)設(shè)定本地載波頻率而確定的。

配置靜態(tài)LACP協(xié)議同樣也需要網(wǎng)絡(luò)管理人員手工加入成員端口，但是它可以通過(guò)主動(dòng)端設(shè)備來(lái)完成鏈路聚合中相關(guān)端口的參數(shù)協(xié)商，可以實(shí)現(xiàn)對(duì)端口的活動(dòng)管理，比如選擇其中的兩條鏈路轉(zhuǎn)發(fā)數(shù)據(jù)，另一條鏈路實(shí)現(xiàn)備份。

圖6中的本地載波頻率設(shè)定間隔固定為1 kHz，且對(duì)本地偽碼取與橫塊混疊時(shí)相同的降采樣因子進(jìn)行時(shí)域混疊，最終輸出為一個(gè)L×B的矩陣，該矩陣的縱坐標(biāo)(0, 1…B-1)對(duì)應(yīng)混疊的偽碼相位筐，橫坐標(biāo)（0, 1 …L-1）對(duì)應(yīng)載波多普勒頻率，第m個(gè)橫塊對(duì)應(yīng)的多普勒頻率值f(m)為：

多普勒頻率的分辨率由ωm決定，而ωm的頻率粒度是1 kHz被L等分，所以L越大多普勒頻率分辨率就越高，L即對(duì)應(yīng)相干積分時(shí)長(zhǎng)TI。

尋找到當(dāng)前衛(wèi)星超過(guò)門限值所對(duì)應(yīng)的多普勒頻移與混疊的偽碼相位峰值信號(hào)后，由于其混疊的偽碼相位筐中有p個(gè)碼片，為p個(gè)可能的真實(shí)碼相位點(diǎn)，對(duì)該p個(gè)碼片分別進(jìn)行時(shí)域相關(guān)運(yùn)算，得到其中時(shí)域相關(guān)值最大的碼片，更新縱坐標(biāo)的值，此時(shí)最大峰值對(duì)應(yīng)的坐標(biāo)值即為捕獲的多普勒頻移及偽碼相位。

將本地偽碼與載波的混合信號(hào)的SFT等各項(xiàng)操作提前完成并加以儲(chǔ)存，使這部分運(yùn)算量不占用捕獲時(shí)間。完成上述存儲(chǔ)后，每個(gè)橫塊數(shù)據(jù)的操作需要兩次FFT運(yùn)算，一次是對(duì)橫塊的FFT運(yùn)算，另一次是對(duì)相乘以后數(shù)據(jù)的IFFT運(yùn)算；每個(gè)豎塊需要一次FFT運(yùn)算。對(duì)于一個(gè)L×N的二維數(shù)據(jù)塊，若搜索的多普勒頻率范圍[-5 kHz, +5 kHz]，總共需要2L×10個(gè)橫塊的B點(diǎn)FFT運(yùn)算，B個(gè)豎塊的L點(diǎn)FFT運(yùn)算，混疊時(shí)BL次加法運(yùn)算，頻域中的BL次乘法運(yùn)算及N次最終重構(gòu)時(shí)的相關(guān)運(yùn)算，按照n點(diǎn)FFT的運(yùn)算量為nlog2n計(jì)算，則本文提出的低運(yùn)算量捕獲算法（BL_FFT）總運(yùn)算量為：

對(duì)LN個(gè)數(shù)據(jù)進(jìn)行普通的FFT捕獲，依然將本地?cái)?shù)據(jù)預(yù)先處理，若想達(dá)到相同的多普勒頻率分辨率，需要的多普勒頻率井個(gè)數(shù)為10L個(gè)，要完成兩次FFT運(yùn)算以及頻域中LN次乘法運(yùn)算，此時(shí)的總運(yùn)算量為：

采用SFT運(yùn)算則需在FFT運(yùn)算的基礎(chǔ)上增加BL次混疊加法運(yùn)算，頻域中的BL次乘法運(yùn)算與N次重構(gòu)相關(guān)運(yùn)算，此時(shí)總的運(yùn)算量為：

如圖7(a)為降采樣因子固定時(shí)運(yùn)算量隨數(shù)據(jù)塊個(gè)數(shù)的變化曲線，圖7(b)為數(shù)據(jù)塊個(gè)數(shù)固定時(shí)運(yùn)算量隨降采樣因子的變化曲線，當(dāng)L>1，p>1時(shí)，本文所提算法運(yùn)算量小于FFT與SFT捕獲算法。

圖7 理論運(yùn)算量Fig.7 Theoretical calculation

3 算法仿真與分析

本文利用UTREK210A衛(wèi)星中頻信號(hào)前端采集系統(tǒng)采集半物理仿真所需的數(shù)據(jù)，以驗(yàn)證本文所提出的低運(yùn)算量快速捕獲方法效率，仿真參數(shù)如表1。

表1 仿真參數(shù)Tab.1 Simulation parameters

在仿真中，主要對(duì)比分析了基于FFT、SFT的快速捕獲算法與本文所提出的BL_FFT快速捕獲算法的性能，當(dāng)取數(shù)據(jù)塊個(gè)數(shù)L為2，頻率搜索步長(zhǎng)為500 Hz，信號(hào)長(zhǎng)度TI為2 ms。數(shù)據(jù)采集時(shí)天頂上有五顆GPS衛(wèi)星，隨機(jī)取50組采集數(shù)據(jù)做捕獲實(shí)驗(yàn)，三種方法的捕獲結(jié)果如圖8。

可以從圖8(a)看出信號(hào)強(qiáng)度較大時(shí)，三種方法均能夠?qū)崿F(xiàn)正確捕獲，但因降采樣影響，同信號(hào)強(qiáng)度條件下，SFT與BL_FFT快速捕獲算法較FFT快速捕獲算法的成功次數(shù)略有下降，但捕獲失敗的實(shí)驗(yàn)組可通過(guò)增加數(shù)據(jù)塊個(gè)數(shù)或降低降采樣因子的大小實(shí)現(xiàn)正確捕獲，如圖8(b)，雖然運(yùn)算量有所增加，但其總運(yùn)算量仍低于初始條件下的FFT或SFT捕獲算法，這一結(jié)論與圖7理論運(yùn)算量的比較結(jié)果相符。

圖8 捕獲結(jié)果統(tǒng)計(jì)圖Fig.8 Acquisition result statistics

下面以實(shí)際捕獲結(jié)果分析捕獲精度及時(shí)間，圖9為G15衛(wèi)星的某組三維搜索結(jié)果，表2為最終捕獲結(jié)果數(shù)據(jù)對(duì)比。

表2 仿真實(shí)驗(yàn)數(shù)據(jù)Tab.2 Simulation experiment data

圖9 三維搜索結(jié)果Fig.9 3D search results

對(duì)基于SFT與BL_FFT的快速捕獲算法，三維搜索的輸出是在降采樣因子約束下的結(jié)果，如圖9(b)(c)，降采樣因子取2，尖峰對(duì)應(yīng)的偽碼相位取值有2個(gè)，相隔8184個(gè)相位點(diǎn)，即0.5 ms。

由圖9與表2可得，SFT與BL_FFT算法初始輸出的偽碼相位點(diǎn)數(shù)為520，由于混疊該點(diǎn)對(duì)應(yīng)的另一偽碼相位點(diǎn)數(shù)為8704，分別計(jì)算兩偽碼相位點(diǎn)的相關(guān)值，8704碼片處的相關(guān)值遠(yuǎn)大于520處的相關(guān)值，得到8704為最終的偽碼相位點(diǎn)，與FFT算法的結(jié)果相同。相比于FFT算法，SFT與BL_FFT算法信噪比降低1.5 dB左右，運(yùn)算時(shí)間卻大大減少，BL_FFT算法的時(shí)間相比于FFT算法降低了4.1倍，相比于SFT算法降低了1.7倍。按照仿真參數(shù)計(jì)算，可得CBL_FFT≈CFFT/ 4.5，CBL_FFT≈CSFT/ 2.1與實(shí)驗(yàn)結(jié)果倍數(shù)均相差0.4，該部分誤差由硬件及額外運(yùn)算造成。

4 結(jié) 論

本文針對(duì)采用長(zhǎng)相干積分時(shí)間捕獲時(shí)導(dǎo)致運(yùn)算量成倍累積、載波頻率誤差容忍度低的問(wèn)題，利用數(shù)據(jù)分塊與降采樣的思想，提出了一種低運(yùn)算量快速捕獲方法，實(shí)現(xiàn)了縮小頻率搜索步長(zhǎng)并增加積分?jǐn)?shù)據(jù)量的需求。理論分析與仿真結(jié)果表明：

1)本文提出的低運(yùn)算量快速捕獲方法可以將多普勒頻移搜索分辨率細(xì)化為1/LkHz，對(duì)信號(hào)進(jìn)行頻率補(bǔ)償后的累加將信噪比增大10lgLdB，將整體運(yùn)算量縮減至20LBlog2B+BLlog2L+2BL+2N。

2)采樣頻率固定的情況下，算法的整體運(yùn)算量由L、p兩個(gè)參數(shù)決定，當(dāng)L=1，p=1或L=1，p>1時(shí)，算法等同于基于FFT或SFT的捕獲算法，當(dāng)L>1，p>1時(shí)，運(yùn)算量有明顯降低。

3)TI=2 ms，L=2，p=2時(shí)，算法較基于FFT的方法信噪比降低約1.5 dB，效率提升約4.1倍；較基于SFT的方法信噪比降低約0.01 dB，效率提升約1.7倍。即使對(duì)于微弱信號(hào)該算法需要增加數(shù)據(jù)塊個(gè)數(shù)或降低降采樣因子的大小實(shí)現(xiàn)正確捕獲，其整體運(yùn)算時(shí)間仍優(yōu)于基于FFT或SFT的捕獲算法。