(北京信息科技大學 信息與通信工程學院，北京 100101)

衛(wèi)星導航中XFAST捕獲的降計算量去模糊處理算法*

趙盼盼，姚彥鑫**

(北京信息科技大學 信息與通信工程學院，北京 100101)

衛(wèi)星導航系統(tǒng)中，采用擴展復制重疊法(Extended Replica Folding Acquisition Search Technique，XFAST)對長PN碼進行直接捕獲時，粗捕后得到的對齊碼相位存在重疊模糊度。為減少去模糊處理的計算量，提高捕獲速度，提出了一種新的去模糊處理算法。新算法在得到粗捕對齊碼相位結果后，先對本地碼序列重新按照對齊相位進行排列、分段、段內循環(huán)移位等操作，然后進行段間疊加，再與接收碼序列通過FFT-IFFT運算實現(xiàn)循環(huán)相關運算，從而確定對齊碼相位所在的子碼段，得到無模糊度的捕獲結果。理論分析與仿真結果證明，該算法可以在分段疊加段數(shù)和子段長滿足一定關系的條件下，在檢測性能滿足系統(tǒng)要求下，大大降低去模糊處理的計算量和操作時間，從而提高捕獲速度。

衛(wèi)星導航系統(tǒng)；長碼直捕；快速捕獲；去模糊；計算量；折疊相關

1 引 言

GPS信號采用C/A碼和P碼兩種不同的偽隨機碼。其中C/A碼稱為粗碼，是一種低碼率、周期重復的短碼；P碼稱為精碼，是一種高碼率、長周期、加密的偽隨機碼[1]。傳統(tǒng)的P碼捕獲一般采用C/A碼引導的方式，但是C/A碼碼率低、容易受敵方干擾和欺騙，在強干擾和欺騙的戰(zhàn)爭環(huán)境中，輔助捕獲很難實現(xiàn)。由于P碼具有比C/A更強的反干擾和反欺騙的特性，因此要求在軍事通信和導航系統(tǒng)中具備對P碼快速直接捕獲的能力。

因為P碼具有6.1871×1012個碼元[2]，完成P碼直接捕獲需要很長的捕獲時間和巨大的計算量。針對此問題，近年來國內外對于P碼的直接捕獲算法進行了大量的研究。按照捕獲策略可分為串行、并行和混合型，按照處理域又可以分為時域和頻域兩種處理方式。由于串行搜索方法[3]是逐個檢測碼相位，導致搜索過程非常長，搜索效率低，不適用于大范圍搜索。分塊并行搜索碼相位的混合型方法成為許多快速捕獲P碼方案的基礎。

典型的P碼直接捕獲算法有補零法 (Zero-Padding Method，ZPM)[4]、擴展復制重疊法 ( Extended Replica Folding Acquisition Search Technique，XFAST)[5]、直接平均法 (Direct Average Method，DAM)[6]、重疊平均法 (Overlap Average Method，OAM)[7]，以及在此基礎上的各種演變算法[8-10]。其中XFAST由Yang等人[5]于1999年提出，其核心是通過將長度為M×N的本地碼序列進行M段疊加，利用分段疊加碼序列與長度為N的接收碼序列進行循環(huán)相關運算，使偽碼相位并行搜索范圍擴大至(M-1)N+1個碼相位。與其他方法相比，XFAST可以顯著提高搜索效率。

文獻[11-12]對XFAST算法性能及應用進行了廣泛的討論，但都是從算法參數(shù)方面進行優(yōu)化。本文以解決XFAST粗捕后碼相位存在重疊模糊度的問題為目標，提出了一種衛(wèi)星導航中XFAST捕獲的降計算量去模糊處理算法。與XFAST去模糊處理算法進行計算量和操作時間的對比分析，當本地碼序列分段疊加段數(shù)和子段長度滿足一定條件時，本文提出的去模糊算法使得計算量和操作時間明顯降低，從而提高了去除模糊度的速度。文中還對新去模糊處理算法的檢測性能進行了理論分析和仿真分析。

2 算法描述

2.1XFAST捕獲算法

接收的基帶信號可用以下公式表示：

sl=sI,l+jsQ,l(l=0,1,2,…) 。

(1)

式中：sI,l=Adl+λcl+λcos(2πfDlΔt+φ)+nI,l為同相分量，sQ,l=AdQ+λcQ+λsin(2πfDlΔt+φ)+nQ,l為正交分量，A為信號幅度，dl+λ∈{+1,-1}為導航電文，cl+λ∈{+1,-1}為調制擴頻碼，fD為多普勒頻偏，Δt為采樣間隔，φ為載波初始相位，l為采樣索引，λ為接收信號的偽碼相位，nI,l、nQ,l分別為同相和正交分量中的加性高斯白噪聲。

接收信號采樣序列s=sI+jsQ長度取N，其中sI=[sI,0,sI,1,…,sI,N-1]T為同相序列，sQ=[sQ,0,sQ,1,…,sQ,N-1]T為正交序列。接收機以標稱偽碼頻率產生本地偽隨機碼，經采樣后碼序列為[cδ,c1+δ,c2+δ,…,cl+δ]T(l=0,1,2,…)，δ為本地偽碼相位。

XFAST算法是建立在被捕獲偽碼的優(yōu)良自相關特性的基礎之上，碼的自相關性能越好，則處理效率越高；碼周期越長，因分段疊加引起的干擾越小。XFAST算法的原理是，根據(jù)接收信號采樣序列s=sI+jsQ的長度N，在本地偽碼序列擴展M段的情況下，接收機產生長度為M×N的本地偽碼序列[cδ,c1+δ,c2+δ,…,cMN-1+δ]T，將其分成M段長度為N的子碼序列

rm=[cmN+δ,cmN+1+δ,…,cmN+N-1+δ]T,

由于XFAST粗捕得到的碼相位具有模糊度，即重疊模糊度，為了得到精確的偽碼相位值，需要進行去除重疊模糊度處理，也可稱為精捕。根據(jù)粗捕得到的對齊碼相位，對本地碼序列進行重新排列，方法為：根據(jù)粗捕得到的對齊碼位置對本地碼序列進行循環(huán)左移，移位位數(shù)為粗捕得到的對齊碼位置值減1(例如：粗捕得到的對齊碼位置值為3，則移位位數(shù)為2)，從而以粗捕得到的對齊碼中第一個原始碼片為本地碼序列的起點，即c1成為本地碼序列的起點。將重新排列的本地碼序列分成M段長為N的子碼段序列，各個新子碼序列分別與接收碼序列在時域中進行線性相關運算，在得到的M個相關值中，最大值對應的子碼段即為粗捕得到的碼相位所在的子碼段，如圖1所示。

圖1 XFAST去模糊算法(精捕)Fig.1 The algorithm of XFAST ambiguity resolution(fine capture)

圖1中最大相關值為接收碼序列與第3段本地子碼序列的相關值，即粗捕得到的碼相位處于第3個子碼段中。根據(jù)粗捕得到對齊碼片位置3和去模糊處理得到的碼相位所處的子碼段3，可以計算得出接收碼序列與本地碼序列在第11(計算過程為3+(3-1)×4=11)個碼片c3處對齊。

2.2新去模糊處理算法

本文提出的去模糊算法同樣是利用P碼具有優(yōu)良的自相關性的特點，從而獲得較高的處理效率。其步驟是對本地碼序列重新排列、分段、段內循環(huán)移位后疊加，然后再與接收碼序列通過FFT-IFFT運算實現(xiàn)循環(huán)相關運算，根據(jù)相關結果最大值確定粗捕得到的對齊碼所在的具體子碼段，如圖2所示。

圖2 新去模糊處理算法Fig.2 The new algorithm of ambiguity resolution

Step2 各個子碼段序列分別循環(huán)右移，移位位數(shù)為相應的子碼段號減1。例如：第1段循環(huán)右移0位，第2段循環(huán)右移1位，以此類推，第M段循環(huán)右移M-1位。

Step3 將移位后的各子碼段序列對應相加，得到一個新的長為N的分段疊加碼序列，對新的分段疊加碼序列進行N點FFT運算。

Step4 將Step 3中的計算結果與接收碼序列的FFT計算結果進行復共軛相乘。

Step5 將得到的結果進行N點IFFT運算，在得到的N個相關值中，最大值對應的本地碼片位置序號即為粗捕得到的對齊碼相位所在的本地子碼段序號。

根據(jù)粗捕得到對齊碼片位置和去模糊處理得到的碼相位所處的子碼段，可以計算得出接收碼序列與本地碼序列對應相同的唯一碼相位。

3 性能分析

3.1捕獲概率和虛警概率

3.1.1XFAST新去模糊算法捕獲概率分析

新去模糊算法與XFAST粗捕算法的唯一不同之處在于，新去模糊算法對重新分段的本地子碼段序列進行了循環(huán)移位。根據(jù)P碼優(yōu)良的自相關特性，碼對齊出現(xiàn)的相關峰值位置跟隨對齊碼循環(huán)移位而相應地移位，而對于峰值大小沒有影響，同樣對于碼未完全對齊產生的互相關噪聲也沒有影響。因此，移位前、后的子碼段序列與接收碼序列進行循環(huán)相關的兩種結果，對峰值的檢測性能是相同的。此處用非移位子碼段的疊加碼序列與接收碼序列的循環(huán)相關結果進行檢測性能分析。

接收碼序列與本地分段疊加碼序列進行相關運算，相關結果包括同相相關和正交相關兩部分，對同相相關結果CI進行詳細分析，正交相關結果CQ與之類似。同相相關結果表達式如下：

(2)

同相相關結果CI由3項構成：相干積分、自噪聲和加性高斯白噪聲。假設接收信號的同相采樣序列sI與本地碼序列有n(n=0,1,…,N)個碼元對應相同，接收信號同相采樣序列的sI,g～sI,g+n-1與本地碼序列的ch+δ～ch+δ+n-1對應相同，g、h分別為接收碼序列和本地碼序列對應相同碼段的首個碼相位的索引，則相干積分項為

(3)

其中：φ1=2πfDΔtg+φ。在相干積分過程中，認為導航電文為常數(shù)dλ。n=0說明不存在相干積分項，n=N說明本地信號包含所有的接收信號。ΩI的均值為

(4)

其中：p=[(g+λ)-(h+δ)]-?(g+λ)-(h+δ)」為殘余碼相位偏移(?y」表示不大于y的最大整數(shù))。假設H0表示被檢測信號不存在，即接收信號只含有噪聲，則R0(p)=0；H1表示被檢測信號存在，即接收信號中同時含有信號和噪聲，則R1(p)=1-|p|。由于ΩI的方差不大于A2nGi(p)，近似認為ΩI的方差為A2nGi(p)，其中G1(p)=p2，G0(p)=(1-|p|)2。根據(jù)中心極限定理，相干積分項近似服從高斯分布，即ΩI～ψ(EΩI,nA2Gi(p))。

CI～ψ(EΩI,MN(σ2+A2)+nGi(p)A2-nA2),i=0,1。

(5)

CQ～ψ(EΩQ,MN(σ2+A2)+nGi(p)A2-nA2),i=0,1。

(6)

(7)

當接收信號中沒有被檢測信號時，令μi=0，得到fξ(x|0,p,H0)服從瑞利(Rayleigh)分布。概率密度函數(shù)

(8)

從而，虛警概率為

(9)

(10)

(11)

3.1.2XFAST的兩種去模糊算法捕獲概率對比

XFAST去模糊度算法將重新排列的各個新子碼序列分別與接收碼序列在時域中進行線性相關運算，同向相關結果表達式為

(12)

(13)

3.2計算量分析

3.2.1XFAST去模糊算法計算量

根據(jù)XFAST去模糊算法，將重新分段的各個本地子碼段序列與接收碼序列在時域中分別進行線性相關，共進行M次。每次相關運算乘法計算量為N，加法計算量為N-1，則總的乘法計算量為M×N，總的加法計算量為M×(N-1)。

3.2.2新去模糊算法計算量

3.2.3計算量對比分析

相對來說，乘法計算量比加法計算量大很多，因此只考慮乘法的計算量。XFAST去模糊算法的乘法計算量為M×N，新去模糊算法的乘法計算量為NlbN+N。對兩種去模糊算法的乘法計算量進行比較，當滿足

NlbN+N

(14)

即N<2M-1時，本文提出的新去模糊算法比XFAST去模糊算法計算量小，相應地加快了去模糊處理的速度。當滿足上述條件時，新去模糊算法相對于XFAST去模糊算法的計算量降低百分比為

(15)

其中：M為本地碼序列分段疊加的段數(shù)，N為接收碼序列長度。

3.3捕獲時間分析

T1=(3lbN+2)t1。

(16)

XFAST去模糊算法的乘法計算量為M×N，則完成一次XFAST去模糊處理算法需要的時間為

T2=2Mt1。

(17)

新去模糊算法的乘法計算量為NlbN+N，則完成一次新去模糊處理算法需要的時間為

T3=2(lbN+1)t1。

(18)

若用XFAST去模糊算法，則一次完整的P碼捕獲消耗的時間為

T4=T1+T2=(3lbN+2+2M)t1。

(19)

若采用新去模糊算法，則一次完整P碼捕獲消耗的時間為

T5=T1+T3=(5lbN+4)t1。

(20)

根據(jù)公式(19)可知，當接收碼序列長度N一定時，新算法的捕獲時間不隨本地碼序列疊加段數(shù)M變化；當本地碼序列長度M×N一定時，本地碼疊加段數(shù)M減小，隨之選取的接收碼序列長度N增大，則捕獲時間隨之變長，反之，捕獲時間變短。

對兩種去模糊算法的耗時進行對比分析，當滿足T2>T3即N<2M-1時，本文提出的新去模糊算法比XFAST去模糊算法耗時短，相應地加快了去模糊處理的速度。當滿足N<2M-1時，新去模糊算法相對于XFAST去模糊算法的消耗時間降低百分比為

(21)

4 仿真分析

4.1功能仿真

在Windows平臺下，通過Matlab對本文提出的新去模糊算法進行功能仿真。此部分是說明新算法可以完成去模糊處理，暫時不考慮子碼段序列長度和段數(shù)對性能方面的影響，選取了一組較短數(shù)據(jù)進行仿真說明。假設接收碼長N為1 024；本地碼總長16 384，分段疊加段數(shù)M為16，每段長度N為1 024；接收碼序列與本地碼序列中的第2 109～3 132的碼片對應相同。圖3中(a)為粗捕仿真圖，(b)為新去模糊算法仿真圖。

(a)XFAST粗捕

(b)新去模糊算法圖3 XFAST粗捕和新去模糊算法Fig.3 XFAST coarse acquisition & new algorithm of ambiguity resolution

觀察以上仿真波形圖，由XFAST粗捕得到的對齊碼相位在本地分段疊加碼序列的第61個碼片處，去模糊處理得到對齊碼相位在本地碼的第3個子碼段，從而可以計算得知接收碼序列與本地碼序列對齊的具體碼相位在本地碼序列的第2 109(即61+1 024×(3-1))個碼片處，與仿真條件中的假設相同。仿真結果表明，本文提出的新的去模糊算法可以準確地確定對齊碼相位所在的本地碼子段。

4.2檢測性能仿真

為了方便理論分析，假設殘余碼相位偏移p=0，多普勒頻偏fD=0，接收碼序列長度N分別取32 768和65 536，本地碼序列分段疊加段數(shù)M分別取18和21。在給定虛警概率Pfa=10-5和Pfa=10-7情況下，單次捕獲檢測概率隨接收信號載噪比C/N0的變化如圖4所示。

對于XFAST去模糊算法，檢測概率與本地碼序列分段疊加段數(shù)無關，隨著接收碼序列長度增加，捕獲概率提高；當接收碼序列長度以及接收信號載噪比一定時，隨著虛警概率變大，則捕獲概率變高。

(a)虛警概率Pfa=10-5

(b)虛警概率Pfa=10-7圖4 單次檢測概率隨C/N0變化Fig.4 The probability of single detection vs. C/N0

對于新去模糊處理算法，當本地碼序列分段疊加段數(shù)和接收信號載噪比一定時，隨著接收碼序列長度增加，捕獲概率提高；當接收碼序列長度和接收信號載載噪比一定時，隨著本地碼分段疊加段數(shù)增加，捕獲概率降低。當本地碼序列分段疊加段數(shù)、接收碼序列長度以及接收信號載噪比一定時，隨著虛警概率變大，則捕獲概率會變高，當然虛警概率不能設定過大，否則會使得捕獲性能變差。

兩種去模糊算法檢測概率對比分析可知，新去模糊處理算法的檢測性概率有所降低。

4.3計算量仿真

FFT運算的數(shù)據(jù)個數(shù)必須為2的整數(shù)次冪，從而如果將FFT運用到P碼捕獲過程中，數(shù)據(jù)長度最長可取65 536(即216)約6.4 ms的數(shù)據(jù)記錄。根據(jù)以上分析，截取不同長度的P碼數(shù)據(jù)進行計算量對比分析，參數(shù)均滿足條件N<2M-1，結果如表1所示。

表1 不同長度P碼數(shù)據(jù)使用不同分段數(shù)處理的結果Tab.1 The results of different lengths P-code data processed using a different number of segments

由表1中的數(shù)據(jù)分析得知，在捕獲P碼過程中，選取合適的參數(shù)滿足N<2M-1時，新去模糊算法的計算量得到明顯降低。

4.4捕獲時間仿真

截取不同長度的P碼數(shù)據(jù)進行操作時間對比分析，參數(shù)均滿足條件N<2M-1，根據(jù)公式(21)，分析結果如表2所示。

表2 不同長度P碼數(shù)據(jù)使用不同分段數(shù)捕獲時間降低分析Tab.2 The capture time reduction analysis with different lengths P-code data using a different number of segments

由表2中的數(shù)據(jù)分析得知，在捕獲P碼過程中，選取合適的參數(shù)滿足N<2M-1時，新去模糊算法的捕獲時間得到明顯降低。

5 結束語

采用擴展復制重疊法(XFAST)對長碼捕獲后，得到的對齊碼相位存在重疊模糊度，XFAST去模糊處理需要逐段進行線性相關運算，多次線性相關的計算量與子碼段長度和段數(shù)都成正比，計算量是偏大的。為了提高去模糊處理的計算效率，本文提出了一種衛(wèi)星導航中XFAST捕獲的降計算量去模糊處理算法，通過對本地碼序列進行重新排列、分段、段內循環(huán)移位后疊加，再與接收碼通過FFT-IFFT運算實現(xiàn)循環(huán)相關，確定對齊碼相位所在的具體子碼段，實現(xiàn)去模糊處理。

文中從理論上分析、比較了新舊去模糊處理算法的計算量，并推導出當接收碼序列長度N與本地碼序列擴展分段疊加段數(shù)M滿足公式(14)中的條件時，采用本文提出的算法進行去模糊處理計算量明顯降低，并通過仿真數(shù)據(jù)進行了分析驗證。類似地，對比分析新舊去模糊處理算法的操作時間，在滿足降低計算量的條件下，新算法捕獲時間大大降低。對XFAST新去模糊處理算法的檢測性能進行了理論與仿真分析，得出新算法的檢測概率有所降低，但是檢測性能可以滿足系統(tǒng)要求。下一步研究的工作是在此基礎上找到提高算法檢測概率的方法策略。

[1] ELLIOTT D K,CHRISTOPHER J H. Understanding GPS:principles and applications[M]. 2nd Ed. Boston:Artech House Inc.,2006.

[2] TSUI J B. Fundamentals of global positioning system receivers a software approach[M]. 2nd Ed. New Jersey:Wiley Interscience,2005.

[3] POLYDOROS A,WEBER C L. A unified approach to serial search spread-spectrum code acquisition-part I & II[J]. IEEE Transactions on Communication. 1984,32(5):542-560.

[4] LI H,LU M Q,FENG Z M. Improved zero-padding method for rapid long PN-code acquisition[J]. IEEE Transactions on Signal Processing,2008,56(8):3795-3799.

[5] YANG C,VASQUEZ J,CHAFFEE J. Fast direct P(Y)-code acquisition using XFAST[C]//Proceedings of ION GPS 1999. Nashville:ION,1999:317-324.

[6] PANG J. Direct global positioning system P-code acquisition field programmable gate array prototyping[D]. OH,USA:Ohio University,2003.

[7] CUI H,LIAN B W. Study of GPS P-code direct acquisition technique[C]// Proceedings of IEEE International Conference on Broadband Network and Multimedia Technology.Beijing:IEEE,2010:1111-1114.

[8] LI H,CUI X W,LU M Q et al. Dual-folding based rapid search method for long PN-code acquisition[J]. IEEE Transactions on Antennas and Propagation,2008,12(7):5286-5296.

[9] XU Y,XU L J,YUAN H,et al. Direct P-code acquisition algorithm based on bidirectional overlap technique[J]. Journal of Systems Engineering and Electronics,2014,25(4):538-546.

[10] FENG W Q,XING X D,ZHAO Q,et al. Dual-channel method for fast long PN-code acquisition[J]. Communications China,2014,11(5):60-70.

[11] 唐小妹,龐晶,黃仰博,等.XFAST長碼直捕算法參數(shù)優(yōu)化設計[J]. 中南大學學報(自然科學版),2014,45(4):1113-1118.

TANG Xiaomei,PANG Jing,HUANG Yangbo,et al. Optimization of XFAST design[J]. Journal of Central South University (Science and Technology),2014,45(4):1113-1118. (in Chinese)

[12] 唐小妹,雍少為,王飛雪. 存在偽碼多普勒條件下的XFAST性能分析[J].通信學報,2010,31(8):54-59.

TANG Xiaomei,YONG Shaowei,WANG Feixue. Performance of XFAST in the presence of code Doppler[J]. Journal on Communications,2010,31(8):54-59. (in Chinese)

[13] 黃勁松,劉峻寧,劉成寶,等.GPS信號載噪比研究[J].武漢大學學報(信息科學版),2007,32(5):427-430.

HUANG Jinsong,LIU Junning,LIU Chengbao,et al. On C/N0 of received GPS signal.[J]. Geomatics and Information Science of Wuhan University,2007,32(5):427-430. (in Chinese)

AnAmbiguityResolvingAlgorithmforXFASTAcquisitionwithLessComputationalAmountinSatelliteNavigation

ZHAO Panpan,YAO Yanxin
(School of Information and Communication Engineering,Beijing Information Science and Technology University,Beijing 100101,China)

In satellite navigation system,extended replica folding acquisition search technique (XFAST) is used to capture long PN-code directly,but the aligned code phase obtained after coarse acquisition has overlapped ambiguity. In order to reduce the computational amount of resolving ambiguity and to speed up acquisition process,a new method is proposed. Firstly,local code chips are arranged according to the coarsely captured aligned code phase,segmented and shifted circularly within separate segments,and then all new local code sub-segments are folded together. Further,the

code and the new local folded code are performing circular correlation operations through FFT-IFFT,and the precise code sub-segment of the aligned code phase can be determined. Thus the ambiguity of coarse acquisition can be solved. Theoretical analysis and simulation results demonstrate that,under the condition that the number of sub-segments and the length of the sub-segment satisfy certain relations,the proposed algorithm can reduce the computational amount of resolving ambiguity and operating time to speed up acquisition process greatly with the detection performance meeting the system requirements.

satellite navigation system;direct acquisition of long code；rapid acquisition；ambiguity resolution；computational amount；folded correlation

10.3969/j.issn.1001-893x.2017.10.017

趙盼盼，姚彥鑫.衛(wèi)星導航中XFAST捕獲的降計算量去模糊處理算法[J].電訊技術，2017,57(10):1205-1212.[ZHAO Panpan,YAO Yanxin.An ambiguity resolving algorithm for XFAST acquisition with less computational amount in satellite navigation[J].Telecommunication Engineering,2017,57(10):1205-1212.]

2017-03-13；

2017-07-14 Received date:2017-03-13；Revised date：2017-07-14

國家自然科學基金資助項目(61302073)；北京市自然科學基金資助項目(4172012，Z160002)；北京市教委面上項目(KM201711232010)

**通信作者：yanxin_buaa@126.com Corresponding author：yanxin_buaa@126.com

TN967.1

A

1001-893X(2017)10-1205-08

趙盼盼(1990—)，男，河北滄州人，碩士研究生，主要研究方向為GNSS關鍵技術；

Email：zhaopanp321@163.com

姚彥鑫(1982—)，女，河北人，2009年于北京航空航天大學獲博士學位，現(xiàn)為副教授，主要研究方向為無線通信與節(jié)能通信網(wǎng)絡、壓縮感知與智能信號處理。

Email:yanxin_buaa@126.com