雙門限唐檢測改進算法

張超逸,李金海,閻躍鵬

(1.中國科學院微電子研究所,北京100029;2.中國科學院大學,北京100049)

0 引 言

全球導航衛星系統(Global navigation satellite system,GNSS)采用直接序列擴頻技術實現定位、測速和授時功能。在導航接收機設計中,需要完成信號在時域和頻域的二維捕獲,并對每個捕獲單元的結果進行檢測確認[1-3]。最基本的檢測確認方法是對每個單元的信號進行積分和清零,將得到的包絡與門限相比較,以確定衛星信號是否存在。由于單次駐留檢測的虛警概率過高,無法滿足系統要求,需采用多次駐留檢測來對捕獲結果進行確認[4]。唐檢測算法憑借可變的駐留次數、計算量少、結構簡單以及在低信噪比下良好的檢測性能得到了廣泛的應用[5]。為了提升檢測性能,文獻[6]提出了含近鄰約束的改進唐檢測算法,增強對弱信號的檢測能力,但檢測速度并未得到有效提高。為解決駐留次數不確定導致檢測器長時間駐留在某個捕獲單元中的問題,文獻[7]提出了對單次檢測的總次數設置門限進行約束的方法,通過選擇合理的次數門限,使得在檢測性能不受影響的條件下可以有效控制檢測次數,但該算法主要針對弱信號情況,對平均駐留次數影響有限。文獻[8]在捕獲模塊之前增加了一個能量估計模塊,通過自適應調整門限和駐留次數來提高檢測性能,但檢測速度受能量估計值影響較大,同時會帶來大量額外的計算復雜度。檢測速度對接收機至關重要,直接決定了衛星從捕獲狀態轉至跟蹤狀態所需的時間。為了加快檢測速度,本文基于傳統唐檢測算法,提出了采用雙門限比較的唐檢測改進算法,該算法將信號包絡與兩級門限分別比較后作出檢測判決,在檢測性能基本不受影響的前提下,有效降低了平均駐留次數,減少了檢測確認時間。

1 檢測統計量

接收機天線接收到導航信號后通過射頻模塊下變頻為數字中頻信號,再經過解調、解擴、相干積分和清零之后得到I、Q兩路信號的表達式如下[9]:

式中:a為信號幅值;D為相干積分時間內調制的導航電文;R為擴頻碼自相關函數;τ為本地碼與輸入信號之間的碼相位差;T為相干積分時長;fe為本地載波和輸入信號的載波頻率差;φe為本地載波和輸入信號的載波相位差;n I和n Q為互不相關的均值為零、方差為的高斯白噪聲。

對I、Q兩路信號進行如下式的非相干積分:

本文取V2作為單次檢測的檢測統計量,即對Nnc個I、Q兩路信號的相干積分功率和進行累加。當衛星信號不存在時,V2服從自由度為2Nnc的中心卡方(χ2)分布。令y＝v2,則其概率密度函數為[10]:

式中:Γ(p)為γ函數。此時的概率密度函數僅與相干積分后的噪聲功率、非相干次數有關。當衛星信號存在時,V2服從自由度為2Nnc的非中心卡方分布。

令y＝v2,則其概率密度函數為[10]:

式中:Iα(x)為第一類α階修正貝塞爾函數;s2稱為非中心分布參量,考慮碼相位偏差τ與載波頻率偏差fe均為0的情況下定義為:

可以看出此時的概率密度函數還與輸入信號的功率有關。

單次檢測的虛警概率計算表達式如下:

式中:Vt為檢測門限值。

單次檢測的檢測概率計算表達式如下:

式中:Q m(a,b)為廣義馬庫姆(Marcum′s)Q函數。

由式(6)(7)可知,在相同檢測條件下,虛警概率越低,所需的檢測門限值越大,相應的檢測概率也越低,因此,在虛警概率和檢測概率之間需要取得折中。檢測時采用Neyman-Pearson準則,在給定單次檢測的虛警概率Pfa和由接收機估計得到的噪聲功率后由式(6)計算得到檢測門限Vt,然后再由式(7)計算得到單次檢測的檢測概率Pd。

2 唐檢測算法介紹

唐檢測算法是一種可變駐留次數的檢測確認算法,其將檢測統計量與門限相比較,若大于門限,則檢測計數器K加1;若小于門限,則檢測計數器K減1。經過多次檢測后,當K達到次數門限A時,認為信號存在。當K＝0時,認為信號不存在。這里K的初始值取B。算法流程圖如圖1所示。

圖1 唐檢測器檢測算法流程Fig.1 Flow diagram of Tong detection algorithm

文獻[11]給出了唐檢測算法的系統虛警概率為:

相干積分時長T＝1 ms,非相干次數Nnc＝1,系統虛警概率PFA＝10－6,B＝1時,A取不同值、不同信噪比下的系統檢測概率PD如圖2所示。

圖2 唐檢測系統檢測概率Fig.2 System detection probability of Tong detection

為了進行性能比較,圖2中同時給出了單次檢測的檢測概率?？梢钥闯?單次檢測要滿足檢測概率大于90%的條件,信噪比需要大于13.5 dB,這樣的檢測性能是導航接收機無法接受的。而在相同的虛警概率下,經過唐檢測處理后接收機的檢測性能得到大幅提升。如當A等于4時,滿足檢測概率大于90%所需信噪比僅為9.5 d B,比單次檢測降低4 dB,且A越大檢測性能越好。

表1給出了A取值不同時噪聲單元的平均駐留次數,以及當系統檢測概率等于90%時信號單元的平均駐留次數。當僅采用單次檢測確認算法時,在每個捕獲單元僅駐留1次。采用唐檢測算法后,由表1可以看出,信號單元和噪聲單元的平均駐留次數都增加,且信號單元的平均駐留次數遠大于噪聲單元。隨著A的增大,平均駐留次數也在增加。較大的平均駐留次數會導致接收機檢測確認速度過慢,增加捕獲轉跟蹤所需的時間。因此,有必要對唐檢測算法進行改進,減少平均駐留次數,尤其是信號單元的平均駐留次數。

表1 唐檢測平均駐留次數Table 1 Average dwell times of Tong detection

3 本文算法

3.1 算法簡介

為了有效減少平均駐留次數,在單門限檢測的基礎上額外增加另一個較大的門限,構成兩級門限檢測。首先,判斷檢測統計量與較小的第一級門限的比較結果,當大于第一級門限時,檢測計數器K加1,否則,檢測計數器K減1。接著,判斷檢測統計量與較大的第二級門限的比較結果,當大于第二級門限時檢測計數器K加1,否則不做處理。改進算法流程如圖3所示。

圖3 雙門限唐檢測器檢測算法流程Fig.3 Flow diagram of Tong detection algorithm with double thresholds

由于第二級門限較大,具有較小的虛警概率,檢測通過門限的信號存在概率較大,這時對檢測計數器K再加1是合理的。通過設置兩級門限,在信號存在時,使得檢測計數器K能夠更為迅速地接近檢測次數門限A,減少平均駐留次數,提高檢測速度。

3.2 理論分析

唐檢測的數學模型可以采用具有兩個吸收態的馬爾可夫鏈來描述[6,7]。每個馬爾可夫鏈包含有一個狀態集S和一個轉移概率矩陣P。狀態集S包含了所有可能出現的狀態。從狀態i轉移到狀態j的概率稱為轉移概率P ij,其中i,j∈S。所有的P ij組成轉移概率矩陣P。當P ii＝1,P ij＝0,i≠j時,稱狀態i為吸收態。唐檢測算法對應的狀態集S＝{0,1,…,A},吸收態為0和A。

令第一級門限對應的虛警概率為Pfa1,第二級門限對應的虛警概率為Pfa2。定義p0＝1－Pfa1表示小于第一級門限的概率;p1＝Pfa1－Pfa2表示大于第一級門限小于第二級門限的概率;p2＝Pfa2表示大于第二級門限的概率。p0、p1、p2均大于0,且p0＋p1＋p2＝1。由改進算法流程可知,從狀態i到狀態i－1的概率為p0,從狀態i到狀態i＋1的概率為p1,從狀態i到狀態i＋2的概率為p2,到其余狀態的概率均為0,則可以得到改進算法的轉移概率矩陣如下:

對式(14)中的a i表達式進行等價變換可得:

聯立式(17)(18)(19)可求得δ0的表達式。又δ0＝a1－a0＝a1,a1表示從狀態i＝B＝1出發,到達吸收態A的概率,即給定兩級門限的虛警概率后可計算得到系統虛警概率為:

同理,用兩級門限的檢測概率Pd1、Pd2代替虛警概率Pfa1、Pfa2,按照上述推導,即可得到系統檢測概率,與式(20)形式一致。

定義從狀態i到吸收態A或0的平均次數為平均駐留次數μi(i＝0,1,…,A),則μi滿足如下線性方程組:

聯立式(24)(25)(26)可求得η0的表達式。又η0＝μ1－μ0＝μ1,μ1表示從狀態i＝B＝1出發,到達吸收態A或0的平均次數,即給定兩級門限的虛警概率后可計算得到噪聲單元的平均駐留次數為:

同理,用兩級門限的檢測概率Pd1、Pd2代替虛警概率Pfa1、Pfa2,按照上述推導,即可得到信號單元的平均駐留次數,與式(27)形式一致。

3.3 檢測性能

為了得到第二級門限不同取值對系統虛警概率和系統檢測概率的影響,設置理論仿真條件如下:

(1)取A＝4,B＝1,T＝1 ms,Nnc＝1。

(2)取PFA＝10－6,通過式(8)計算得到Pfa＝0.009 934,將其作為第一級門限對應的虛警概率,即Pfa1＝Pfa。

(3)取Pfa2分別等于10－3、10－4、10－5、10－6、10－7作為第二級門限對應的虛警概率。

根據式(20)計算得到雙門限下的系統虛警概率,結果如表2所示。

表2 雙門限唐檢測系統虛警概率Table 2 System false alarm probability of Tong detection with double thresholds

未增加第二級門限時,單門限檢測算法對應的系統虛警概率為10－6。增加第二級門限后,由表2可看出,雙門限檢測算法的系統虛警概率有所增加,但隨著第二級門限對應的虛警概率變小(即第二級門限值變大),雙門限檢測算法的系統虛警概率隨之變小,且不斷逼近單門限檢測算法的系統虛警概率10－6。如在本例中,當第二級門限所對應的虛警概率小于等于10－4時,雙門限檢測算法的系統虛警概率與單門限檢測算法的系統虛警概率已處于同一數量級。

為了分析上述仿真條件下的系統檢測概率,首先分別將Pfa1和不同取值的Pfa2代入式(6)求得對應的門限值,然后將門限值代入式(7)計算得到單次檢測概率Pd1和Pd2,最后求出不同信噪比下的雙門限檢測算法系統檢測概率,如圖4所示。

圖4 雙門限唐檢測系統檢測概率Fig.4 System detection probability of Tong detection with double thresholds

從圖4可以看出,不同Pfa2取值下的雙門限檢測算法系統檢測概率在不同信噪比下同單門限檢測算法相比均略有提升。隨著第二級門限對應的虛警概率變大,系統檢測概率的提升越明顯。

當A取其他值時,雙門限檢測算法的系統虛警概率和系統檢測概率也具有上述特點。即雙門限檢測算法在檢測性能上會增加系統虛警概率和系統檢測概率,但可通過合理設置第二級門限值使其檢測性能與單門限檢測算法基本相同。

3.4 駐留次數

在相同的理論仿真條件下,設置不同的第二級門限后,根據式(27)計算得到的雙門限噪聲單元平均駐留次數如表3所示。

表3 噪聲單元平均駐留次數Table 3 Average dwell times for noise cells

由表1得到單門限檢測算法的噪聲單元平均駐留次數為1.0203。與表3的雙門限結果對比可以看出,雙門限檢測算法對噪聲單元的平均駐留次數影響較小,與單門限時的平均駐留次數基本相等。

不同信噪比下不同第二級門限所對應的信號單元平均駐留次數如圖5所示。

圖5 信號單元平均駐留次數Fig.5 Average dwell times for signal cells

從圖5可以看出,第二級檢測門限對應的虛警概率越大,平均駐留次數越少,檢測速度越快。表4給出了采用雙門限檢測算法在A取值不同下,系統虛警概率滿足1.2×10－6時第二級門限對應的虛警概率大小,以及此時系統檢測概率等于90%時信號單元的平均駐留次數和與單門限結果比較的差值Diff。

由表4可以看出,雙門限檢測算法在系統虛警概率從1.0×10－6略微提高到1.2×10－6的條件下,能有效減少平均駐留次數,且A越大次數減少得越多,從而大大提高了信號單元的檢測速度。

表4 雙門限唐檢測性能Table 4 Performance of Tong detection with double thresholds

3.5 算法應用

在實際應用中,雙門限唐檢測算法的兩級門限可通過如下步驟選取:

(1)已知接收機的系統虛警概率要求為PFA,通過式(8)計算得到單門限唐檢測算法對應的單次檢測虛警概率Pfa,將其作為雙門限算法中第一級門限的虛警概率Pfa1,并通過式(6)計算得到對應的門限值Vt1。

(2)選取n個小于Pfa1的值作為第二級門限的虛警概率估計值,然后將代入式(20)求出雙門限唐檢測算法的系統虛警概率。n的大小取決于對虛警概率估計精度的要求。

通過上述方法選取的門限大小可使雙門限唐檢測算法的系統虛警概率與單門限唐檢測算法的系統虛警概率處于同一數量級,使得算法對接收機系統性能的影響可以忽略。與此同時,使得系統檢測概率的提升最大,信號單元平均駐留次數的減少也最大,有效提高了接收機的檢測速度。

在各系統可見衛星數為10顆,三系統聯合定位,駐留時間T＝1 ms,非相干次數Nnc＝1,A取12的條件下,經仿真得出,采用改進算法對每顆衛星進行捕獲檢測確認,共可減少檢測確認時間82.161 ms。在針對弱信號的捕獲檢測中,需要更大的A,更長的相干積分時長T和更多的非相干次數N,此時采用改進算法節省的檢測確認時間更為可觀。此外,改進算法僅需額外增加一個比較器,在實現過程中硬件資源消耗非常少。

4 仿真結果

用思博倫GSS9000模擬信號發生器產生不同信噪比的GPS信號,再用采集器將信號轉換為數字中頻信號后用于仿真校驗。采集器的采樣率為16.368 MHz,數字中頻頻率為4.092 MHz。仿真條件為A＝4,B＝1,T＝1 ms,Nnc＝1,PFA＝10－6,Pfa1＝0.009 934。圖6為在Pfa2＝10－5條件下雙門限唐檢測算法系統檢測概率的理論值與仿真值。圖7分別給出了單門限、Pfa2＝10－3、Pfa2＝10－5三種情況下的唐檢測算法平均駐留次數的理論值與仿真值。

圖6 系統檢測概率仿真結果Fig.6 Simulation result of system detection probability

圖7 信號單元平均駐留次數仿真結果Fig.7 Simulation result of average dwell times for signal cells

從圖6和圖7可以看出,理論與實際仿真結果基本吻合,從而驗證了理論推導分析,雙門限改進唐檢測算法確實能有效減少平均駐留次數,提高檢測速度。

5 結束語

針對唐檢測算法平均駐留次數過長導致檢測速度較慢的問題,在唐檢測算法中引入第二級門限用于比較檢測。算法經過了理論推導和性能分析,并且通過實際仿真校驗。結果表明,雙門限唐檢測算法在檢測性能上會略微增加系統虛警概率和檢測概率;在平均駐留次數上,噪聲單元的平均駐留次數基本不變,信號單元的平均駐留次數明顯減少。因此,通過給定系統虛警概率選擇合適的第二級門限,使得雙門限檢測算法可以有效提升檢測速度。

[1]Zhu Z,Graas F V,Pelgrum W.C/A code cross-correlation at a high doppler offset[J].IEEE Transactions on Aerospace and Electronic Systems,2015,51(3):1826-1838.

[2]劉曉明,張鶴,吳皓威,等.高動態環境下長碼擴頻信號快速捕獲算法[J].電子與信息學報,2016,38(6):1398-1405.Liu Xiao-ming,Zhang He,Wu Hao-wei,et al.Rapid DSSS signal acquisition algorithm under high dynamic environment[J].Journal of Electronics&Information Technology,2016,38(6):1398-1405.

[3]Zhu C,Fan X.A novel method to extend coherent integration for weak GPS signal acquisition[J].IEEE Communications Letters,2015,19(8):1343-1346.

[4]Renzo M D,Annoni L A,Graziosi F,et al.A novel class of algorithms for timing acquisition of differential transmitted reference UWB receivers:architecture,performance analysis and system design[J].IEEE Transactions on Wireless Communications,2008,7(6):2368-2387.

[5]Kaplan E D,Hegarty C H.Understanding GPS:Principles and Applications[M].Boston:Artech House,2006:223-227.

[6]馬琳,崔嵬,吳嗣亮.極低信噪比環境下含近鄰約束的改進唐檢測判決算法[J].系統工程與電子技術,2011,33(8):1745-1749.Ma Lin,Cui Wei,Wu Si-liang.Improved Tong multiple trial algorithm with near neighbor constraint in extremely low SNR condition[J].Systems Engineering and Electronics,2011,33(8):1745-1749.

[7]馬琳,崔嵬,田靜,等.基于馬爾可夫鏈的含有檢測次數約束條件的唐檢測器[J].宇航學報,2011,32(8):1799-1804.Ma Lin,Cui Wei,Tian Jing,et al.Study on Tong detector with number of detection times constraint based on Markov chain[J].Journal of Astronautics,2011,32(8):1799-1804.

[8]Park H,Lee S.PN code acquisition technique with an adaptive dwell time in DS-SS system[C]∥23rd International Conference on Software,Telecommunications and Computer Networks,Split,Croatia,2015:341-345.

[9]謝崗.GPS原理與接收機設計[M].北京:電子工業出版社,2009:286-287.

[10]Proakis J G.數字通信[M].4版.北京:電子工業出版社,2003:29-31.

[11]姚錚,崔曉偉,陸明泉,等.應用于GPS接收機的序貫檢測器性能分析[J].清華大學學報:自然科學版,2007,47(7):1166-1169.Yao Zheng,Cui Xiao-wei,Lu Ming-quan,et al.Performance analysis of sequential detector for GPS receivers[J].Journal of Tsinghua University(Science and Technology),2007,47(7):1166-1169.

[12]李思超,葉甜春,徐建華.唐檢測器的駐留時間及檢測性能分析[J].電子測量技術,2009,34(3):53-55.Li Si-chao,Ye Tian-chun,Xu Jian-hua.Analysis on resident time and detection performance of tong detector[J].Electronic Measurement Technology,2009,34(3):53-55.

[13]朱云龍,丑武勝,楊東凱.Tong檢測算法性能分析及參數設置[J].北京航空航天大學學報,2015,41(3):418-423.Zhu Yun-long,Chou Wu-sheng,Yang Dong-kai.Performance analysis and parameter setting for Tong detection algorithm[J].Journal of Beijing University of Aeronautics and Astronautics,2015,41(3):418-423.