双门限唐检测改进算法

张超逸,李金海,阎跃鹏

(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.