劉詩涵,王可東

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

?

一種改進的全比特算法

劉詩涵,王可東

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

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

關(guān)鍵詞：全球定位系統(tǒng);捕獲;全比特;塊累加

0引言

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

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

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

1塊累加法分析

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

圖1L塊采樣數(shù)據(jù)

PRN為

k

的衛(wèi)星的采樣數(shù)據(jù)離散化后可以得到輸入信號的復數(shù)表達形式:

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

(1)

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

GPS每個導航數(shù)據(jù)位的長度是20ms,因此，

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

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

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

(2)

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

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

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

lk(n)=ej2πΔfknts,

(3)

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

將本地載波信號與輸入信號相乘得到載波調(diào)整后的信號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的點數(shù)為NL個,對信號進行塊累加后,FFT處理的點數(shù)降至L個,因此對信號進行塊累加后,可以大幅降低后續(xù)捕獲算法的計算量,提高算法的執(zhí)行速度。

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

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

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

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

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

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

算法的具體實現(xiàn)過程如下:

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

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

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

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

5) 將每組數(shù)據(jù)的結(jié)果進行取模運算,然后進行M次非相干累加,得到20個相關(guān)峰值。

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

3捕獲判決方法

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

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

1) 找到相關(guān)值中最大相關(guān)值,次大相關(guān)值。

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

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

4算法增益分析

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

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

Gc=10×lgTcoh,

(7)

式中:Tcoh為相對于1ms的數(shù)據(jù)長度。

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

Gnc=10×lgNnc-L(n),

(8)

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

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

(9)

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

5實驗驗證

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

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

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

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

本文選取5段連續(xù)的20 ms數(shù)據(jù)進行驗證,利用式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長度的數(shù)據(jù)進行處理,理論上能夠捕獲信噪比為-38 dB的信號,下面對本文提出的算法進行驗證。

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

圖4　12號衛(wèi)星捕獲結(jié)果

圖5　12號衛(wèi)星碼相位捕獲細化圖

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

表1　改進前后算法執(zhí)行時間對比

6結(jié)束語

本文提出了一種改進的全比特算法,利用塊累加和FFT技術(shù)將傳統(tǒng)的全比特算法的20錄ms相干積分縮短至1 ms,并采用循環(huán)相關(guān)的方法進行并行捕獲。實驗結(jié)果表明,通過20 ms的相干積分并進行5 次非相干累加,改進后的算法能夠捕獲到信噪比為-38 dB的GPS 信號,靈敏度并未受到影響,而且改進后的算法,其運行時間較傳統(tǒng)的全比特算法縮短了近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]. 中國慣性技術(shù)學報, 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全球定位接收機-原理與軟件實現(xiàn)[M].北京:電子工業(yè)出版社,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]. 中國慣性技術(shù)學報, 2012, 20(1): 46-50.

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

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

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