基于FFT的高数据率低信噪比下的长码直捕算法

韩航程，刘井龙，梁丹丹，龚巧娴

(北京理工大学 信息与电子学院，北京 100081)



基于FFT的高数据率低信噪比下的长码直捕算法

韩航程，刘井龙，梁丹丹，龚巧娴

(北京理工大学 信息与电子学院，北京 100081)

在伪码测距系统中，高信息速率的长码直扩技术可提高通信性能、改善测距精度，但与此同时弱信号的长码捕获存在巨大挑战. 为此，提出一种基于FFT技术的长码直捕改进算法，主要包括非连续式码相位搜索和并行载波多普勒搜索策略、基于位同步的全比特相干积累算法和基于频率补偿的时频二维约束Tong判决算法. 理论分析和仿真结果均表明，该直捕算法不仅能降低资源消耗、缩短捕获时间、大幅度降低虚警概率，还能消除能量累加时由于比特翻转所带来的影响. 所提出的算法可实现虚警概率低于10-6，检测概率大于99.5%，捕获时间小于5 s的盲捕性能.

长码直捕；高数据率；低信噪比；搜索策略；Tong判决

在全球卫星导航系统(GNSS)中，长码可用于提供精确的定位服务，具备优良的性能. 由于码周期长且时间不确定度大，致使其搜索时间长、计算量大，长码直捕一直是公认的难题. 对采用伪码测距的扩频系统，测距码上调制的数据位信息速率一般比较低，甚至不调制数据位信息. 但在一些特殊的场合为提高通信性能并节省发射功率，测距码上也会调制较高速率的信息位. 然而，对于含有高数据率调制并且测距码为长码的测距系统，捕获弱信号的难度很大.

目前，国内外有关长码直捕技术的研究，可分为两大类. 一类是时域处理算法，即采用大规模并行相关器，其中以STS公司的Y-EXPRESS芯片[1]为代表；另一类是基于FFT技术的频域处理算法，以及由此衍生的改进算法，其中以Chun Yang等的XFAST算法[2]和Jing Peng等的均值法[3]为代表. 在这两类算法中，以频域处理算法较为实用，它在一定程度上能解决缩短捕获时间和降低运算量的难题. 然而，其实际应用要么受限于数据位调制，要么难以适应低信噪比高动态环境. 因而研究低信噪比高数据率下的长码直捕具有重要的意义. 本文即要在上述环境下研究长码快速直捕. 为使本算法具体化，本设计以伪码速率为3.069 M、伪码周期为1 s、信息速率为8 kbit/s、EbN0为4.5 dB、多普勒频移为±120 kHz的BPSK-DSSS信号体制为例进行研究.

在基于FFT的伪码快速捕获算法[4]基础上，提出一种改进的时频二维不确定度搜索策略，能显著降低资源消耗和缩短捕获时间；为解决信号能量累加时因高数据率调制带来的比特翻转问题，提出一种基于位同步的全比特相干积累算法，使检测性能明显提升；判决阶段，本文提出一种基于频域预补偿的时频二维约束Tong检测策略，能极大幅度地降低虚警概率；最后通过计算机仿真，验证了算法的有效性.

1 基于FFT的长码直捕搜索策略

基于FFT伪码捕获算法[4]能对码相位并行搜索，其利用圆周相关原理，能完成某一频点下码相位并行搜索，再通过频点切换，实现所有频点串行搜索. 考虑长码捕获搜索时间不确定度大，本文采用基于FFT的伪码捕获方式. 但在长码直捕中，该算法有3个缺点:① 由于每次积分清除时间内取出的本地伪码序列不再是周期序列，该序列相关不再是圆周相关，故不能直接利用基于FFT的传统捕获算法；② 在对某一基带数据段搜索伪码相位时，单次检测的驻留时间Twait往往大于该数据段的持续时间Tdata. 为降低Twait，需消耗大量资源做并行运算；③ 该算法利用FFT变换频移性质实现多普勒频点搜索，是串行搜索方式，限制了捕获速度.

针对问题(1)，采用双倍零扩展算法[5](doubleblockzeropadding, DBZP)即可解决. 基本思路是对接收信号每次连续取2N(N=2k，k为正整数)个点组成接收数据块，而相邻两次取的数据重合N个点；对本地伪码每次连续取N个点并在其后补N个0组成本地伪码块，再利用FFT技术将这两个数据块做快速相关，取结果的前N个点处理.

针对问题(2)，本文提出非连续式码相位搜索策略. 例如，Twait=5 ms，Tdata=1 ms，Twait/Tdata=q，单次检测时每隔Twait时间取一段基带信号捕获，相邻两次检测之间本地伪码做相应步进，则经过q轮搜索即可完成对整个时域不确定度的搜索，如图1所示. 该策略最坏情况下时域不确定度搜索总次数及总时间与连续式相位搜索相当，但硬件资源消耗规模降低至原来的1/q.

针对问题(3)，本文引入频点部分并行搜索策略. 如图1，将要搜的多普勒分成1～L段，各频段之间并行搜索，频段内串行搜索. 在搜索频域不确定度时，循环移位后若每个多普勒频段用1个FFT核做IFFT操作，则Twait较多普勒频点串行搜索方式降低1/L，若采用非连续式相位搜索，捕获时间将缩短至少L倍. 该策略兼顾了资源消耗和捕获时间.

图2给出了改进后的长码直捕原理框图. 改进之后的长码直捕算法在资源、时间、性能三者之间可联合优化，属于一个多目标的线性优化问题. 相比传统算法，硬件资源消耗可降低q倍，捕获时间能缩短L倍.

2 高数据率低信噪比下的长码直捕算法

以上的讨论虽能解决长码直捕的捕获时间和资源消耗的问题，但并没涉及到提供高数据率低信噪比下的长码直捕的检测性能问题. 针对低信噪比问题，捕获的基本思想是在低信噪比下对信号做长时间的积累以提高检测信噪比[6]；针对高数据率调制的伪码测距信号，捕获的基本思想是做相关时消除数据位翻转对相关值的影响[7].

2.1 基于位同步的全比特相干积累算法

要确保低信噪比和高数据率条件下的检测性能，必须将多个比特能量累加在一起. 相干累加、非相干累加和差分相干累加是常用的累加方式. 文献[8]表明相干累加和差分累加都受限于数据位调制，而非相干累加不受此影响.

对相干积累的结果取模平方后再累加即为非相干累加. 设n为累加次数，Gx(n)为相干积累增益，Gf(n)为非相干累加增益，则有

(1)

(2)

式中L(n)是平方损耗[9]，其值为

(3)

其中理想检测能力因子

erfc-1(x)为逆函数，Pfa为虚警概率，Pd为检测概率.

若Pfa=10-6，Pd=99%，Gf、Gx及L(n)与n的关系如图3所示.

由图3知，Gx(n)和L(n)与n均成正相关，这表明：在总预检测时间固定时，为了获得最大的总累加增益，Gx(n)要尽可能地大，L(n)要尽可能地少，即单次相干积累时间Tcoh越长越好，非相干累加次数M越小越好. 因此，可从以下两方面对累加算法进行优化.

首先，Tcoh需尽量长. 在本设计中，Tcoh最长可达一个比特时间Tb，即0.125 ms，但此时需进一步考虑比特翻转的影响. 如图4所示，假设某段接收信号中第1～4 byte所含的伪码分别是码段A、B、C和D，若用本地伪码方式1中的0.125 ms伪码与0.25 ms接收信号相关，必定会将接收信号中两个比特能量叠加在一起，且存在比特翻转. 为解决该问题，本文采用本地伪码方式2中的0.125 ms伪码与接收信号相关，即本地PN码段的起点和终点每次都刚好对应任意比特位的起点和终点. 在实际工程中，利用长码特点，通过控制接收机复制的本地伪码序列码表就能简单地实现这种精确位同步.

其次，在总累加时间能满足检测性能需要的前提下，为了缩短捕获时间、降低工程复杂度、降低平方损耗，均需使M尽量小.M的参考值可通过公式推导得到，也可通过仿真得到.

综上，基于位同步的全比特相干积累算法，不但能有效解决比特翻转问题，而且最大化增加相干积累时间，提高接收机灵敏度.

2.2 基于频率补偿的时频二维约束Tong判决

Tong判决属可变驻留时间判决，在低信噪比下相比M/N检测算法具有更好的检测性能和更快的检测速度[10]，因而得到广泛应用. 它先给计数器设置一个初值B，当检波器输出大于门限，计数器加1，否则减1. 若计数器达到门限B，则判决捕获成功；若计数器减为0，则判决捕获失败. Tong判决算法原理如图5所示. 通过仿真发现，对于弱信号中的长码直捕，若直接利用图5中的传统算法，要达到预定的PD和PFA，不仅计算量大，且信号处理时间也长，不利于实时信号处理，因此需要对判决模块做进一步优化.

(4)

当fe降到±0.125Tcoh时，则功率衰减降为-0.224 dB. 要实现这一目的，只需将基带信号乘以复信号exp(j2πfit)进行单频率补偿，即可完成，其中fi为补偿的多普勒. 文献[12]提出如果在Tong检测算法中引入近邻约束条件，即将相邻单次检测中捕获的伪码相位估计值之差限定在一定范围内，作为计数器K加减约束条件，可大幅度降低PFA. 受此启发，并考虑到频率补偿时具有多个补偿点，可将这多个补偿点看成不同的频率检验通道，于是可将单纯的一维相位约束转为既约束码相位又约束多普勒频移的时频二维约束.

图6给出了改进后的Tong判决原理图. 在Tong判决中，经过频率补偿后，若要增加计数器K，不仅要求信号功率大于噪声门限，且要求相邻单次检测对应的频率补偿点和伪码相位估计值都满足约束条件才可.

改进后的Tong判决，整体性能比传统的Tong判决算法有明显提升，尤其是虚警概率得到极大地降低，而且利于实时信号的处理.

3 理论分析

3.1 检测概率和虚警概率

接收机的中频数字信号可以表示为

(5)

式中:A为接收信号幅度；P(t)为伪码序列；Ts为采样间隔；fIF为载波中频频率；fd为载波多普勒频率；η=fd/Rf为码多普勒归一化系数；Rf为射频载波频率；τ为伪码延时；φ0为载波初始相位；v(t)为输入窄带高斯噪声.

(6)

(7)

相参积累后，接着进行M次非相干积累. 则平方检波器输出为

(8)

捕获的过程可看成二元假设检验问题，通过比较检波器输出值和噪声门限之间大小关系来判断哪一个假设成立.

在H0纯噪声假设下，Z(k)服从自由度为2M的Γ分布. 令方差σ0=var [I(i)]=var [Q(i)]，则概率密度函数为

(9)

σ1=var [I(i)]=var [Q(i)]，

则概率密度函数为

(10)

式中IM-1(x)为第一类M-1阶修正贝塞尔函数.

假设接收机的门限为Vth，则可得到信号的单次检测概率Pd和单次虚警概率Pfa为

(11)

(12)

单次检测到信号后进入判决阶段，若用Tong检测器，则总检测概率为

(13)

总虚警概率为

(14)

平均驻留次数为

(15)

式中：B为初值；A为上行门限[13].

3.2 捕获时间

设时域不确定度Tsea含有Kt个搜索单元，频域不确定度Fsea含有Kf个搜索单元，在最坏情况下完成全部二维搜索的时间Tcap为

(16)

Tcell也即每个网格的驻留时间，非相干累加串行实现有利于最大限度共用FFT核，此时有

(17)

式中:Twcell为搜索每个网格时不做非相干累加的驻留时间;Ttong为唐判决的平均驻留时间;Pfa为式(11)的值;M为非相干累加次数.

在本设计中，每次能搜索的时域不确定度为Tstep，每次能搜索的多普勒不确定度为fstep，设频域分段数为L，则有

(18)

(19)

将式(17)～(19)代入式(16)得

(20)

4 仿真与验证

为验证本文算法性能，采用Matlab进行蒙特卡洛仿真，仿真的基本参数如表1所示.

表1 仿真参数设置

4.1 长码直捕搜索策略性能分析验证

若利用本文提出的搜索策略，不失一般性，令M=L，对式(20)，按表1参数可得，Tsea=1 s，Fsea=240 kHz，Tstep=0.125 ms，Fstep=4 kHz. 若FPGA的信号处理时钟为200 MHz，则Twcell=2 048/(2×108)，由式(20)可得，Tcap=4.92 s.

现改用基于连续式相位搜索和多普勒频移不分段搜索的传统搜索策略进行对比. 当Tdata=0.125 ms，非相干累加全并行实现时，Twait≈62×2 048÷(2×106)=0.63,ms，若要达到相同的Tcap，须利用并行处理方式解决Twait和Tdata的矛盾，这意味着：相对于本文提出的新算法，其资源消耗将会提高q=Tdata/Twait≈5倍. 值得一提的是，若非相干累加串行实现，其q值将更大.

4.2 基于位同步的全比特相干积累性能仿真

在基于位同步的全比特相干积累算法基础上进行仿真验证，并以最大相关峰的位置是否对应预设频偏和码偏为捕获标志. 当累加次数M分别为13、19、25的仿真结果分别如图7(a)、7(b)和7(c)所示. 可见，当累加次数达25时才有较可靠的相关峰.

在此基础上，统计非相干累加次数与检测概率的关系，结果如图8所示. 由图可知，当M=25时，检测概率的理论值和仿真值均达到99.7%. 当其余条件相同时，将基于位同步的全比特积累法与基于位同步半比特积累法的仿真值进行比较，结果如图9所示. 由图9可知，若同样达到检测概率为99.7%的性能，基于位同步的半比特积累法至少需要满足M=59. 这说明基于位同步的全比特积累法具有较高的累加增益，能明显提高检测概率.

4.3 改进的Tong判决器性能仿真

仿真参数如表1所示，当M=25时，将两种不同的Tong检测算法进行对比，仿真结果如表2所示. 表2中平均驻留次数Cs为计数器K从初值B开始，到达A或0时停止的平均次数. 需特别指出，表中虚警概率为0是指受仿真条件限制，在106次仿真中未发现有虚警存在，并非虚警概率真的为0.

表2 传统Tong算法与改进Tong算法性能对比

Tab.2 Performance comparison of traditional and new Tong detecting methods

峰均比门限20212325计数器B=1A=5B=1A=4B=1A=4B=1A=3算法目标+噪声纯噪声PDCsPFACs传统Tong999%5211×10-225改进Tong999%5614×10-518标准Tong996%5375×10-414改进Tong998%58012传统Tong975%4211×10-610改进Tong978%49010传统Tong941%2141×10-610改进Tong947%31010

由表2可看出，在相同条件下，相比于传统Tong算法，在时频二维约束作用下，PFA值急剧降低，而平均驻留时间却变化不大；改进Tong算法的PD有所提升，这是因为引入频率补偿改善了Sinc函数衰落的影响；此外，在PFA满足指标的前提下，通过降低单次检测门限，不仅能提高PD值，还能捕到更微弱的信号，提高接收机灵敏度.

5 结束语

针对高数据率低信噪比下的长码直捕问题，本文以降低资源消耗、缩短捕获时间、提高检测概率及降低虚警概率为目标，从长码直捕中的多普勒频移和码不确定度的搜索策略、信号相关和捕获判决3个方面分别做了研究，最后通过理论分析和仿真验证了文中算法的有效性.

[1] Pickholtz R L， Schiling D L, Milstein L B. Theory of spread-spectrum communication-a tutorial[J]. IEEE Transaction on communications, 1982,30(5):855-884.

[2] Yang C，Vasquez J，Chaffee J. Fast direct P(Y)-code acquisition using XFAST[C]∥Proc of ION GPS. Ten-nessee: the ION Publication Department. Nashville, USA: 20N, 1999:317-324.

[3] Pang J. Direct global positioning system P-code acquisition field program mable gate array prototyping[D]. Ohio， USA: College of Engineering and Technology, Ohio University， 2003.

[4] Van Nee D J R， Coenen A J R M. New fast GPS code-acquisition technique using FFT[J]. Electronics Letters， 1991，27(2):158-160.

[5] Ziedan N I， Garrison J L. Unaided acquisition of weak GPS signals using circular correlation or double-block zero padding[C]∥Proceedings of IEEE-PLANS 2004. Monterey， CA: [s.n.], 2004:26-29.

[6] Chansarkar M M， Garin L， Acquisition of GPS signals at very low signal to noise ratio[C]∥Proceedings of the 2000 National Technical Meeting of the Institite of Navigation， Anaheim， CA: [s.n.], 2000:26-28.

[7] 赵春燕，崔嵬.一种可克服非相干数据调制影响的直扩信号捕获算法[J].电子学报，2011，39(7):1491-1496.

Zhao Chunyan， Cui Wei. A kind of DSSS signal acquisition algorithm that can overcome the influence of non-coherent modulation[J]. Journal of Electronic， 2011，39(7):1491-1496. (in Chinese)

[8] Shanmugaml S K, John Robert, Watson Nielsen, et al. Differential signal processing for enhanced GPS acquisition[C]∥Proceedings of ION GNSS 2005. Long Beach: [s.n.], 2005:212-222.

[9] James B. Fundamentals of global positioning system receivers a software approach[M]. New Jersey: Wiley-Interscience， 2005.

[10] Kaplan E D，Hegarty C. Understanding GPS: principles and application[M]. 2nd ed. Boston: Artech House Publishers， 2006.

[11] 谢钢.GPS原理与接收机设计[M].北京：电子工业出版社，2009:289-291.

Xie Gang. The method of GPS and the design of GPS receivers[M]. Beijing: Electronic Industry Press， 2009:289-291. (in Chinese)

[12] 马琳，崔嵬，吴嗣亮.极低信噪比环境下含近邻约束的改进唐检测判决算法[J].系统工程与电子技术，2011，33(8)：1745-1749.

Ma Lin， Cui Wei， Wu Siliang. A improved tong detecting and judging algorithm with neighbor constraints under very low SNR situations[J]. Systems Engineering and Electronics， 2011，33(8)：1745-1749. (in Chinese)

[13] Kaplan E D，Hegarty C. Understanding GPS: principles andapplication[M]. 2nd ed. Boston: Artech House Publishers， 2006:166-170.

(责任编辑：刘芳)

Long Code Direct Acquisition Algorithm of DSSS Signals Based on FFT in High Rate and Low SNR Condition

HAN Hang-cheng, LIU Jing-long, LIANG Dan-dan, GONG Qiao-qian

(School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China)

In pseudo-code ranging systems, the high rate and long code direct sequence spread spectrum (DSSS) can improve not only the communication performance but also the ranging accuracy. However, long code DSSS acquisition of weak signals is still faced with lots of challenges. Hence, an improved DSSS acquisition algorithm based on FFT was proposed，including the discontinuous search of code phase and parallel search of Doppler, the whole-bit coherent accumulation based on bit synchronization and the Tong judgment based on the frequency compensation of the time-frequency two-dimensional constraint. Both theoretical analysis and simulation results show that the proposed algorithm can substantially reduce the resource consumption and the probability of false alarm, shorten the acquisition time and eliminate the effects of data modulation under conditions of long time accumulation. In this paper such performance can be realized that the false alarm probability is less than 10-6, the detecting probability is over 99.5% and the acquisition time is less than 5 s.

direct acquisition of longcode; high datarate; low SNR; searching strategies; Tong detector

2014-06-11

国家自然科学基金资助项目(61301089)

韩航程(1985—)，男,博士，讲师，E-mail:hanhangcheng@bit.edu.cn.

TN 967

A

1001-0645(2016)09-0976-07

10.15918/j.tbit1001-0645.2016.09.018