Tong檢測算法性能分析及參數設置

朱云龍，丑武勝，楊東凱

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

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

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

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

1 Tong檢測算法結構

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

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

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

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

用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)!為伽瑪函數.

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

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

2 滯留次數的統計特性

2.1 平均滯留次數

2.1.1 噪聲搜索單元平均滯留次數

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

2.1.2 信號搜索單元平均滯留次數

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

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

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

則由全概率公式可得

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

故而，E1可表示為

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

由以上推導可得

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

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

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

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

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

2.2 信號搜索單元滯留次數方差

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

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

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

式中

可以解得

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

2.3 最大滯留次數的選擇方法

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

3 Tong檢測算法性能分析

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

3.2.1 噪聲搜索單元中的平均滯留次數

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

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

3.2.2 信號搜索單元中的平均滯留次數

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

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

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

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

在A一定時，若s/n較低，則B較小時，平均滯留次數也較小，B較大時，平均滯留次數也較大.這是由于當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%，這種情況下很容易發生漏檢，計數器值減小并到達0的概率較大，此時不同B值下的單次檢測概率較為接近，則B越小，計數器越容易到達0，平均滯留次數也越小.隨著A的增大，檢測概率也在增大，計數器值增加并到達A的可能性變大，但單次檢測概率仍不是很高，中間過程有可能出現反復，例如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 較小時單次檢測概率稍大，因此平均滯留次數稍小.

在A一定時，若s/n較高，則B較小時，平均滯留次數較大，B較大時，平均滯留次數較小.這是由于，若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%.這時，計數器值增加并到達A的概率較大，且不同B值下的單次檢測概率較為接近，則初始位置越接近A，平均滯留次數越小.隨著A的增加，不同B值下的平均滯留次數之差趨于定值，即計數器初始位置之差，例如，B=1和B=2兩種情況下的平均滯留次數之差隨著A的增加趨于1.

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

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

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

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

4 算法參數設置

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

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

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

5 結論

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

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

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

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

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

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

References)

［1］ 謝剛.GPS原理與接收機設計［M］.北京:電子工業出版社，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軟件接收機與信號模擬器系統研究［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系統BOC信號處理實驗平臺研究與實現［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］ 鄧煒.導航衛星信號處理算法測試平臺研究與實現［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接收機系統的研究［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］ 馬琳，崔嵬，吳嗣亮.極低信噪比環境下含近鄰約束的改進唐檢測判決算法［J］.系統工程與電子技術，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］ 孫曉峰，劉云飛，王西奪.高動態條件下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］ 馬琳，崔嵬，田靜，等.基于馬爾科夫鏈的含有檢測次數約束條件的唐檢測器［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).