Tong檢測算法性能分析及參數(shù)設置

朱云龍，丑武勝，楊東凱

(1.北京航空航天大學 機械工程及自動化學院，北京100191;2.北京航空航天大學 電子信息工程學院，北京100191)

衛(wèi)星導航系統(tǒng)是國家重要基礎設施.接收機是系統(tǒng)與用戶的惟一接口，衛(wèi)星導航信號的捕獲是接收機信號處理部分的核心技術，用于搜索衛(wèi)星信號并將其牽引至跟蹤范圍內［1-2］.捕獲是對擴頻碼相位和載波頻率的二維搜索過程，捕獲系統(tǒng)將可能的碼相位和載波頻率搜索范圍分成若干分格，一個碼相位分格與一個載波頻率分格構成一個搜索單元.搜索控制邏輯采用某種策略遍歷各搜索單元，檢測信號是否存在，并給出碼相位和載波頻率的粗略估計［2-7］.搜索策略可以是串行的也可以是并行的.

在檢測某個搜索單元時，一般采用門限判決法進行檢測［8-9］，檢測量可使用輸入信號與本地復現(xiàn)信號相關結果的功率值，若檢測量高于門限，則認為信號存在，該搜索單元對應的值就是碼相位與載波頻率的估計值.

這種單次檢測的虛警概率和檢測概率往往不能滿足要求［9-10］，可以通過增加預檢測積分時間或是增加非相干累加次數(shù)的方式來改善檢測性能，但會使計算量和檢測時間都大幅增加.另一種提高檢測性能的方法是采用多次滯留的檢測算法，如M/N檢測算法、(1+M/N)檢測算法以及Tong 檢測算法等［2，8，10］.M/N 算法適用于信號較強的情況，且檢測時間較長，(1+M/N)算法是單次檢測與M/N檢測的結合體，也只適用于強信號情況［8］.Tong算法是一種可變滯留次數(shù)檢測算法，其結構簡單靈活，可以通過調整參數(shù)適應各種環(huán)境下的信號檢測.國內外學者對Tong算法已進行了比較多的研究［5-6，9-15］，這些研究討論了 Tong算法的虛警概率、檢測概率和噪聲單元平均滯留次數(shù)等性質，但對檢測信號單元的平均滯留次數(shù)卻少有研究.實際上，在并行搜索過程中，信號單元滯留次數(shù)對總捕獲時間將有比較重要的影響，同時也會影響到最大滯留次數(shù)等算法參數(shù)的選擇，對它的研究將有助于合理設置算法參數(shù)，提高檢測性能.本文將對信號單元滯留次數(shù)的均值和方差進行詳細推導，給出最大滯留次數(shù)限定方法，分析算法參數(shù)對檢測性能的影響，并給出參數(shù)設置方法.本文以 GPS(Global Positioning System)C/A(Coarse/Acquisition)碼信號為例進行討論，所得結論也可適用于北斗二號系統(tǒng)公開服務信號.

1 Tong檢測算法結構

Tong算法結構如圖1所示［2］.該算法設定一個向上/向下計數(shù)器k，最大值為A，初始值為B.若檢測量超過判決門限Vt，則k加1，否則減1，當k=A時捕獲成功，k=0時該搜索單元被否決，進入下一搜索單元進行檢測.為防止k在A與0之間徘徊，可規(guī)定一個最大滯留次數(shù)Nmax，如在某一單元的滯留次數(shù)超過Nmax，則放棄此單元.

圖1 Tong檢測算法結構Fig.1 Structure of Tong detection algorithm

圖1中的檢測量l為功率檢測量，表達式為

式中，Ij，Qj為相關器I路與Q路輸出的預檢測積分結果;M為非相干累加次數(shù).

用H1表示信號存在，H0表示信號不存在.對功率檢測量做歸一化處理:z=l/σ2n.其中，σ2n是I路或Q路預檢測積分結果中噪聲的功率.可以證明［2］，z滿足如式(2)和式(3)所示的卡方分布:

式中，λ =2M·(s/n)=2M·(c/n)·TI，s/n為預檢測信噪比，c/n為預檢測載噪比，TI為預檢測積分時間;Γ(M)=(M－1)!為伽瑪函數(shù).

設歸一化判決門限為NVt，則單次檢測概率Pd和虛警概率Pf分別為

總檢測概率PD與總虛警概率PF與單次檢測概率和單次虛警概率有如下關系［5，12］:

2 滯留次數(shù)的統(tǒng)計特性

2.1 平均滯留次數(shù)

2.1.1 噪聲搜索單元平均滯留次數(shù)

檢測噪聲單元的平均滯留次數(shù)Nn已有明確結論，如式(8)所示［12］.其中，r=(1 － Pf)/Pf.

2.1.2 信號搜索單元平均滯留次數(shù)

以下來推導檢測信號單元時滯留次數(shù)的平均值.假定檢測正在信號單元中進行，第n次判決時，計數(shù)器值k=i，或記為k(n)=i，下一次判決時計數(shù)器的值只能加1或減1，加1的概率為減1的概率為

假定計數(shù)器從到達i后到結束對此單元的檢測的滯留次數(shù)為 X(i)，其均值為 Ns(i)=暫時忽略最大滯留次數(shù)的制約(事實上，通過合理設置Nmax可以使滯留次數(shù)超過Nmax的概率極小，而且考慮Nmax制約時，難以得到閉式解).這時，結束檢測主要分為兩種情況:一是計數(shù)器到達A，信號捕獲成功;二是計數(shù)器到達0，發(fā)生漏檢.

在第1種情況下，X(i)的最小可能取值為A－i，即每次判決后計數(shù)器的值均加1，一直到達A.則Ns(i)可表示為

則由全概率公式可得

由于X(i－1)的最小值為A－i+1，因此有

故而，E1可表示為

用相同方法處理 E2得:E2≈Pd［Ns(i+1)+1］.

由以上推導可得

在第2種情況下，即發(fā)生漏檢時，X(i)的最小值為i，即每次判決計數(shù)器的值均減1，一直到達0.用與上面類似的推導辦法，可得出這時Ns(i)的遞推形式與式(10)一致.

當計數(shù)器到達A時，宣布信號存在，因此沒有滯留，故而Ns(A)=0;當計數(shù)器到達0時，此單元被放棄，發(fā)生漏檢，也沒有滯留，因此Ns(0)=0.如此便得到遞推關系的兩個邊界條件.

綜上所述，可得平均滯留次數(shù)的遞推模型為

令 a=(1 －Pd)/Pd，b=1/Pd，解差分方程得

令i等于計數(shù)器初始值B，并將a與b表達式代入式(12)，可得檢測信號單元的平均滯留次數(shù)為

2.2 信號搜索單元滯留次數(shù)方差

令Ds(i)為計數(shù)器值為i時滯留次數(shù)X(i)的方差，由方差的定義容易得到

此差分方程較復雜，這里不做通解推導.在實際應用中可通過數(shù)值方法求解.

令 Δ(i)=Rs(i)－Rs(i+1)，對式(15)變形可得

式中

可以解得

通過數(shù)值計算可得 Δ(0)的值，進而得到Rs(1)=Rs(0)－Δ(0)= －Δ(0)，再通過式(15)，求得各個Rs(i).令 i=B，由式(14)可得檢測信號單元的滯留次數(shù)方差為

2.3 最大滯留次數(shù)的選擇方法

在下面的分析中將會看到，信號單元的平均滯留次數(shù)往往遠大于噪聲單元的平均滯留次數(shù)，因此最大滯留次數(shù)的選擇以信號單元的情況為準.可依據(jù)3西格瑪原則，取最大滯留次數(shù)為

3 Tong檢測算法性能分析

檢測一般采用涅曼-皮爾遜準則，即恒虛警準則.限定總虛警概率PF后，由式(7)求得單次虛警概率Pf，由式(5)求得門限后，可由式(4)求得單次檢測概率Pd，然后由式(6)求得總檢測概率PD，由式(8)、式(13)分別求得噪聲單元平均滯留次數(shù)Nn和信號單元平均滯留次數(shù)Ns.分析使用GPS C/A碼信號，預檢測積分時間TI=1 ms，非相干累加次數(shù)M=1.限定總虛警概率PF=10－6.

3.1 檢測概率分析

圖2是Tong算法的總檢測概率曲線.可以看出，增加A和B均能使總檢測概率提高，增加B的效果比增加A的效果更明顯.

圖2 Tong算法總檢測概率Fig.2 Total detection probabilities of Tong algorithm

3.2 平均滯留次數(shù)分析

3.2.1 噪聲搜索單元中的平均滯留次數(shù)

表1為不同A與B下，噪聲單元平均滯留次數(shù).可以看出，增加A與B的值均會使噪聲單元的平均滯留次數(shù)增加，增加B的效果更為明顯.

表1 不同A與B下噪聲搜索單元平均滯留次數(shù)Table1 Average dwell times of noise search unit for different A and B

3.2.2 信號搜索單元中的平均滯留次數(shù)

表2與表3為不同A與B下，信號單元的平均滯留次數(shù).其中，表2中的數(shù)據(jù)在預檢測信噪比s/n=6 dB情況下得到，表3中的數(shù)據(jù)在預檢測信噪比s/n=9 dB情況下得到.

表2 不同A與B下信號搜索單元平均滯留次數(shù)(s/n=6 dB)Table2 Average dwell times of signal search unit for different A and B(s/n=6 dB)

表3 不同A與B下信號搜索單元平均滯留次數(shù)(s/n=9 dB)Table3 Average dwell times of signal search unit for different A and B(s/n=9 dB)

從表2和表3可以看出，信號單元的平均滯留次數(shù)遠大于噪聲單元的平均滯留次數(shù)，增大A會使信號單元的平均滯留次數(shù)增加.

在A一定時，若s/n較低，則B較小時，平均滯留次數(shù)也較小，B較大時，平均滯留次數(shù)也較大.這是由于當s/n較低時，尤其當A也較小時，檢測概率也較低，例如s/n=6 dB，A=4，B=1時，Pd=48.36%，PD=22.60%;A=4，B=2 時，Pd=48.32%，PD=36.02%，這種情況下很容易發(fā)生漏檢，計數(shù)器值減小并到達0的概率較大，此時不同B值下的單次檢測概率較為接近，則B越小，計數(shù)器越容易到達0，平均滯留次數(shù)也越小.隨著A的增大，檢測概率也在增大，計數(shù)器值增加并到達A的可能性變大，但單次檢測概率仍不是很高，中間過程有可能出現(xiàn)反復，例如s/n=6 dB，A=8，B=1 時，Pd=83.99%，PD=80.94%;A=8，B=2 時，Pd=83.78%，PD=96.25%，B 較小時單次檢測概率稍大，因此平均滯留次數(shù)稍小.

在A一定時，若s/n較高，則B較小時，平均滯留次數(shù)較大，B較大時，平均滯留次數(shù)較小.這是由于，若s/n較高，則檢測概率也較高，例如s/n=9 dB 時，A=4，B=1 時，Pd=86.31%，PD=84.19%;A=4，B=2 時，Pd=86.28%，PD=97.48%;A=12，B=1 時，Pd=99.30%，PD=99.29%;A=12，B=2 時，Pd=99.27%，PD=99.99%.這時，計數(shù)器值增加并到達A的概率較大，且不同B值下的單次檢測概率較為接近，則初始位置越接近A，平均滯留次數(shù)越小.隨著A的增加，不同B值下的平均滯留次數(shù)之差趨于定值，即計數(shù)器初始位置之差，例如，B=1和B=2兩種情況下的平均滯留次數(shù)之差隨著A的增加趨于1.

表4是不同A與B值及預檢測信噪比s/n情況下信號單元的平均滯留次數(shù).

表4 不同A，B和s/n下信號搜索單元平均滯留次數(shù)Table4 Average dwell times of signal search unit for different A，B and s/n

由表4可以看出，除了A=4，B=1情況外，其他各種A，B組合情況下的信號單元平均滯留次數(shù)隨著s/n的提高而減小.這是由于隨著s/n的提高，檢測概率將增加，計數(shù)器到達A的可能性增大，中間的反復過程減少，平均滯留次數(shù)隨之下降.另外，由圖2可以看出，隨著s/n的提高，在一定的A，B組合下，總檢測概率增加的趨勢越來越緩慢，單次檢測概率增加的趨勢也將變緩，這造成平均滯留次數(shù)下降趨勢的減緩，逐漸接近成功捕獲所需的最低滯留次數(shù).

對于A=4，B=1的情況，上面已經(jīng)提到，當s/n較低時，漏檢概率較大，例如s/n=6 dB時，Pd=48.36%，PD=22.60%，又由于 B 值較小，因此計數(shù)器很容易到達0，造成平均滯留次數(shù)較小;當s/n有所提高時，檢測概率也會增加，但仍然不很高，例如 s/n=7 dB時，Pd=61.53%，PD=44.24%，這會造成中間過程的反復，致使平均滯留次數(shù)增加;若s/n繼續(xù)增加，則檢測概率迅速增加，例如 s/n=10 dB 時，Pd=94.20%，PD=93.84%，這時，中間反復過程減少，平均滯留次數(shù)降低.

4 算法參數(shù)設置

Tong算法的主要可調參數(shù)是A與B.通過以上分析可知，當信號較強(即s/n較大)時，A和B的值不需要取很大就能滿足檢測概率的需求.對于串行搜索，檢測多數(shù)情況下在噪聲單元中進行，適當增大A、減小B可以在保證檢測概率的前提下，減小噪聲單元中的平均滯留次數(shù)，例如可選A=8，B=1;對于并行搜索，信號單元滯留次數(shù)影響較大，可以適當減小A、增大B，這樣可以在保證檢測概率的前提下，減小信號單元中的平均滯留次數(shù)，縮短捕獲時間，例如可選A=6，B=2.

在信號較為微弱(即s/n較小)的情況下，對串行搜索，可以通過增加A的方法來提高檢測概率，例如，可選A=12，B=1，這樣既能保證檢測性能，又能使噪聲單元的平均滯留次數(shù)不至于過大;對并行搜索，可以通過增加A或B的方法，尤其是增加B的方法來提高檢測概率，可選A=10，B=2或者A=8，B=2，這樣既能保證高檢測概率，又可以使信號單元的平均滯留次數(shù)不至于過大.

總之，參數(shù)的選擇應依據(jù)信號強弱和搜索方式，并且要折衷考慮對檢測概率與平均滯留次數(shù)的影響.

5 結論

1)在涅曼-皮爾遜準則下，增加計數(shù)器上限A和初值B能使Tong檢測算法的總檢測概率提高，增加B的效果尤為明顯.

2)增加A與B的值會使檢測噪聲單元的平均滯留次數(shù)增加，增加B的效果更為明顯.

3)信號單元的平均滯留次數(shù)遠大于噪聲單元的平均滯留次數(shù)，增大A會使信號單元的平均滯留次數(shù)增加.若預檢測信噪比s/n較低，則B較小時，平均滯留次數(shù)也較小，B較大時，平均滯留次數(shù)也較大;若s/n較高，則B較小時，平均滯留次數(shù)較大，B較大時，平均滯留次數(shù)較小.

4)A與B一定時，一般情況下信號單元平均滯留次數(shù)隨著s/n的提高而減小.若A與B均較小，則信號單元平均滯留次數(shù)隨著s/n的提高先增大而后減小.

5)A與B的選擇需依據(jù)信號強弱和搜索方式，并且要折衷考慮對檢測概率與平均滯留次數(shù)的影響.

6)最大滯留次數(shù)可依據(jù)信號單元滯留次數(shù)的均值和方差，采用3西格瑪原則確定.

References)

［1］ 謝剛.GPS原理與接收機設計［M］.北京:電子工業(yè)出版社，2009:349-389.Xie G.Principles of GPS and receiver design［M］.Beijing:Publishing House of Electronics Industry，2009:349-389(in Chinese).

［2］ 寇艷紅.GNSS軟件接收機與信號模擬器系統(tǒng)研究［D］.北京:北京航空航天大學，2006.Kou Y H.The study on GNSS software receiver and signal simulation system［D］.Beijing:Beijing University of Aeronautics and Astronautics，2006(in Chinese).

［3］ 張麗娜.Galileo系統(tǒng)BOC信號處理實驗平臺研究與實現(xiàn)［D］.北京:北京航空航天大學，2007.Zhang L N.BOC signals processing platform in Galileo system design and research［D］.Beijing:Beijing University of Aeronautics and Astronautics，2007(in Chinese).

［4］ 鄧煒.導航衛(wèi)星信號處理算法測試平臺研究與實現(xiàn)［D］.北京:北京航空航天大學，2006.Deng W.Navigation satellite signal process algorithm testing platform design and research［D］.Beijing:Beijing University of Aeronautics and Astronautics，2006(in Chinese).

［5］ Kaplan E D，Hegarty C J.Understanding GPS:principles and applications［M］.2nd ed.Boston:Artech House Inc，2006:223-227.

［6］ Enge P K.The global positioning system:signals，measurements，and performance［J］.International Journal of Wireless Information Networks，1994，1(2):83-105.

［7］ Tusi J B Y.Fundamentals of global positioning system receivers:a software approach［M］.New York:John Wiley ＆ Sons Inc，2000:133-164.

［8］ 孫禮.GPS接收機系統(tǒng)的研究［D］.北京:北京航空航天大學，1998.Sun L.The study on GPS receiver system［D］.Beijing:Beijing University of Aeronautics and Astronautics，1998(in Chinese).

［9］ 姚錚，崔曉偉，陸明泉，等.應用于GPS接收機的序貫檢測器性能分析［J］.清華大學學報:自然科學版，2007，47(7):1166-1169.Yao Z，Cui X W，Lu M Q，et al.Performance analysis of sequential detector for GPS receivers［J］.Journal of Tsinghua University:Science and Technology，2007，47(7):1166-1169(in Chinese).

［10］ 馬琳，崔嵬，吳嗣亮.極低信噪比環(huán)境下含近鄰約束的改進唐檢測判決算法［J］.系統(tǒng)工程與電子技術，2011，33(8):1745-1749.Ma L，Cui W，Wu S L.Improved Tong multiple trial algorithm with near neighbor constraint in extremely low SNR condition［J］.Systems Engineering and Electronics，2011，33(8):1745-1749(in Chinese).

［11］ Tong P S.A suboptimum synchronization procedure for pseudo noise communication systems［C］//IEEE 1973 National Telecommunications Conference Vol.II.Piscataway，NJ:IEEE Press，1973:26D1-26D5.

［12］ 李思超，葉甜春，徐建華.唐檢測器的駐留時間及檢測性能分析［J］.電子測量技術，2009，34(3):53-55.Li S C，Ye T C，Xu J H.Analysis on resident time and detection performance of Tong detector［J］.Electronic Measurement Technology，2009，34(3):53-55(in Chinese).

［13］ Daffara F，Vinson P.Improved search algorithm for fast acquisition in a DSP-based GPS receiver［C］//Proceeding of ISSSE 98.Piscataway，NJ:IEEE Press，1998:310-314.

［14］ 孫曉峰，劉云飛，王西奪.高動態(tài)條件下Tong檢測技術應用研究［J］.無線電工程，2012，42(4):34-36.Sun X F，Liu Y F，Wang X D.Application research of Tong detection based on high dynamic environment［J］.Radio Engineering，2012，42(4):34-36(in Chinese).

［15］ 馬琳，崔嵬，田靜，等.基于馬爾科夫鏈的含有檢測次數(shù)約束條件的唐檢測器［J］.宇航學報，2011，32(8):1799-1804.Ma L，Cui W，Tian J，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(in Chinese).