一種改進的基于FFT的GPS弱信號捕獲算法

田拓,張風國,陳奇東,甄衛民

(中國電波傳播研究所,青島 266107)

一種改進的基于FFT的GPS弱信號捕獲算法

田拓,張風國,陳奇東,甄衛民

(中國電波傳播研究所,青島 266107)

傳統的GPS弱信號捕獲通過延長相干積分時間來提高信噪比,但受到導航電文比特位翻轉的影響,相干積分時間一般不超過20 ms,且存在捕獲算法運行效率不高等問題。針對在弱信號環境下有效克服比特位翻轉并增加運算效率的問題,給出了兩種翻轉位預測算法。基于預測結果本文提出了一種改進的捕獲方案,即舍棄存在位翻轉的5 ms數據從而消除其影響,并對其余數據進行15 ms的“先累加后相關”分塊相干積分。最后,利用Matlab仿真的信號對改進捕獲算法進行驗證并與傳統捕獲算法進行對比。結果表明,改進的捕獲算法能有效地捕獲到信噪比低至-40 dB的微弱信號,將相干積分時間延長至15 ms,相較于傳統捕獲算法捕獲靈敏度更高,執行時間更短。

微弱GPS信號;比特位翻轉預測;分塊相干積分;FFT

0 引 言

GPS定位技術在各行各業中得到了越來越廣泛的應用,信號處理始終是定位導航技術的首要問題[1]。GPS接收機處理的衛星信號主要包括載波、偽碼和數據碼三個信號層次,其中捕獲是GPS接收機進行衛星信號處理的關鍵步驟,也是GPS接收機進行導航和定位的關鍵步驟。捕獲是指接收機接收到衛星信號后,將載波解調后的中頻信號與接收機內部產生的C/A碼進行相關運算,利用C/A碼的正交性解調中頻信號,使信號頻寬變回到只含數據碼的基帶。然而,室內、密集地區、叢林遮擋等復雜環境下GPS信號功率大幅衰減,遠低于-130 dB[2]。接收信號的載噪比也將降至-20 dB以下,普通接收機很難實現捕獲,因此研究弱信號環境下的捕獲算法具有重要的意義。

目前對于微弱GPS信號捕獲的通用方法是利用連續積分的增加來提高捕獲微弱信號的能力。具體的方法有相干累積(CC)、非相干累積(NCC)和差分相干累積(DCC)。但是導航電文數據位的跳變限制了積分時間,由于導航電文的傳播速率是50 bit/s,經過20 ms后可能引起GPS信號產生相位翻轉,因此一般的捕獲方法連續積分時間不能超過20 ms.

本文討論、對比了基于FFT的微弱信號捕獲算法,并針對相干累積(CC)、非相干累積(NCC)和差分相干累積(DCC)算法的優缺點提出了兩種行之有效的預測導航電文翻轉位的算法。這兩種算法均基于分塊相干積分算法,采用“先累積后相關”的方式進行相關積分,利用比較前后相關值來預測導航電文數據位跳變位置,使得連續相干積分時間進一步增加。仿真實驗和分析表明,本文提出的改進捕獲方案弱信號環境下性能突出,能捕獲到信噪比低至-40 dB的信號,具有較高的運算效率。

1 傳統弱信號捕獲算法分析

基于FFT的捕獲算法是將接收到的中頻信號和本地載波相乘,通過低通濾波器,得到基帶復信號,然后做FFT,將本地偽碼信號做FFT并取共軛與做過FFT的基帶復信號相乘,最后做IFFT變換,將最后結果取模,并對結果進行門限判斷。若超過門限值,則說明信號捕獲成功,尖峰對應位置就是偽碼相位,本地載波頻率就是接收信號所在的載波頻率;若沒有超過門限值,則重設本地載波發生器的值,重新開始捕獲。

假設x(n)是接收的C/A 碼序列,c(n)是本地產生的C/A碼序列;基于FFT的捕獲算法是按如下方式實現的:

=IFFT{FFT[x(n)]·

FFT[c*(-n)]}.

(1)

基于FFT的捕獲算法通過FFT代替大量的相關運算,不僅大大縮短了捕獲時間,并且減小了硬件實現難度,可以適應高動態環境對系統快速反應能力的要求[3]。

當GPS信號比較微弱時,僅選取1 ms長度的數據無法有效捕獲到信號,通用方法是通過增加數據的長度和增加累加次數來實現對弱信號的捕獲。針對弱信號條件下的捕獲技術也有很多學者作了研究,如相干積分和非相干積分、差分相干積分等。

1.1 相干積分法

相干積分法利用累加時間內信號的相關性,只將信號能量累加起來,噪聲能量不隨累加時間而累加。相干的含義就是保留所有相位信息,對應相位點的相關值累加[4]。其數學表達式為

(2)

式中: Rk(τ,fd)表示第k個C/A碼周期的相關值矩陣;τ和fd分別表示碼相位點和多普勒頻移，相干累積增益GCOH可以表示為

GCOH=10log(N),

(3)

式中,N為參與相干累積的毫秒數。對于相干積分法而言,導航電文數據位的跳變會使得信號部分甚至完全抵消。

1.2 非相干積分法

“非相干”的含義是去除相位信息,僅保留幅度信息。即將相干累積后的同相和正交兩支路信號求模平方,再累積,非相干累積使得導航電文的影響不是很明顯。其數學表達式為

(4)

式中:Rk(τ,fd)表示第k個相干累計矩陣;N為非相干累積次數。在非相干積分中,噪聲和信號同時被平方,不僅噪聲本身經平方后放大,而且噪聲與信號的交叉項成為新的噪聲,稱這種損失為“平方損失”。非相干累積增益GNCH等于相干累積增益減去非相干累積損失。

GNCH=GCOH-L(n)=10log(N)-L(n).

(5)

其中,非相干積分的平方損耗L(n)

(6)

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

1.3 差分相干積分

差分相干積分法是采用相鄰兩個碼元相關結果的非相關性,把相關結果共軛相乘后累加,減小了平方損失,也削弱導航電文數據位跳變的影響,是目前微弱信號捕獲算法中性能最好的[6]，其數學表達式為

(7)

差分累積算法對噪聲的放大較小,能夠減小平方損失,對信噪比的改善優于非相干積分累積,而劣于相干積分累積。

2 改進算法及完整捕獲方案

2.1 先累加后相關的分塊相干積分法

由上面分析可得,相干積分累積和非相干積分累積的方法在微弱GPS信號處理中都能帶來信噪比的增益,但是兩種方法也都存在局限性。一般是將這兩種累積方式結合起來,采取折中的方式來盡可能地提高捕獲過程的性能。其中結合的典型算法就是半比特算法和全比特算法[8]。

全比特算法能規避比特跳變的影響采用20ms相干累積,半比特算法只用10ms的相干累積,因而在處理相同數據長度和載噪比條件下,全比特算法的信噪比改善性能要優于半比特算法。但是全比特算法需要20ms的相干積分,運算量比較大,因為基于FFT的捕獲方式,算法計算量主要由FFT/IFFT的運算量來決定,而全比特算法FFT/IFFT的點數較大。本文針對減少算法運算量的問題,給出了“先累加后相關”的分塊積分方式:即將要處理的數據先分為M塊,每塊ams,然后將每塊ams的數據累加成1 ms,再對累加的各塊數據與本地信號進行獨立的相干積分,最后將各塊數據的相干結果進行非相干求和，累積方法如圖1所示。

圖1 “先累加后相關”分塊相干積分示意圖

與傳統的“先相關后累加”的方式相比,先累加后相關的優勢在于:累加增加了信號的強度,而不會對信號造成影響;而且噪聲為高斯白噪聲,均值為0,累加操作可以一定程度上減少噪聲影響,并大大的降低了運算量。但是先累加后相關的積分方式在累加時會受到導航電文數據位翻轉的影響,因此對于微弱GPS信號的捕獲,還需考慮翻轉位預測來減弱甚至消除位翻轉所帶來的負面影響[8]。

2.2 導航電文翻轉位預測算法

本文提出了兩種簡單有效的方法對翻轉位進行粗估計,從而舍棄其中數據位翻轉的那塊數據消除其負面影響,將相干積分時間延長至15 ms.

圖2 翻轉位預測數據分組示意圖

(8)

然后比較各塊數據的最大積分值,值最小的即為可能包含翻轉位的數據塊,稱該數據塊為翻轉塊，因此,為了規避導航電文翻轉可能帶來的負面影響,在之后的捕獲方案中舍棄每組20ms數據中的翻轉塊。假設第i塊數據為翻轉塊,則捕獲數據從接收數據的第(4i+1)ms開始選取,即取第N×(4i+1)ms至第N×(4i+15)ms共N塊連續15ms的數據作為捕獲數據,捕獲方案采取基于FFT的“先累加后相干”的分塊相干積分進行運算。

(9)

得到各塊數據的積分值后采用式(10)的方法得到每塊數據的相關結果。

(10)

以R4的計算較為特殊,選擇了下一組數據塊1進行共軛相乘,之所以這樣做是由于導航電文翻轉情況復雜,周期為20 ms,R4采用不同組的數據塊共軛相乘規避了若發生翻轉則同一組的數據塊1和數據塊4必然異號給翻轉位預測判決所帶來的干擾。將各塊數據差分相干結果計算完成后比較各個數據差分結果的最大積分值,找到最大值相對較小的數據塊即為包含翻轉位的數據塊,稱之為翻轉塊。在之后的捕獲方案中舍棄每組20 ms數據中的翻轉塊。假設第i塊數據為翻轉塊,則捕獲數據從接收數據的第(4i+1)ms開始選取,即取第N×(4i+1) ms至第N×(4i+15)ms共N塊連續15 ms的數據作為捕獲數據,捕獲方案采取基于FFT的“先累加后相干”的分塊相干積分進行運算。

2.3 改進算法的完整捕獲流程

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

1) 首先將中頻輸入信號按照圖2的方式進行分塊分組,每組20 ms,每組數據以5 ms為單位進行分塊。本文取四組連續的20 ms數據;

3) 將各塊相關結果直接非相干累加(算法一)或將前后兩個數據塊相干結果共軛相乘(算法二),得到各塊數據相干積分結果矩陣Rn,比較各塊數據的最大積分值來預測翻轉位,舍棄翻轉塊;

4) 從翻轉塊之后開始取80 ms的GPS中頻數據,剔除翻轉塊并對數據進行分組,將每組15 ms數據進行累加運算得到4組長度為1 ms的數據；

5) 對每組1 ms的數據進行FFT,并將FFT結果與本地產生的41個步長為500 Hz的C/A碼的共軛FFT相乘,分別對每組相乘結果進行IFFT后取模進行非相干累積,得到最終相關值矩陣R;

6) 搜索相關值矩陣R中最大相關值和次大相關值,并進行捕獲判決:即最大相關值/次大相關值>閾值,則認為捕獲成功,繼而得到相應的載波相位和多普勒頻移,否則認為捕獲失敗。

完整的捕獲方案流程圖如圖3所示。

圖3 改進的捕獲算法框圖

3 算法仿真及結果比較

為了對前面兩種算法所作的翻轉位預測分析進行仿真驗證,本文在Matlab環境下對微弱GPS信號的碼捕獲過程進行仿真,仿真數據采用Matlab生成的GPS中頻信號數據,中頻頻率為4.092 MHz,采樣頻率16.368 MHz,仿真信號參數選擇信噪比取值在-20～35 dB之間,噪聲是高斯白噪聲，捕獲時多普勒頻率步長為500 Hz,本文采用1號衛星4段連續的20 ms共80 ms的數據來進行驗證、對比。

仿真實驗主要基于以下兩個目的:

1) 分別驗證本文提出的兩種改進算法對于預測導航電文翻轉位置行之有效,改進的捕獲方案對微弱GPS信號切實可行;

2) 從碼相位捕獲結果、捕獲概率、算法執行時間對比本文提出的捕獲方案和傳統的捕獲算法。

3.1 仿真實驗主要模塊

仿真軟件部分由Matlab實現,主要模塊有GPS中頻數據仿真、翻轉位預測、信號搜索、捕獲和數據處理輸出。圖4為其軟件設計流程示意圖。

圖4 軟件設計流程圖

3.2 導航電文翻轉位置預測及捕獲結果分析

首先對本文提出的兩種翻轉位預測算法進行驗證,在產生的同一組信號下(即具有相同的信噪比-20 dB,導航電文均設置在數據塊1翻轉)分別在Matlab平臺上運行算法一和算法二,并繪制出各個數據塊的相關值,如圖5所示。

由圖5可以看出,算法一和算法二的判決結果均是數據塊1的最大積分值max(R2)較小,因此數據塊1為翻轉塊,這與生成的仿真數據相一致,故兩種算法在導航電文翻轉位預測上有效可行。

在對翻轉位進行粗估計后,舍棄掉每組翻轉塊的5 ms數據(數據塊2),從翻轉塊之后開始選取4塊連續15 ms的數據作為捕獲數據,利用式(3)、式(5)、式(6)可計算出本文提出的改進的捕獲方案所能獲得的捕獲增益為

G=GCOH+GNCH=10lg(NT)+

10lg(N)-L(n),

(11)

代入NT=15,N=n=4,Dc(1)=21計算可得G=15 dB,GPS信號的標稱信噪比為-20 dB[9],按照上述增益計算,基于本文提出的改進捕獲算法對60 ms長度的數據理論上能夠捕獲信噪比為-35 dB的信號,下面進行仿真驗證;仿真生成1號衛星的信噪比為-40 dB的信號,基于本文提出的改進算法的捕獲結果如圖6,圖7所示。

圖5 翻轉位預測算法各數據塊相干結果(a)算法一；(b) 算法二

圖6 1號衛星捕獲結果

圖7 1號衛星碼相位捕獲細化圖

圖6示出有明顯的相關峰存在,程序得到的碼相位3 475和載波頻率4.092 MHz也與仿真生成的GPS信號數據相吻合,因此捕獲成功,本文提出的改進捕獲方案有效可行。

3.3 檢測概率分析

將處理信號數據長度設定為60 ms,通過仿真比較本文提出的改進捕獲方案與傳統捕獲方法在不同載噪比狀態下的檢測性能,得到如圖8所示的曲線,從圖中可以看出,隨著載噪比的降低,改進捕獲方法的檢測性能明顯優于傳統捕獲方法。在信噪比為-35 dB的情況下,傳統算法的檢測概率僅僅為83%,而改進算法則能達到90%的檢測概率,說明改進算法更加適合弱信號環境。表1選取1號衛星信噪比為-35 dB的60 ms連續信號,分別從碼相結果、算法執行時間、捕獲概率三個方面來對比傳統捕獲算法和改進后的捕獲算法,進行仿真實驗時,利用的聯想計算機配置參數為:Microsoft Windows 10 Professional SP3 Inter?CoreTMi5-4570 @ 3.20 GHz.由表1可見,改進后的捕獲算法,碼相結果更加精準,運行時間縮短近1/3,檢測性能更優。

圖8 不同信噪比捕獲概率對比示意圖

表1 傳統算法與改進算法捕獲結果對比

4 結束語

針對弱信號環境下GPS信號的捕獲問題,本文提出了基于FFT的導航電文翻轉位估計的微弱信號捕獲算法,通過對翻轉位的粗估計較半比特算法將相干積分時間延長至15 ms,并在相干累積、非相干累積及差分累積的優缺點的基礎上提出了“先累加后相關”的分塊相干累積算法[10],平衡了前三種累積算法的矛盾,減少了運算量,較適宜弱信號環境下的捕獲。仿真實驗結果表明,改進后的捕獲算法能夠捕獲到信噪比為-40 dB的GPS信號,在相同信號環境下其較于傳統捕獲算法具有更高的相關峰值、更高的檢測概率、更短的執行時間。因此,本文提出的改進算法為弱信號捕獲算法應用于工程實際提供了參考,對我國北斗導航接收終端研發工作具有很好的借鑒作用。下一步研究工作將基于如何降低“先累加后相關”的分塊相干累積算法的虛警概率、進一步提高捕獲靈敏度等展開。

[1] KAPLAN E D. GPS原理與應用[M].2版.寇艷紅譯,北京:電子工業出版社,2007.

[2] 黃鵬達. 微弱GPS信號捕獲算法研究[D].成都：電子科技大學,2008.

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

[4] 張文,饒谷音,韓松來,等.不同相干積分方法對GPS弱信號捕獲的影響[J].數據采集與處理,2012(1):38-44.

[5] 劉詩涵,王可東.一種改進的全比特算法[J]. 全球定位系統,2015,40(6):11-15.

[6] 馬若飛. GPS弱信號捕獲算法研究及其在軟件接收機上的實現[D].哈爾彬:哈爾濱工業大學,2010.

[7] SELLONE F. Robust autofocusing widebandDOA estimation.[J]. Signal Processing,2006,86(1):17-47.

[8] AHAMED S F, RAO S,GANESH L. Fast acquisition of GPS signal using FFT decomposition[J]. Procedia Computer Science,2016(87):190-197.

[9] 陳慶.微弱GPS/北斗基帶信號捕獲研究與實現[D].廣州:暨南大學,2013.

[10] 吳勇.GPS弱信號的捕獲與跟蹤的算法研究[D].重慶:重慶大學,2012.

An Improved Weak GPS Signal Acquisition Algorithm Based on FFT

TIAN Tuo,ZHANG Fengguo,CHEN Qidong,ZHEN Weimin

(ChinaResearchInstituteofRadiowavePropagation,Qingdao266107,China)

Traditional acquisition algorithm of Global Positioning System weak signal used to improve the SNR gain by extending the coherent integration. But it is limited in the navigation data bit flipping. Coherent integration time is generally not more than 20 ms and the operation efficiency is not high. Two improved prediction algorithms are proposed to solve the problem of overcoming the navigation data bit flipping and increasing the computational efficiency in the weak signal environment. Based on the prediction results, an improved capture scheme is proposed in this paper. Firstly, the 5 ms signal with possible involve bit-flipping was canceled to eliminate its influence, then coherent integration was applied to its sub-block signal in the remaining 15 ms, which the summation operation was done ahead of coherent integration. Finally, by verifying and comparing with the traditional acquisition algorithm on the Matlab platform, the simulation show that the improved acquisition algorithm even can capture weak signals with Signal-to-Noise-Ratio(SNR) as low as -40 dB. The coherent integration time have been increased to 15 ms by predicting the navigation data bit flipping. Compared with the traditional capture algorithm, the acquisition sensitivity and the execution time have been improved.

Weak GPS signal; bit-flipping prediction; block coherent integration; FFT

2016-10-26

10.13442/j.gnss.1008-9268.2016.06.007

P228.4

1008-9268(2016)06-0030-07

田拓(1992-),男,碩士生,主要從事導航應用與干擾檢測方面的研究。

張風國(1985-),男,工程師,主要從事導航應用方面研究。

陳奇東(1980-),男,高級工程師,主要從事無線電信號處理和衛星導航應用研究。

甄衛民(1963-),男,研究員，博士生導師，主要從事空間環境、電磁環境和衛星導航領域研究。

聯系人：田拓 E-mail: 705722543@qq.com