一种低运算量GNSS接收机快速捕获方法

程向红，徐文杰

（1. 微惯性仪表与先进导航技术教育部重点实验室，南京 210096；2. 东南大学 仪器科学与工程学院，南京 210096）

北斗三号系统的全面建成使全球卫星导航系统（GNSS）在军事与民用领域的用途更加广泛，特色服务的全面部署也使得GNSS的应用场景丰富多变，包括交通运输、农林渔业、武器装备等专业领域[1]，数十亿的智能设备均集成有GNSS技术。信号捕获是卫星信号接收机内信号处理的第一步，只有完成了信号的捕获，才可能开始信号跟踪等一系列信号处理过程，最终完成位置速度解算（PVT）功能[2]。捕获阶段三维搜索带来的数千万到几十亿次数字乘法会消耗大量的功率及软硬件资源，接收机从上电到实现有效定位，花费在信号捕获上的时间是所有首次定位时间（TTFF）环节中最冗长的一部分[3]；又因为许多支持GNSS的设备，如智能手机，具有严格的电池容量限制，这使得接收机的功耗问题也十分凸显[4]。尤其因卫星信号非常微弱，常需要延长捕获数据长度、增加相干积分时间，使得本就庞大的运算量成倍增加，因而降低捕获阶段的算法运算量，减少捕获阶段花费的时间与其所占的功耗十分必要。低运算量的快速捕获算法也一直是GNSS接收机的研究热点。

信号捕获主要是利用码分多址（CDMA）系统伪随机噪声码（PRN）具有强自相关性实现的。自Van Nee[5]提出基于傅里叶变换（FFT）的并行频率/码相位的搜索算法以来，FFT算法便成为实现卫星信号快速捕获的核心，基于离散傅里叶变换（DFT）与信号卷积的关系，时域中相关函数的运算可以转换为频域的乘法并利用FFT变换极大地减少运算量。Hassanieh[6]提出的稀疏傅里叶变换（SFT）利用捕获结果的稀疏性实现捕获算法的亚线性处理，减少了运算时间。Gao等[7]基于参数估计理论提出了多普勒频移估计算法，减小多普勒频移搜索范围以加快捕获过程。杨峰等[8]根据压缩感知理论降低了捕获运算量，并优化了重构矩阵，使捕获算法具有良好捕获效率。Nie等[9]利用惯性导航系统辅助对星历进行预估，减少多普勒频移与码相位搜索空间以实现快速捕获。许睿等[10]利用多级搜索和降采样策略，通过粗捕获和精捕获的结合实现了无模糊快速捕获。卫星信号的捕获要求在一定的灵敏度下，降低捕获阶段的运算量并保证捕获结果的精度以满足跟踪环路的要求，上述算法都对单个伪码周期内的捕获过程进行了优化，而长相干积分时间下就会造成算法运算量的成倍累积。

本文算法策略借鉴数据分块与降采样的思想，将采集数据二维重排，使多普勒频移搜索粒度细化的同时，只使用一个伪码周期内的数据进行运算，通过降采样操作减少三维搜索阶段的运算点数，使得整体运算量会随着相干积分的时间延长与降采样因子的增大而大幅度降低。最后基于真实信号的半物理仿真验证了本文方法对捕获效率的提升。

1 GNSS信号捕获过程简介

射频前端将天线接收到的信号进行放大、滤波、降噪和混频处理后得到的中频（IF）信号可以描述为：

其中，A为载波信号幅度值；fIF为中频载波频率；fd为多普勒频移；φ0为初始载波相位；Ts为采样周期；τ为传输过程中的时间延迟；n为时间离散序列编号；C(nTs-τ)为伪随机噪声码，其值为±1；SBOC(nTs-τ)为调制副载波，若未调制副载波，该项为1；D(nTs-τ)为导航电文；cos[2π(fIF+fd)nTs+φ0]为载波；η[n]为白噪声。

捕获是一个三维搜索过程，如图1所示，第一维是卫星号（PRN码），如果初始上电没有任何辅助信息，则从天线接收的信号中可能存在的GPS卫星的PRN码数目是32个，北斗是37个，此时必须穷举尝试每一个可能的PRN，若设备拥有辅助导航信息，则可减少大量搜索时间。第二维是伪码相位τ，首先产生本地伪码，对本地伪码设置不同的相位，利用伪码的强自相关性，将本地伪码和输入信号做相关运算，找到正确的伪码相位，根据采样频率的大小与实际需求的码相位精度确定码相位搜索灵敏度tbin。第三维是多普勒频移fd，首先产生本地载波，通过调节本地载波的频率和输入信号相乘并积分，由于不可预测初始输入载波的频率，需要设置不同的本地载波频率值来测试；通常根据卫星与载体间的相对运动状态来确定搜索范围，通过相干积分时间TI来确定载波频率搜索步长fbin，通过搜索范围和搜索步长确定正向及负向搜索频率井个数k。

图1 信号捕获的三维搜索图示Fig.1 3D search diagram of signal acquisition

信号捕获的最终目的就是要“粗略”捕获到载体与卫星之间相对高速移动带来的多普勒频移fd与用来区分卫星、提供测距信息的伪码相位延迟τ。

2 低运算量GNSS快速捕获算法设计

考虑时长为Lms（L≥1且为整数）的数据，假设在1 ms时间内，总共有N个采样点（N由采样频率决定），那么在Lms内，有NL个采样点，L不超过导航电文比特跳变周期。将这些采样点分成L个数据块，每一个数据块恰好包含1 ms的数据采样，如图2所示。

图2 L ms采样数据分块Fig.2 L ms sampling divided into data blocks

一般信号中会有多颗卫星信号，对其中一颗卫星进行分析，PRN为k的卫星得到的离散采样数据sk(n)表示为：

其中，n为时间离散序列编号，n∈[0,NL-1]；fk为信号载波频率，受多普勒频移影响，每颗卫星的载波频率均不同；vk(nTs)是白噪声。因为式(2)中的载波幅度为1，这里将噪声功率做归一化处理。

省略噪声项，仅考虑信号部分，如果L长度小于电文比特周期，则Dk可以看做常数，伪码信号Ck(i)是个周期函数，对GPS和北斗B1I信号的周期都是1 ms，用离散域表示：

sk(n)信号中共有三个分量：｛Dk，Ck，ej2πf knTs｝，其中分量Dk和Ck在不同数据块的相同位置都保持不变，把这L个数据块相同位置的对应点进行叠加，有：

式中，S{sk(n)}是sk(n)中的信号分量，G(L,fk)是一个新增益函数，表示为：

将L段数据合成一段数据，累加后的数据相当于原始信号和G(L,fk)相乘且在ej2πf kiNTs=1时，G(L,fk)取到最大值L，而该函数值与fk有关，使直接对输入信号进行块累加并不能保证原始信号被放大L倍。引入频率为Δfk的本地载波频率补偿信号pk(n)=ej2πΔf knTs，如图3，将pk(n)与sk(n)相乘，得到载波频率补偿后的新信号yk(n)：

图3 频率补偿过程Fig.3 Frequency compensation process

可以看出pk(n)的引入只改变原始载波信号频率，对Dk和Ck无任何影响，噪声分量也只是旋转一定的相位，并无功率谱密度变化。对yk(n)进行块累加得：

其中，fk′=fk+Δfk。当fk′NTs是一个整数时，e j2πf k'iNTs=1，G(L,f′k)中的L项累加值均为1，累加和取到最大值L。

因为NTs=1 ms，所以fk’ NTs是一个整数的条件等价于mod(1 kHz)=0，此时，

即累加后的数据块中信号强度得到了增强，为了实现数据块累加，必须对优化的Δfk进行搜索，搜索过程可以通过串行尝试不同的Δfk以覆盖[0, 1 kHz]的范围。受数据块相同位置采样信号的载波相位特点的启发，通过FFT算法来实现Δfk搜索，并可通过SFT算法进一步降低整体捕获运算量。将图3中的数据二维重排，如图4分成二维矩阵的形式，图中一个粗框内表示一个中频采样点，采样点之间的箭头表示数据流的方向。从矩阵横向看，数据被分成L个横块，每一个横块表示1 ms的采样数据；从纵向看，数据被分成N个竖块，每一个竖块中有L个数据，每个数据之间的时间间隔是1 ms。

图4 中频采样数据二维排列Fig.4 Two-dimensional arrangement of IF sampling data

图5 二维混叠排列Fig.5 Two-dimensional aliasing arrangement

其中β=1…L，竖块中的采样频率是1 kHz，如果把载波频率分成1 kHz的整数倍和余数部分，即

其中F为整数，0 ＜ Δfk＜1 kHz，则第i个竖块的采样点可简化为：

对这L个采样点进行FFT变换，得到的结果为：

式中，ωm=2πmfp/L，m=0, 1…L-1，fp=1 kHz，Δωk=2πΔfk，为简便表述将下标k去除。对式(12)进行化简得：

用Y(i,m)替换第i个竖块的数据，此时第m个横块的数据则为：

A(m)在第m个横块数据内是一个与采样时刻无关的公共项。对第m个横块使用FFT捕获的方法就可以得到全部伪码相位相关的运算结果，如图6所示，唯一区别在于参与相关运算的中频数据中多了一个公共项因子A(m)，其模可以表示为：

图6 对横块数据进行FFT并行捕获Fig.6 FFT parallel capture of horizontal block data

当Δω=ωm时，式(15)取到最大值L，A(m)就可以看做对fk中1 kHz以下部分的选频因子，而fk中1 kHz的部分F是由通过对横块数据进行FFT捕获时通过设定本地载波频率而确定的。

配置静态LACP协议同样也需要网络管理人员手工加入成员端口，但是它可以通过主动端设备来完成链路聚合中相关端口的参数协商，可以实现对端口的活动管理，比如选择其中的两条链路转发数据，另一条链路实现备份。

图6中的本地载波频率设定间隔固定为1 kHz，且对本地伪码取与横块混叠时相同的降采样因子进行时域混叠，最终输出为一个L×B的矩阵，该矩阵的纵坐标(0, 1…B-1)对应混叠的伪码相位筐，横坐标（0, 1 …L-1）对应载波多普勒频率，第m个横块对应的多普勒频率值f(m)为：

多普勒频率的分辨率由ωm决定，而ωm的频率粒度是1 kHz被L等分，所以L越大多普勒频率分辨率就越高，L即对应相干积分时长TI。

寻找到当前卫星超过门限值所对应的多普勒频移与混叠的伪码相位峰值信号后，由于其混叠的伪码相位筐中有p个码片，为p个可能的真实码相位点，对该p个码片分别进行时域相关运算，得到其中时域相关值最大的码片，更新纵坐标的值，此时最大峰值对应的坐标值即为捕获的多普勒频移及伪码相位。

将本地伪码与载波的混合信号的SFT等各项操作提前完成并加以储存，使这部分运算量不占用捕获时间。完成上述存储后，每个横块数据的操作需要两次FFT运算，一次是对横块的FFT运算，另一次是对相乘以后数据的IFFT运算；每个竖块需要一次FFT运算。对于一个L×N的二维数据块，若搜索的多普勒频率范围[-5 kHz, +5 kHz]，总共需要2L×10个横块的B点FFT运算，B个竖块的L点FFT运算，混叠时BL次加法运算，频域中的BL次乘法运算及N次最终重构时的相关运算，按照n点FFT的运算量为nlog2n计算，则本文提出的低运算量捕获算法（BL_FFT）总运算量为：

对LN个数据进行普通的FFT捕获，依然将本地数据预先处理，若想达到相同的多普勒频率分辨率，需要的多普勒频率井个数为10L个，要完成两次FFT运算以及频域中LN次乘法运算，此时的总运算量为：

采用SFT运算则需在FFT运算的基础上增加BL次混叠加法运算，频域中的BL次乘法运算与N次重构相关运算，此时总的运算量为：

如图7(a)为降采样因子固定时运算量随数据块个数的变化曲线，图7(b)为数据块个数固定时运算量随降采样因子的变化曲线，当L>1，p>1时，本文所提算法运算量小于FFT与SFT捕获算法。

图7 理论运算量Fig.7 Theoretical calculation

3 算法仿真与分析

本文利用UTREK210A卫星中频信号前端采集系统采集半物理仿真所需的数据，以验证本文所提出的低运算量快速捕获方法效率，仿真参数如表1。

表1 仿真参数Tab.1 Simulation parameters

在仿真中，主要对比分析了基于FFT、SFT的快速捕获算法与本文所提出的BL_FFT快速捕获算法的性能，当取数据块个数L为2，频率搜索步长为500 Hz，信号长度TI为2 ms。数据采集时天顶上有五颗GPS卫星，随机取50组采集数据做捕获实验，三种方法的捕获结果如图8。

可以从图8(a)看出信号强度较大时，三种方法均能够实现正确捕获，但因降采样影响，同信号强度条件下，SFT与BL_FFT快速捕获算法较FFT快速捕获算法的成功次数略有下降，但捕获失败的实验组可通过增加数据块个数或降低降采样因子的大小实现正确捕获，如图8(b)，虽然运算量有所增加，但其总运算量仍低于初始条件下的FFT或SFT捕获算法，这一结论与图7理论运算量的比较结果相符。

图8 捕获结果统计图Fig.8 Acquisition result statistics

下面以实际捕获结果分析捕获精度及时间，图9为G15卫星的某组三维搜索结果，表2为最终捕获结果数据对比。

表2 仿真实验数据Tab.2 Simulation experiment data

图9 三维搜索结果Fig.9 3D search results

对基于SFT与BL_FFT的快速捕获算法，三维搜索的输出是在降采样因子约束下的结果，如图9(b)(c)，降采样因子取2，尖峰对应的伪码相位取值有2个，相隔8184个相位点，即0.5 ms。

由图9与表2可得，SFT与BL_FFT算法初始输出的伪码相位点数为520，由于混叠该点对应的另一伪码相位点数为8704，分别计算两伪码相位点的相关值，8704码片处的相关值远大于520处的相关值，得到8704为最终的伪码相位点，与FFT算法的结果相同。相比于FFT算法，SFT与BL_FFT算法信噪比降低1.5 dB左右，运算时间却大大减少，BL_FFT算法的时间相比于FFT算法降低了4.1倍，相比于SFT算法降低了1.7倍。按照仿真参数计算，可得CBL_FFT≈CFFT/ 4.5，CBL_FFT≈CSFT/ 2.1与实验结果倍数均相差0.4，该部分误差由硬件及额外运算造成。

4 结 论

本文针对采用长相干积分时间捕获时导致运算量成倍累积、载波频率误差容忍度低的问题，利用数据分块与降采样的思想，提出了一种低运算量快速捕获方法，实现了缩小频率搜索步长并增加积分数据量的需求。理论分析与仿真结果表明：

1)本文提出的低运算量快速捕获方法可以将多普勒频移搜索分辨率细化为1/LkHz，对信号进行频率补偿后的累加将信噪比增大10lgLdB，将整体运算量缩减至20LBlog2B+BLlog2L+2BL+2N。

2)采样频率固定的情况下，算法的整体运算量由L、p两个参数决定，当L=1，p=1或L=1，p>1时，算法等同于基于FFT或SFT的捕获算法，当L>1，p>1时，运算量有明显降低。

3)TI=2 ms，L=2，p=2时，算法较基于FFT的方法信噪比降低约1.5 dB，效率提升约4.1倍；较基于SFT的方法信噪比降低约0.01 dB，效率提升约1.7倍。即使对于微弱信号该算法需要增加数据块个数或降低降采样因子的大小实现正确捕获，其整体运算时间仍优于基于FFT或SFT的捕获算法。