高动态卫星DSSS 信号Turbo 迭代捕获算法

姜春晓，王佳蔚

（1.清华大学国家信息与科学技术研究中心，北京 100084；2.清华大学宇航中心，北京 100084；3.清华大学电子工程系，北京 100084）

1 引言

卫星通信可以在全球范围内为地面终端提供多样化服务，在很多领域中都发挥着重要的作用[1-4]。随着高机动终端的发展和普及，高动态通信受到国内外学者的广泛研究[5-9]，但关于卫星高动态通信的研究仍相对缺乏。与地面移动通信不同，直接序列扩频（DSSS,direct sequence spread spectrum）技术被广泛应用于卫星通信以提高抗干扰性能[10]。一般而言，DSSS 信号的捕获是卫星高动态通信系统重要的组成部分，只有正确估计出接收信号的扩频码相位才能获取扩频增益。但是传统的DSSS 方法难以应用在高动态卫星通信中。

一方面，为了确保移动终端具有较高的抗干扰性能，扩频序列一般较长，这将增加捕获的复杂度和捕获时间。另一方面，终端的高机动特性会引起大多普勒频偏和大多普勒变化率，由于时变多普勒频偏和多普勒变化率难以估计和补偿，这将导致DSSS 信号的捕获成为瓶颈。考虑到扩频序列较长，传统的逐频偏、逐相位的遍历搜索算法的复杂度在卫星高动态通信中是不可接受的。因此，十分有必要地为高动态卫星通信系统设计专门的、具有较低复杂度的捕获方法。

尽管过去有很多捕获算法被提出，但是大多数传统的DSSS 信号捕获算法难以应对高动态通信环境的挑战。文献[11-12]提出了基于相关累加的串行搜索捕获算法，通过遍历搜索相关的方法获取各个码字相位的相关峰，根据峰值门限来判断是否捕获成功。但这种方法难以应用到高动态卫星通信中，因为时变多普勒频频偏和长扩频序列会显著增加计算复杂度。文献[13-14]和文献[15]分别提出了并行捕获算法和基于快速傅里叶变换（FFT,fast Fourier transform）的捕获算法，但复杂度较大。另外，这些算法将多普勒频偏视为常数，没有考虑多普勒的时变特性。相似地，文献[16-17]提出了二维压缩相关捕获算法，在第一次搜索中对一系列相邻的码字相位和多普勒频偏测试点的组合进行遍历搜索，从而搜索到可能的码字相位和频偏值；在第二次搜索中使用相关器对第一次搜索中的组合进行逐一检测判决。这种方法能够有效降低计算复杂度，但是忽略了时变多普勒频偏的影响。与前面所述方法不同，文献[18]提出了基于m 序列约束关系的快速捕获算法。该算法具有较低的复杂度，但没有考虑多普勒频偏的影响，难以应用在高动态通信中。文献[19]提出了基于遗传算法的伪随机（PN,pseudo noise）序列捕获算法，用于全球导航卫星系统（GNSS,global navigation satellite system），可以有效降低捕获时间，但是无法应对高动态通信环境的挑战。同时，文献[20]提出了多普勒补偿估计算法来补偿接收信号中的多普勒频偏，但频偏的估计和补偿范围较小，难以支持高动态卫星通信。文献[21]使用反馈放大器和限制器实现了m 序列的可靠捕获。该算法适用于长扩频序列的捕获，但未考虑多普勒效应的影响。综上分析，大多数捕获算法都未将时变多普勒频偏和多普勒变化率的影响以及计算复杂度考虑在内，导致其无法应用于高动态卫星通信系统中。

通过以上分析，现有的捕获算法大致可以分为两类：相关捕获和非相关捕获。相关捕获的捕获性能主要取决于PN 序列的长度，而非相关捕获主要取决于码片间的约束关系。相关捕获算法通常可以在低信噪比（SNR,signal-to-noise ratio）环境中取得更好的性能，但在高动态环境下难以发挥出良好的捕获性能。一方面，时变多普勒频偏和多普勒变化率严重削弱了扩频增益。另一方面，长扩频序列通常导致较高的计算复杂度，难以实际应用在卫星高动态通信中。相比于相关捕获算法，非相关捕获算法有望在高动态卫星通信系统中发挥出更好的性能，因为码片间的约束关系可以被用来减少多普勒效应的不利影响，即可以通过逐码片处理的方式获取编码增益。然而，大多数非相关捕获算法都未考虑时变多普勒频偏和变化率的影响。

为了应对高动态卫星通信的挑战，需要设计适合高动态环境的DSSS 信号捕获算法，以实现高动态环境下长扩频序列的高性能捕获。因此，本文提出了全新的高动态信号因子图结构，其中时变多普勒变化率被建模为随机游走模型。基于所提出的因子图，本文提出了Turbo 迭代捕获算法，该算法由多普勒消除环路和码字判决环路组成，可以有效地克服时变多普勒频偏和变化率的负面影响，在高动态环境下实现更好的捕获性能。

本文主要的研究工作如下。

1) 设计了高动态信号捕获的因子图。在所提因子图中，多普勒变化率被建模为随机游走模型，并利用马尔可夫链来描述时变多普勒变化率。

2) 分析了信号在时变多普勒频偏和变化率影响下的统计特性，根据和积规则，推导了因子图各节点之间所传递的消息。

3) 基于所提因子图结构，提出了Turbo 迭代捕获算法。该算法由多普勒消除环路和码字判决环路组成，通过双环迭代，可以有效消除时变多普勒频偏和多普勒变化率对捕获产生的不利影响。仿真分析表明，所提算法相比于传统算法具有更好的捕获性能和更低的复杂度。

2 系统模型

本文系统中使用的PN 序列是m 序列[22-24]。本质上，m 序列是线性反馈移位寄存器（LFSR,linear feedback shift register ）序列，周期长度为2u1M=-，其中u为反馈寄存器个数。m 序列生成器结构如图1 所示。

根据m 序列生成器结构，输出序列x间的约束关系可以表示为

其中，xn表示在n时刻m 序列生成器的输出，zn表示反馈系数，其值只能取0 或1。因此，m 序列的生成多项式可以表示为

其中，D表示单位延迟算子。当寄存器的初始值不全为0 时，m 序列可达最大周期长度为M=2u-1。另外，根据码片间的约束关系，校验矩阵可以表示为

因此，m 序列的约束关系可以被表示为

其中，T 表示转置操作。

在发送端，PN 序列经过二进制相移键控（BPSK,binary phase shift keying）调制后，被添加多普勒频偏、多普勒变化率和加性白高斯噪声（AWGN,additive white Gaussian noise）。一般而言，在大多数场景下，只有部分PN 序列可被观测到[18]，记为x=(x1,x2,…,xN)。观测序列的长度远大于寄存器的个数，但远小于m 序列周期数，即u≪N≪M。

当卫星在视线范围内时，接收信号可以表示为

其中，c(n)=(-1)x(n)，v(t)表示终端的运动速度，θ(t)表示移动方向与信号入射方向的夹角，N表示观测序列的长度，Ec表示每个码片的能量，Ts表示每个码片的持续时间，w(t)表示均值为0、方差为的高斯白噪声，fd(t)和fc分别表示时变多普勒频偏和载波频率。

假设接收机的下变频是理想的，接收滤波器采样输出可以表示为

其中，f0表示初始的多普勒频偏，ad(n) 表示时变多普勒变化率，且。

在这种情况下，时变多普勒变化率被建模为随机游走模型[25-27]，即

本文提出的迭代捕获接收机模型如图2 所示。首先，长度为N的观测序列被选中进行迭代捕获。然后，在消息传递模块中，基于高动态信号的因子图，计算各相邻节点间传递的消息，从而消除高动态环境下多普勒频偏产生的不利影响，进而恢复出传输的扩频序列。最后，通过统计判决的方式来判断是否捕获成功。如果失败，观测窗口将移动到下一位置重复以上迭代捕获的过程。

3 高动态信号的因子图结构

一般来说，因子图可视为Tanner 图的一种延伸[28]。因子图可以通过因子化的方式处理含有多个变量的全局函数，根据因子图结构，采用和积规则可以计算多个由全局函数导出的边缘函数。本节将详细地阐述高动态信号的因子图结构以及节点间的消息传递。

其中，f表示初始的多普勒频偏，a表示时变多普勒变化率。为了简化连续变量积分问题，将连续变量f和a进行离散化表示

其中，fmax和amax分别表示初始多普勒频偏和时变多普勒变化率的最大值。从而，可以被进一步表示为

考虑到实际中初始多普勒频偏是均匀分布的，所以概率密度函数p(f) 可以表示为

根据m 序列的约束关系，p(c) 可以表示为

其中，c=η(x)表示m 序列满足的约束关系，即，I(·) 表示指示函数，记为

由于随机游走模型的马尔可夫性，p(a) 可以表示为

通过以上分析，可以建立高动态信号捕获的因子图结构，如图3 所示。其中，方形节点表示函数节点，圆形节点表示变量节点。根据m 序列的约束关系，发送的扩频序列可以通过和积算法[29-31]恢复出来。本质上，和积算法是一种消息传递算法，可以通过迭代的形式交互因子图中相邻节点的可靠度信息。具体的和积算法的消息传递原理可参考文献[32]。

其中，α是一个常数，N(·)表示因子图中相邻节点的集合，表示与校验节点τm相连的除cn以外的变量节点，表示在第l-1 次迭代中变量节点到校验节点的传递消息，具体计算方法在式(39)中给出。

根据消息的更新准则，从码片节点cn到信道函数节点hn传递的消息是与cn相邻的校验节点τm传递到码片节点cn的消息之和，可以表示为

其中，τi∈N(cn)表示与码片节点cn相邻的校验节点。根据LLR 消息的定义，满足分别定义为在第l次迭代中，由码片节点到信道函数节点传递的关于

根据和积算法，由信道函数节点hn到变量节点f传递的消息为

相似地，由信道函数节点hn到变量节点an传递的消息为

因此，由变量节点f到信道函数节点传递的消息可以表示为

再次使用和积规则，可以推得变量节点an到函数节点gn传递的消息为

相似地，由变量节点an到函数节点gn-1的消息更新表达式为

在多普勒变化率估计环路中，函数节点gn到变量节点an传递的消息可以表示为

相似地，函数节点gn到变量节点an1+传递的消息可以表示为

根据消息传递准则，由变量节点an到信道函数节点hn传递的消息为之积，表示为

完成多普勒频偏消除子环路和多普勒变化率消除子环路的信息传递后，借助于，由函数节点hn到码片节点cn传递的消息可以表示为

转化为LLR 消息的形式为

最后，由变量节点cn到校验节点τm的消息为

通过以上分析，本文建立了高动态信号捕获的因子图框架，并推导了各节点间传递的信息。

4 Turbo 迭代捕获算法

为了在高动态环境下实现对接收信号的快速捕获，基于设计高动态信号的因子图，本文提出了Turbo 迭代捕获算法，该算法包括消息传递和统计判决两部分。特别地，消息传递过程由2 个环路组成，即码片判决环路和多普勒消除环路。因子图是消息传递算法的直观体现，基于高动态因子图结构设计的消息传递算法，可以有效地消除高动态环境下多普勒频偏对捕获产生的不利影响。本节将详细介绍Turbo 迭代捕获算法。

4.1 消息传递

消息传递算法的结构如图4 所示。通过多普勒消除环路和码字判决环路间的信息迭代传递，来消除时变多普勒频偏和多普勒变化率的影响。

本质上看，m 序列其实也是一种信道编码，存在码片间的约束关系。根据Turbo 迭代原理[33]，m序列的约束关系可以用来对接收序列中的错误码片进行修正，并将经修复后准确性更高的修正值用于多普勒的估计和修正，而多普勒的修正结果又可以在下轮迭代中提高码片判决的准确性，进而通过这样的联合迭代有效提高捕获概率。在消息传递算法中，多普勒消除环路能够向码字判决环路提供关于多普勒频偏和多普勒变化率的可靠度信息，从而使码字判决结果更加可靠；反过来，可靠的码字判决结果将有利于多普勒频偏和多普勒变化率的估计。通过2 个环路信息的交互迭代能够提升PN 序列的捕获性能。

在该算法中，Turbo 迭代从多普勒消除环路开始，首先进行Id次多普勒消除环路的迭代，然后执行Ic次码字判决环路的迭代。为了进一步降低复杂度，中最大的Qs和Ds个值被选中进行之后的迭代，其他多普勒频偏和多普勒变化率值不参与后续的迭代。

4.2 统计判决

根据和积规则，码片节点的置信度可以表示为

因此，在第l次迭代中的扩频序列估计值为

通过以上分析，Turbo 迭代捕获算法如算法1所示。

算法1Turbo 迭代捕获算法

5 仿真分析

本节通过MATLAB 进行仿真，来验证本文算法的优越性。本文考虑的高动态终端的最大运动速度为20 马赫（6 800 m/s），产生的最大多普勒频偏为50 kHz，最大多普勒变化率为15 kHz/s，符号速率为125 kHz。捕获验证阶段的频率搜索精度为0.05 kHz，相位搜索精度为一个码片长度。另外，一些传统的算法，如并行频率搜索（PFS,parallel frequency search）算法[35]、部分匹配滤波-快速傅里叶变换（PMF-FFT,partially matched filtering-fast Fourier transform）算法[36-37]、递归软序列估计（RSSE,recursive soft sequence estimation）算法[18,38-39]，被用来与本文算法比较，来证明本文算法在捕获性能和计算复杂度上的优势。仿真中采用捕获概率来评价算法的捕获性能，一些必要的参数如表1所示。

表1 系统参数

5.1 捕获性能

图6 给出了本文算法在不同多普勒频偏条件下的捕获性能，其中，多普勒变化率，随机游走方差，Pa表示捕获概率。从图6 中可以看出，本文算法可以在不同频偏下达到相似的捕获性能，因为初始多普勒频偏是均匀分布的，可以在多普勒消除环路中进行统一的补偿消除，从而在不同的初始多普勒频偏下达到了相似的性能。

图7 给出了本文算法在不同多普勒变化率条件下的捕获性能，其中，多普勒频偏f0=10 kHz，随机游走方差。从图7 中可以看出，随着多普勒变化率的增加，捕获性能逐渐下降，这是由于多普勒变化率变化太快难以跟踪补偿导致的。

图8 给出了本文算法在不同随机游走方差条件下的捕获性能，其中，多普勒频偏f0=0，初始多普勒变化率a1=0。从图8 中可以看出，捕获性能随游走方差的增加而降低。因为随着游走方差的增加，多普勒变化率变化更快，多普勒消除环路难以跟踪补偿，所以会残留多普勒频率残差使性能下降。

通过以上分析可知，本文算法的性能主要取决于多普勒频偏、多普勒变化率、随机游走方差，同时高动态特性也由这3 个参量决定。随着高动态特性的增加，捕获性能会逐渐降低。

5.2 性能对比

图9 给出了本文算法与PFS 算法、PMF-FFT算法和 RSSE 算法的捕获性能比较，其中，。从图9 中可以看出，本文算法相比于PFS 算法在捕获性能上有1.3 dB 的提升、相比于PFM-FFT 算法有3.1 dB的提升，验证了本文算法捕获性能的优越性。对于PMF-FFT 算法，高动态环境下的时变多普勒频偏会削弱部分相关器的输出，导致FFT 之后的峰值降低，使捕获性能下降。对于PFS 算法，由于多普勒频偏点的补偿是提前预设的，因此难以用有限的多普勒频偏测试点补偿时变多普勒频偏。RSSE 算法可以通过码片间的约束关系恢复扩频序列，但高动态环境会提高码片的误判概率，因此捕获性能在高动态环境下有明显损失。

本文算法的捕获性能增益主要来源于两点。1) 通过基于随机游走模型的因子图实现了对时变多普勒频偏、多普勒变化率逐码片的精细补偿，更好地消除了时变多普勒效应带来的影响。2) 本文将传统的PN序列捕获问题转化为了序列估计问题，利用了m 序列各个码片间的约束关系，获取了编码增益。因此相较于传统算法，本文算法提升了捕获性能。

5.3 计算复杂度分析

本文算法的复杂度主要通过加法次数、乘法次数和查找表次数进行评价，计算过程中的指数和对数运算均通过查找表获得。在码字判决环路中，需要12IcNlmax次加法运算。在多普勒消除环路中，需要(4D+2Q)IdNlmax+2DQN次加法运算、(7D+2Q)IdNlmax+4DQN次乘法运算和2DQN次查找表运算。在两环路之间进行消息传递时，需要2DQNlmax次加法运算、2DQNlmax次乘法运算和Nlmax次查找表运算。通过以上分析可知，本文算法总共需要大约[(4D+2Q)Id+2DQ+12Ic]Nlmax+2DQN次加法运算、[(7D+2Q)Id+2DQ]Nlmax+4DQN次乘法运算和2DQN+Nlmax次查找表运算。特别地，当l≥ 2时，Sf和Sa中分别只有Qs和Ds个数值参与后续的迭代，因此复杂度计算式中的变量Q和D可以分别被Qs和Ds近似取代。另外，在相同条件下，其他算法的计算复杂度如表2 所示。

表2 各算法的计算复杂度

为了方便与其他算法比较，类似于文献[40]，不再区分加法、乘法次数，而是将其统一用浮点运算次数（FLOP,floating-point operation）表示。比较可得，本文算法的计算量约是PFS 算法的1/5。实际运算中大约需要7.03×108次乘法运算和6.59×108次加法运算，时间复杂度为O(N)。

6 结束语

本文对高动态信号的捕获进行了研究。基于DSSS 信号的高动态特性，建立了高动态信号捕获的因子图结构，其中将时变多普勒变化率建立为随机游走模型。利用和积算法，推导了因子图各节点间的消息传递公式。在设计的因子图基础上，提出了Turbo 迭代捕获算法，通过码字判决环路和多普勒消除环路之间的软信息交互迭代，提高了高动态环境下的信号捕获性能。最后分析了所提算法的计算复杂度。仿真结果表明，所提算法相比于传统算法在捕获性能和复杂度方面有一定的优势。