基于壓縮感知的GPS信號壓縮與捕獲研究

何國棟 ,汪佳瑞 ,靳蓓蓓 ,王濤春

(1. 安徽師范大學 物理與電子信息學院,安徽 蕪湖241003；2. 安徽師范大學 數學計算機科學學院,安徽 蕪湖 241003)

?

基于壓縮感知的GPS信號壓縮與捕獲研究

何國棟1,汪佳瑞1,靳蓓蓓1,王濤春2

(1. 安徽師范大學 物理與電子信息學院,安徽 蕪湖241003；2. 安徽師范大學 數學計算機科學學院,安徽 蕪湖 241003)

全球定位系統(Global Position System，GPS)信號的捕獲是其應用的關鍵步驟，直接影響系統的正常運行。針對衛星導航信號所具有的稀疏特性，結合壓縮感知理論稀疏性的要求，設計了基于衛星特性的稀疏字典，應用隨機矩陣對信號進行壓縮，獲得GPS壓縮信號，通過正交匹配追蹤算法對壓縮后的GPS信號進行捕獲。最后通過大量的仿真實驗驗證了該方法的可行性，可以將其應用于 GPS數據壓縮、高信噪比快速捕獲及GPS信號源中。

壓縮感知；全球定位系統；捕獲；正交匹配跟蹤

0 引言

GPS采用碼分多址擴頻調制信號，GPS 信號高效準確的捕獲，是影響導航接收機正常工作的關鍵因素[1-2]。目前已有大量的文獻對GPS信號的捕獲進行了研究，常用的捕獲方法有串行捕獲、基于FFT的并行快速捕獲和微弱信號的長時累積捕獲[3-4]等。

Nyquist采樣定理指出采樣頻率必須高于信號最高頻率的2倍，這對高頻通信系統的采樣無疑是一個重要的制約因素，因此需要尋找新的理論突破。為解決這一技術發展的瓶頸，2006年Candès、Tao和Donoho等[5-6]人提出了壓縮感知的理論：對于稀疏或在某個字典下稀疏的信號，可以以遠低于Nyquist采樣速率對信號進行采樣，并可以通過重構算法實現信號的完美重構。壓縮感知充分利用了信號的稀疏特性，可大大降低信號的采樣速率，減少采樣數據，給信號的后期存儲、傳輸和處理帶來很大的便利。目前，壓縮感知得到了全球研究人員的廣泛關注，其應用的領域涉及模擬到信息轉換[7-8]、圖像處理[9]、無線通信[10]及醫學等[11]。

由于衛星PRN碼互相關具有稀疏特性，符合壓縮感知理論的稀疏性要求，并根據不同的衛星信號設計稀疏字典，應用隨機矩陣對接收的下變頻信號進行壓縮，獲得GPS壓縮信號。通過改進的匹配追蹤算法對壓縮后的GPS信號進行捕獲。仿真實驗驗證了該方法的可行性，可以在高壓縮率下對高信噪比信號準備捕獲，可以對實際GPS信號進行壓縮、捕獲，或應用于GPS信號源中。

1 傳統的GPS信號并行捕獲算法

射頻前端接收的GPS信號通過下變頻后變為中頻信號，第k個衛星信號的數學表達式為：

(1)

式中，Ck(t)為第k個衛星的PRN碼，Dk(t)為導航電文，ωI為中頻頻率，ωd為衛星和接收相對運動產生的多普勒頻移，θk為載波相位，n(t)為噪聲干擾。

捕獲的目的是為了粗略決定可見衛星的載波頻率和碼相位，傳統的碼分多址系統經常采用串行搜索捕獲方法，對所有衛星可能的碼相位和頻率進行二維搜索，計算量大，非常耗時。為了提高捕獲的效率，Frai D M、Reichman A等人[12-13]提出了并行捕獲算法，將二維搜索的一個域進行并行搜索，大大提高了捕獲的速度。

令2個長度為N的序列循環互相關序列為：

(2)

對式(2)進行N點離散傅里葉變換，得到：

(3)

式中，X*(k)為x(n)的傅里葉變換的共軛，Y(k)為y(n)的傅里葉變換的共軛。通過一次傅里葉逆變換，即可找到初始碼相位。根據上面的公式，并行碼相位捕獲原理如圖1所示。

圖1 GPS并行碼捕獲算法原理圖

2 壓縮感知

基于Nyquist采樣頻率的數據采集，沒有考慮信號內部的相關性，得到大量的冗余數據，然后對其進行壓縮，降低數據量。壓縮感知充分利用了數據的稀疏性，將數據的冗余采樣和壓縮合二為一，直接得到較少的采樣數據，給信號處理帶來便利。壓縮感知主要包含3個部分：信號的稀疏表示、測量矩陣和重構算法，下面簡單介紹這個3個部分的組成原理[14]。

2.1 信號的系數表示

給定信號x的長度為N，如果這個信號中大部分元素為零，只有k(k<

x=Ψ·s，

(4)

式中，s只有較少的非零元素，常用的基有離散余弦變換、離散傅里葉變換、小波變換和非正交冗余字典等。壓縮感知應用的前提是信號必須是稀疏的，所以信號的稀疏表示至關重要。

2.2 測量矩陣

測量矩陣Φ是一個M×N(M<

Y=Φ·x=Φ·Ψ·s=Θ·s。

(5)

通過測量獲得了長度為M測量信號Y，實現了對信號的壓縮。將式(5)中Φ*Ψ=Θ測量矩陣和字典合在一起稱為感知矩陣。

測量矩陣與基或字典必須滿足不相關性，其不相關公式定義為：

(6)

M≥c·u2(Φ,Ψ) ·k·ln(N)。

(7)

可以看出，M與相關值成正比，所以一般選用相關值較低的矩陣作為測量矩陣。常用的測量矩陣有Toeplitz矩陣、高斯分布的隨機矩陣和哈達碼矩陣等。

2.3 重構算法

從式(5)的測量過程可以看出，這是一個未知數比方程數多的欠定方程，該方程有無窮多組解，理論分析已經證明，在滿足不相關性和稀疏性的條件下，可以通過重構算法重構出原稀疏信號。基于優化的求解可以表示為：

(8)

式中，‖‖0為求信號中的非零元素的個數，但是上式的求解是一個NP-hard問題，可以通過其他算法進行求解，常用的求解方法有基追蹤算法、迭代法貪婪算法等。

3 基于壓縮感知的GPS信號壓縮與捕獲

根據壓縮感知的理論和GPS信號的特點，提出了一種基于壓縮感知的GPS信號壓縮與捕獲方法。應用隨機矩陣對GPS信號進行壓縮，根據衛星特性構造字典，并通過改進的匹配追蹤算法對衛星進行捕獲，其構成分為以下兩個部分。

3.1 稀疏字典的構造

在GPS串行捕獲方法中，通過碼片移位和多普勒頻移二維搜索尋找衛星，其公式表示為：

(9)

(10)

當本地產生的信號與接收信號的GOLD碼時間移位C(n-τ)和多普勒頻率e-jwdn都對齊時，會得到較強的相關峰，而在其余情況下該值都相對較小，也即捕獲結果是稀疏的，這與壓縮感知所描述的稀疏信號相符合，基于此捕獲原理設計稀疏字典。

字典包含1 023個GOLD碼片的循環移位和多普勒頻率的搜索范圍，一般多普勒頻率搜索范圍為±10 kHz，搜索步進為500 Hz，有41個頻率點，所以字典ψ=[Cn-τ·e-jωdn]∈Rn×(λ×41×1023)，其中λ為每個碼片的采樣點數，n為壓縮前數據的總長度。對于一顆衛星，如果接收的信號中含有該衛星發射的信號，則會有一個很強的相關峰值，而其余值都相對較小，即信號在該字典中可稀疏表示。

3.2 重構算法

壓縮感知重構算法很多，貪婪類算法中的匹配跟蹤算法重構速度較快，適合工程應用。考慮衛星系統的特殊性，即如果含有該衛星信號，則相關峰很強，而其余值都很弱。正交匹配追蹤算法可以重構出原稀疏信號[15-16]，但是考慮GPS信號捕獲只需找到其對應衛星的碼相移和多普勒頻率，設計了一種基于以上構造的稀疏字典正交匹配追蹤算法來捕獲衛星信號[17]，算法具體步驟如下：

初始化：輸入基于GPS偽碼和多普勒的稀疏字典，壓縮觀測信號，殘差r0=y；

Step1：找出殘差和感知矩陣相關積最大值對應的下標λ，即[Rk-1,λ]=argmaxj=1...N‖rk-1,Θj‖2；

Step3：計算最小二乘得到

Step5：判斷是否滿足迭代條件，設定捕獲閾值Thresh，不滿足則繼續執行Step1，如果R2/R1≥Thresh，則認為捕獲到一顆衛星，反之認為沒有該顆衛星信號，捕獲結束。

4 仿真與分析

為了驗證本文提出的基于壓縮感知的GPS信號壓縮和捕獲方法，應用Matlab對其進行仿真，其中測量矩陣使用的是歸一化的零均值高斯分布隨機矩陣，碼相位搜索步長為半個碼片，多普勒頻率步長搜索為500 Hz，為簡化仿真，多普勒頻率搜索范圍為-2.5 ～2.5 kHz。人為構建一顆衛星信號，隨機產生碼移位和多普勒頻移，構造模擬的GPS信號，應用隨機觀測矩陣對信號進行壓縮，并應用本文方法對其進行壓縮捕獲。

仿真以1號衛星為例，產生其對應的GOLD碼，采樣頻率Fs=38.192 MHz，中頻頻率Fc=9.548 MHz，多普勒頻偏和偽碼相移使用隨機產生的一個值，例如下面捕獲仿真中隨機產生的多普勒頻移Fd=0.657 7 kHz，偽碼相移Td=5 890，生成1 ms衛星信號。實驗分為無噪聲、高信噪比(10 dB)和低信噪比(-10 dB)3組，噪聲類型為零均值加性高斯白噪聲，分析其抗噪聲性能；每組又分別包含壓縮率α為70%、80%和90%三種情況，壓縮率定義由式(11)給出，從壓縮率和噪聲強度兩方面分析GPS信號壓縮與捕獲的關系。

(11)

對產生的1 ms信號分別進行100次蒙特卡洛實驗，給出了9組實驗中低信噪最低的捕獲結果圖，如圖2所示，因為這是最差捕獲環境，其余結果都比這種情況好。正確的多普勒頻率值為：5+ceil(0.655 7×103/500)=6，碼相位為ceil(38 192/5 890)=6.5，實驗捕獲的峰值位置為12 592，按照上面給出的字典構成原理反求對應的頻率點和相位點，也即捕獲的頻率點為12 592/2 046=6.15，相位：2 046/(12 592-2 046*6)=6.47。

通過仿真發現，在無噪聲、高信噪比和高壓縮率情況下均可以實現衛星的正常捕獲，但是在低信噪比情況下，當壓縮率為90%(即只保留了10%的采樣數據)時，很難對衛星正確捕獲。

(a)壓縮率為70%

(b)壓縮率為80%

(c)壓縮率為90%

5 結束語

提出了一種基于壓縮感知的GPS信號壓縮與捕獲方法，分析了GPS信號的稀疏特性，并根據衛星特性和壓縮感知理論構造了稀疏字典，應用隨機矩陣對信號進行了壓縮，并應用稀疏重構算法對衛星進行捕獲。通過大量仿真實驗驗證了該方法的可行性，可以將其思想應用到GPS數據的壓縮或模擬信號源中。本文提出方法在高壓縮率和低信噪比下捕獲效果較差，如何提高其性能將是進行后續研究的重要方向。

[1] Braasch M S,Van A J. GPS Receiver Architectures and Measurements[J]. Proceedings of the IEEE,1999,87(1):48-64.

[2] Kai B,Akos D M,Bertelsen N,et al. A Software-Defined GPS and Galileo Receiver[M]. Boston:Birkh?user Boston,2007.

[3] 陳希,張銳,帥濤. 基于FFT的GPS快速并行捕獲算法[J]. 宇航學報,2011,32(1):162-166.

[4] 唐琳琳. L1/L2C雙頻車載GPS軟件接收機快速捕獲算法研究[D]. 南京:南京航空航天大學,2015.

[5] Candès E J,Romberg J,Tao T. Robust Uncertainty Principles: Exact Signal Reconstruction from highly Incomplete Frequency Information[J]. Information Theory,IEEE Transactions on,2006,52(2): 489-509.

[6] Donoho D L. Compressed Sensing[J]. Information Theory,IEEE Transactions on,2006,52(4): 1289-1306.

[7] 何國棟,楊凌云,謝小娟,等. 基于壓縮感知的模擬到信息轉換研究[J]. 無線電通信技術,2015,41(1):21-23.

[8] Kirolos S,Laska J,Wakin M,et al. Analog-to-Information Conversion via Random Demodulation[C]∥Design,Applications,Integration and Software,2006 IEEE Dallas/CAS Workshop on. IEEE,2006: 71-74.

[9] Romberg J. Imaging via Compressive Sampling[J]. Signal Processing Magazine IEEE,2008,25(2):14-20.

[10]楊劍,蔣挺,趙成林,等. 基于CS-ROMP算法的超寬帶信道估計[J]. 無線電工程,2011,41(5): 14-17.

[11]Richy J,Friboulet D,Bernard A,et al. Blood Velocity Estimation Using Compressive Sensing[J]. IEEE Transactions on Medical Imaging,2013,32(11):1979-1988.

[12]Frai D M,Reichman A. Fast Acquisition CDMA Receiver for Burst Transmission System[C]∥ IEEE International Conference on Electronics,Circuits and Systems. IEEE,2004:342-345.

[13]Tang B,Liu S,Tang W,et al. Design a L1 Software GPS Receiver Based on IF GPS Signal Simulator[C]∥ International Conference on Signal Processing. IEEE Xplore,2006,3:109-115.

[14]何國棟,謝小娟,楊凌云,等. 基于壓縮感知的信號重構研究[J].無線電通信技術,2014,40(3):26-28.

[15]Tropp J A,Gilbert A C. Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J]. Information Theory,IEEE Transactions on,2007,53(12): 4655-4666.

[16]Tropp J A,Laska J N,Duarte M F,et al. Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals[J]. IEEE Transactions on Information Theory,2010,56(1):520-544.

[17]馬慶濤. 壓縮感知中的信號重構算法研究[D]. 南京:南京郵電大學,2013.

Research on GPS Signal Compressing and Acquisition Based on Compressive Sensing

HE Guo-dong1,WANG Jia-rui1,Jin Bei-bei1,WANG Tao-chun2

(1. College of Physics and Electronic Information,Anhui Normal University,Wuhu Anhui 241003,China; 2. School of Mathematics & Computer Science,Anhui Normal University，Wuhu Anhui 241003,China)

The acquisition of GPS signal is a key step in its application,directly affecting the normal operation of system. In view of the sparsity of satellite navigation signals and the requirement of sparsity of compressive sensing theory,this paper designs a satellite-based features sparse dictionary. The GPS signal is compressed by random matrix to obtain the GPS compressed signal. The satellite can be acquired from compressed GPS signal by orthogonal matching pursuit. The results of multiple simulation experiments show that this method is feasible,and it can be applied to the GPS data compression,high SNR fast acquisition and GPS signal source.

compressive sensing; GPS; acquisition; orthogonal matching pursuit

2017-03-30

國家自然科學基金項目(61402014)；安徽省高校自然科學重點項目(KJ2016A266)；安徽師范大學項目培育基金(2015xmpy16)

何國棟(1980—)，男，副教授，碩士生導師，主要研究方向：壓縮感知理論及其在信號處理中的應用等。王濤春(1979—)，男，副教授，碩士生導師，主要研究方向：壓縮感知理論與應用及無線傳感器網絡等。

10. 3969/j.issn. 1003-3114. 2017.05.09

何國棟,汪佳瑞,靳蓓蓓,等.基于壓縮感知的GPS信號壓縮與捕獲研究[J].無線電通信技術,2017,43(5):38-41.

[HE Guodong,WANG Jiarui,Jin Beibei,et al. Research on GPS Signal Compressing and Acquisition Based on Compressive Sensing [J]. Radio Communications Technology,2017,43(5): 38-41.]

TP391.4

A

1003-3114(2017)05-38-4