一種改進的全比特算法

劉詩涵,王可東

(北京航空航天大學宇航學院,北京 100191)

?

一種改進的全比特算法

劉詩涵,王可東

(北京航空航天大學宇航學院,北京 100191)

摘要：提出一種改進的全比特算法。新算法將去載波后的信號進行塊累加,將20 ms的相干積分縮短至1 ms,并采用FFT并行捕獲,在不影響捕獲靈敏度的前提下,大大降低了算法的運算量。利用歸一化后最大相關值和次大相關值之差對捕獲結果進行判決,提高了判決方法的適用性。最后,利用Matlab仿真的信號對算法進行驗證,結果表明：利用20 ms的相干積分和5次非相干累加,能夠捕獲信噪比為-38 dB的微弱信號,執行時間縮短了近2/3.

關鍵詞：全球定位系統;捕獲;全比特;塊累加

0引言

隨著信息技術的飛速發展,人們對導航接收機的精度要求越來越高。現有的導航設備在正常環境下的定位精度已經基本滿足要求,然而,室內、密集地區等復雜環境下的導航設備定位難以滿足要求,究其原因,在于如此環境下GPS信號功率會大幅衰減,接收信號的載噪比嚴重惡化[1-2]。無輔助的GPS弱信號捕獲需要更長的相干積分時間和更多的非相干積分次數來提高信號的載噪比,然而,導航數據比特只有20 ms,這將大大限制相干積分的長度。

傳統的串行搜索算法首先對可見衛星進行搜索,然后在每顆可見衛星上的每一個可能的碼相位和多普勒頻移單元進行搜索,硬件上簡單易實現,但捕獲時間較長[3-4]。循環相關算法利用快速傅里葉變換(FFT)來加快信號處理速度,在弱信號捕獲中主要靠延長累積時間來提高檢測增益,但受導航比特跳轉的限制[5-8]。半比特法和全比特法[9-10],有效的規避了數據比特跳變的影響,突破了相干積分時間20 ms的限制,但捕獲速度較慢。文獻[11]提出一種塊累加方法,指出將多個1 ms數據在同一個采樣點進行采樣,采樣得到的C/A碼值不會改變,1 ms的采樣數據就能覆蓋整個碼相位周期。文獻[12]對塊累加方法帶來的信噪比提升進行了詳細的分析,指出其在實際應用中仍會受到導航電文比特跳變的限制。

本文提出一種改進的全比特弱信號捕獲算法。該算法通過塊累加的方式,將全比特算法的20 ms相干積分縮短至1 ms,并采用FFT并行捕獲,大大減少了運算量。仿真實驗和分析表明,本文提出的算法有效可行,適用于GPS軟件接收機,并且具有較高的運算效率。

1塊累加法分析

對L ms的數據進行采樣,將其分成L個數據塊,每個數據塊長度1 ms.假設1 ms的采樣點數為N,則一共有NL個采樣點,這里L≥1,且為整數。如圖1所示。

圖1L塊采樣數據

PRN為

k

的衛星的采樣數據離散化后可以得到輸入信號的復數表達形式:

sk(n)=Dk(nts)Ck(nts)ej2πfknts+vk(nts),

(1)

式中: ts=1/fs為采樣周期; N ts=1ms; n∈[0,LN-1],Dk為導航數據位; Ck為C/A碼; fk為帶多普勒頻移的載波頻率; vk為高斯白噪聲。

GPS每個導航數據位的長度是20ms,因此，

聯系人： 劉詩涵E-mail:shihan_liu0815@126.com選取L≤20,并且認為在這L個數據塊之內Dk(t)不變。

利用Ck(t)周期1ms的性質,可以得到

Ck(nts)=Ck[(n+N)ts],

(2)

式中: n=0,1,…,(L-1)N-1.

因此,對C/A碼采樣,不同數據塊的相同位置采樣數值一樣。

本地載波NCO產生頻率為Δfk的信號,記為lk(n)

lk(n)=ej2πΔfknts,

(3)

式中: n=0,1,…,(L-1)N-1.

將本地載波信號與輸入信號相乘得到載波調整后的信號yk(n)

yk(n)=lk(n)·sk(n)

=Dk(nts)Ck(nts)

ej2π(fk+Δfk)nts+vk(nts)ej2πΔfknts.

(4)

對yk(n)進行塊累加,得到

=S{yk(n)}G(L,

(5)

(6)

對長度為Lms的信號進行FFT并行捕獲時,如果不對信號進行塊累加,FFT的點數為NL個,對信號進行塊累加后,FFT處理的點數降至L個,因此對信號進行塊累加后,可以大幅降低后續捕獲算法的計算量,提高算法的執行速度。

2改進的全比特弱信號捕獲算法

為了克服導航數據比特20 ms的限制,Psiaki提出了全比特算法。全比特算法能夠規避比特跳變的影響,將相干積分時間擴展至20 ms,有效提高信號載噪比,但是其需要對所有可能的跳變進行估計,亦即需要進行20組20 ms的相干積分,運算量很大。

按照前文的分析,本文利用塊累加法對全比特算法進行改進。首先對輸入的中頻信號分成20組,然后將每組去載波后的20 ms數據進行塊累加,成為1 ms的數據,接著采用基于FFT的循環相關方法,將碼相位搜索并行化,最后將這20組數據分別進行非相干累加,查找最大相關峰值,進行捕獲判決并輸出結果。

本文提出的改進的全比特算法,將運算量很大的20 ms相干積分降低至1 ms相干積分,能夠大幅降低算法的計算量,加快算法的捕獲速度。算法的信號分組及算法框圖如圖2和圖3所示。

圖2　全比特算法信號分組圖

圖3　改進的全比特算法框圖

算法的具體實現過程如下:

1) 將輸入信號按照圖1進行分組,得到由M個20 ms數據塊組成的20組數據。

2) 將分組后的信號分別與載波NCO輸出的特定載波頻偏的信號相乘,去除信號的載波分量。

3) 將載波分離后的20組數據中的每個20 ms的數據塊分別進行累加運算,得到20×M個長度為1 ms的數據。

4) 分別對每組1 ms的數據進行FFT,并將FFT結果分別與本地C/A碼的共軛FFT相乘,對相乘結果進行快速傅里葉反變換。

5) 將每組數據的結果進行取模運算,然后進行M次非相干累加,得到20個相關峰值。

6) 保留20個峰值中最大的一個,并進行捕獲判決,輸出結果。

3捕獲判決方法

常用的捕獲判決方法基于恒虛警概率準則,利用噪聲的統計特性,在某一檢測概率下設定捕獲閾值,如果捕獲的相關峰值超過閾值,則判定捕獲成功,否則認為捕獲失敗[15]。這種判決方法對于不同的環境并不通用,因為捕獲前無法預知信號的載噪比。

文獻[14]利用統計學相關理論推導了一種利用最大相關值與次大相關值之差確定捕獲閾值的判決方法,本文參考這種判決方法,具體為

1) 找到相關值中最大相關值,次大相關值。

2) 將相關值歸一化,即將所有相關值除以最大相關值,這樣最大相關值歸一化后的值為1,次大相關值歸一化后的值為小于1的正數。

3) 如果歸一化后,最大相關值-次大相關值>0.15,則認為捕獲成功,否則認為捕獲失敗。

4算法增益分析

改進的全比特算法利用相干積分和非相干積分來提高信號的處理增益,增益的具體計算方法如下:

相干積分所獲得的增益Gc為[15]

Gc=10×lgTcoh,

(7)

式中:Tcoh為相對于1ms的數據長度。

非相干積分所獲得的增益Gnc為[15]

Gnc=10×lgNnc-L(n),

(8)

式中: Nnc為非相干積分的數目; L(n)為非相干積分損耗。

非相干積分的損耗為[15]

(9)

式中: n為非相干積分數目,Dc(1)為在特定虛警概率和檢測概率下的理想檢測因子。這里取虛警概率為10e-7,檢測概率為0.9,此時Dc(1)≈21[13]。

5實驗驗證

仿真試驗要達到以下兩個目的:

1) 驗證本文提出的改進的全比特算法不會造成捕獲靈敏度的降低。

2) 驗證本文提出的算法較傳統的全比特算法復雜度得到了降低,運行效率得到了提升。

本文的仿真數據用Matlab生成,中頻頻率為4.123 968 MHz,采樣頻率為16.367 667 MHz.

本文選取5段連續的20 ms數據進行驗證,利用式7、8、9可以計算本文提出的改進的全比特算法所能獲得的捕獲增益為

G=Gc+Gnc=10×lgTcoh+10×lgNnc-

=19 dB,

式中:Tcoh=20;Nnc=n=5,Dc(1)≈21.

GPS信號的標稱信噪比為-19 dB,按照上述增益計算,基于本文提出的算法對100 ms長度的數據進行處理,理論上能夠捕獲信噪比為-38 dB的信號,下面對本文提出的算法進行驗證。

仿真生成12號衛星的信噪比為-38 dB的信號,圖4示出了基于本文提出的算法的捕獲結果。圖4顯示有明顯的相關峰存在,圖5顯示歸一化的最大值與次大值之差為0.43,超過捕獲閾值0.15,因此捕獲成功,本文提出的算法有效可行。

圖4　12號衛星捕獲結果

圖5　12號衛星碼相位捕獲細化圖

對未改進的全比特算法和改進后的全比特算法分別進行上機測試,對比二者的運行時間,所用PC機的配置為Inter Core i5-3470@3.20 GHz處理器,內存4 GB,改進前后的處理時間對比如表1所示。由表1可見,改進后的全比特算法,在不影響捕獲靈敏度的前提下,運行時間縮短近2/3,運算復雜度大大降低。

表1　改進前后算法執行時間對比

6結束語

本文提出了一種改進的全比特算法,利用塊累加和FFT技術將傳統的全比特算法的20錄ms相干積分縮短至1 ms,并采用循環相關的方法進行并行捕獲。實驗結果表明,通過20 ms的相干積分并進行5 次非相干累加,改進后的算法能夠捕獲到信噪比為-38 dB的GPS 信號,靈敏度并未受到影響,而且改進后的算法,其運行時間較傳統的全比特算法縮短了近2/3。因此,本文提出的改進算法能夠大大減少計算量,為弱信號捕獲算法用于工程實際提供參考。

參考文獻

[1] RODRIGUEZ J A A, EISSFELLER B. Theory on acquisition algorithms for indoor positioning[C]//12th Saint Petersburg International Conference on integrated navigation systems. 2005.

[2] ZHU C, FAN X. GNSS Signal acquisition in weak signal condition[C]//Communication Systems, Networks & Digital Signal Processing (CSNDSP), 2014 9th International Symposium on. IEEE, 2014: 1128-1132.

[3] PARKINSON B W. Progress in astronautics and aeronautics: global positioning system: Theory and Applications[M]. AIAA, 1996.

[4] MISRA P, ENGE P. Global positioning system: signals, measurements and performance Second edition[M]. Lincoln, MA: Ganga-Jamuna Press, 2006.

[5] 徐曉蘇, 范金洋. GPS 軟件接收機捕獲算法[J]. 中國慣性技術學報, 2009, 17(2): 165-169.

[6] TSUI J B Y. Fundamentals of global positioning system receivers[M]. Wiley-Interscience, 2000.

[7] VAN NEE D J R, Coenen A. new fast GPS code-acquisition technique using FFT[J]. Electronics Letters, 1991, 27(2): 158-160.

[8] STARZYK J A, ZHU Z. Averaging correlation for C/A code acquisition and tracking in frequency domain[C]//Proc. IEEE Midwest Sym. on Circuits and Systems (MWSCAS), 2001(2): 905-908.

[9] PSIAKI M L. Block acquisition of weak GPS signals in a software receiver[C]//ION GPS. Salt Lake City, 2001：2838-2840.

[10]LIN D M, TSUI J B Y. Comparison of acquisition methods for software GPS receiver[C]//Proceedings of the 13th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GPS 2000), 2000: 2385-2390.

[11]HECKLER G W, GARRISON J L. Experimental tests of unaided weak signal acquisition methods using a software receiver[C]//Proceedings of the 19th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS 2006). 2001: 1309-1320.

[12]魯郁.GPS全球定位接收機-原理與軟件實現[M].北京:電子工業出版社,2009.

[13]LACHAPELLE G. Software receiver strategies for the acquisition and re-acquisition of weak GPS signals[C]//ION NTM, 2008.

[14]MAO W L, CHEN A B. New code delay compensation algorithm for weak GPS signal acquisition [J]. AEU-International Journal of Electronics and Communications, 2009, 63(8): 665-677.

[15]李寅寅, 徐曉蘇, 劉錫祥. 基于半比特交替和 FFT 組合的 GPS 軟件接收機弱信號捕獲算法[J]. 中國慣性技術學報, 2012, 20(1): 46-50.

劉詩涵(1989-),男,河南商丘人,碩士生,主要從事衛星導航和組合導航相關研究。

王可東(1975-),男,安徽廬江人,博士,副教授,主要從事飛行器導航、制導與控制、慣性導航儀器、匹配算法、衛星導航等方向的研究。

An Improved Full-Bit Algorithm

LIU Shihan,WANG Kedong

(SchoolofAstronautics,BeihangUniversity,Beijing100191,China)

Abstract:An improved full-bit algorithm is proposed. The new algorithm uses block addition upon the carrier-removed signal and shortens the 20ms coherent integration to 1ms.After that, the signal is captured in a parallel way-FFT. The improved algorithm reduces the computing amount greatly with acquisition sensitivity unreduced. Acquisition results are judged by the difference between the normalized maximum value and second maximum value of autocorrelation. This method improves the applicability of acquisition judgment. At last, the improved algorithm is verified with simulated GPS signal in Matlab. Simulation results indicate that weak GPS signals with SNR of-38 dB can be captured through 20 ms coherent integration and 5 times of non-coherent integration, and the executing time is reduced by about 2/3 compared with the former algorithm.

Key words:GPS; acquisition; full-bit; block addition

作者簡介

收稿日期：2015-06-10

中圖分類號：V19;TP391

文獻標志碼：A

文章編號：1008-9268(2015)06-0011-05

doi:10.13442/j.gnss.1008-9268.2015.06.003