高抗噪性的SFFT-DT快速捕获算法

张浩冉 徐 颖 罗瑞丹 毛 亿

（1.中国科学院空天信息创新研究院，北京 100094；2.中国科学院大学光电学院，北京 100049；3.空中交通管理系统与技术国家重点实验室，江苏南京 210007）

1 引言

全球卫星导航系统（Global Navigation Satellite System，GNSS）可向全球用户提供高质量的定位、导航和授时服务，目前已在各个领域得到了广泛应用［1-3］。导航接收机在实现导航定位功能之前，必须先对导航信号进行捕获、跟踪与解调，其中，信号捕获过程消耗着接收机的大量资源，据统计在整个导航定位过程中大约有30%至75%的资源消耗来自于信号捕获过程。随着GPS 定位芯片在各种便携式设备中的普及，功耗逐渐成为评价其适用性的关键指标之一［4-5］。为此本文设计了一种针对GNSS直接序列扩频信号的快速捕获算法，在降低捕获过程资源消耗的同时具有良好的信号检测性能。

目前常见的捕获算法有时域线性捕获、基于FFT 的并行频率捕获和并行码相位捕获［6］算法等。其中，基于FFT 的并行码相位捕获（FFT-Capture）算法由于可以通过一次变换实现伪码相位的全搜索，目前最为常用。但当数据长度较长时，其计算量仍过于庞大，有学者提出将计算效率更高的SFFT 引入到并行码相位捕获算法中。SFFT 算法最早由文献［7-8］提出，该算法主要通过对时域信号进行频谱重排、加窗、混叠降采样以及FFT 以较小的计算量将原始信号的傅里叶系数投影到低维空间中。对于稀疏信号（频域仅有少数大值点），每个投影点中很大概率只包含一个大值点，通过对投影结果进行定位（找到它在原始频谱中的位置）和估值，可以以较小的计算量得到大值点在原始频谱中的位置及幅值。目前该算法已在频谱分析［9］、图像处理［10-11］、5G［12］通信和雷达探测［13］等领域得到了广泛应用。

文献［14］首次将稀疏快速傅里叶变换的混叠降采样过程应用于信号捕获中，提出了一种快速同步算法（QuickSync），但当卫星信号较弱时，需要进行长时间相干积分来提升算法的信号检测能力［15］。文献［16］用逆快速傅里叶变换（Inverse Sparse Fast Fourier Transform，ISFFT）替换了并行码相位捕获中的IFFT过程，从而提升了算法的捕获效率。但由于SFFT 中的定位与估值过程对噪声容忍能力均比较差，导致算法的总体抗噪性能仍然较弱。文献［17］提出一种用相关计算代替SFFT 估值过程的捕获算法（SFFT-Correlate），使得其抗噪性能较文献［16］有所提升，但并没有对噪声容忍能力较差的定位过程进行优化，改善此过程可进一步提升算法的抗噪性能。

本文提出了一种新的SFFT-DT 并行码相位捕获算法，该算法利用DFFT［18］及SFFT 进行联合大值点定位，去除了SFFT 中对噪声容忍能力较差的定位循环与估值循环过程，在降低捕获过程计算量的同时保证了算法具有较好的信号检测能力。本文首先对SFFT 捕获算法的不足进行了详细分析，然后对SFFT-DT 算法进行了论述，最后结合理论分析及实验仿真对设计算法进行了验证。

2 SFFT捕获算法性能分析

2.1 基于SFFT的快速捕获算法

如图1 所示，SFFT 一般被用于并行码相位捕获算法的逆变换过程。记R（k）为混频信号（由输入数字中频信号与本地复制载波信号相乘得到的信号）与本地复制的伪码信号分别进行FFT 变换后共轭相乘得到的结果，此时SFFT 并行码相位捕获算法的逆变换过程主要分为以下几步：

i：首先利用哈希映射以少量运算将输入信号的傅里叶系数投影到低维空间中，其主要过程为：

（1）对R（k）进行频谱重排及窗函数滤波，即

其中x∈RN表示输入信号，σ-1表示关于模N的数论倒数［7］，τ∈[0，N-1]为一随机数。Fk表示平坦窗函数，可以有效减弱频谱泄露对IFFT 变换结果的影响。

（2）对yk进行频域混叠及IFFT变换，即

其中B为频域混叠因子，由式（2）至（4）可知，利用哈希映射可将参与IFFT变换的数据长度由原来的N维降低到B维，从而大大降低逆变换过程的计算复杂度。

其中hσ(i)和oσ(i)分别表示哈希函数及偏移函数［7］，即

iii：对i和ii步骤进行L=log2N次循环，得到大值点可能的位置集合Ir={I1，I2，…，IL}。统计Ir中各个下标出现的次数，记为Ti={i|count(i=k)，k∈Ir}，找出其中出现次数大于L/2的下标，记为最终定位结果Is={i|Ti≥L/2}。利用估值循环对Is中的点进行估值，即

找出其中幅值最大的点，其下标值即为大值点在原始IFFT结果中的位置。

通过ISFFT变换，可将逆变换过程的计算复杂度由原来的O(Nlog2N)降为，计算复杂度仅为IFFT 算法的，且数据长度越长，ISFFT 捕获算法的计算优势越明显，进而实现导航信号的快速捕获。

2.2 SFFT并行码相位捕获算法不足

虽然利用ISFFT 替代并行码相位捕获的IFFT过程后，算法的计算效率得到了有效提升，但基于SFFT的并行码相位捕获算法还存以下两个问题：

（1）算法的抗噪性能较差：如式（1）和（2）所示，在已有的SFFT 捕获算法中，为保证各次哈希逆映射结果间除大值点外其余位置不会重合，在每次哈希映射前需对输入信号进行频谱重排。对于宽带信号，该过程不会对哈希映射结果产生较大影响。但由于伪码相关信号属于窄带信号，如图2 所示其能量主要分布在频宽为2.046 MHz 的主峰中，频谱重排会使得信号能量近似均匀的分布在整个频域上，导致信号加窗后会产生较大信噪比损失，从而造成算法的抗噪性能变差。

（2）算法流程比较繁琐：现有的SFFT 算法是针对所有信号的一个通用设计，对于伪码相关信号这种超稀疏信号（时域相关结果仅有一个峰值），定位循环和估值循环过程显得有些繁琐和不合时宜，此时可通过其他的方法来对此过程进行进一步优化，以提升算法的抗噪性能同时降低其实现的复杂度。

上述两个问题限制了SFFT 算法在并行码相位捕获算法中的应用，需根据导航信号的特点对其加以改进。

3 高抗噪性的SFFT-DT快速捕获算法

为解决SFFT 捕获算法中定位循环信噪比损失较大、算法流程繁琐的问题，提出了一种新的基于SFFT-DT 的快速捕获算法。该算法去除了SFFT 捕获算法中对算法抗噪性能影响较大的定位循环与估值循环过程，转而通过DFFT 的变换结果与SFFT的哈希映射结果的交集来确定大值点位置，在提升捕获算法抗噪性能的同时简化了其实现流程。

3.1 本文算法介绍

本文算法的主要流程如下：

步骤1：首先将本地伪码与混频信号的FFT 变换结果共轭相乘，得到R（k），即

步骤2：将R（k）与窗函数F(k)相乘，得到加窗后信号。对Rc(k)进行频域混叠后得到Rcd(k)，对Rcd(k)进行IFFT变换后得到时域降采样结果cd(n)，即Rc(k)

为避免时域变换结果发生频谱泄露，本文仍采用平坦窗函数对信号进行加窗。

步骤3：当cd(n)大于阈值时，记其下标为k1，利用式（8）进行哈希逆映射，得到大值点在原始IFFT变换中可能的位置集合I1，即

步骤4：对R（k）直接进行降采样，即Rm(k)=R(mk)，对Rm(k)进行IFFT 变换后得到其时域变换结果cd1(n)，记其大值点下标为k2，则其在原始IFFT变换中大值点的可能位置为

步骤5：计算大值点的位置：km=I1∩I2。当两者下采样因子选取适当时，I1，I2存在唯一交点，即为大值点所在位置。

如图4 所示，去除定位循环过程后，步骤3 得到的结果存在一个连续的模糊度p=N/B。步骤4 得到的结果模糊度为m，这m个位置点以N/m为步长等间隔分布在整个变换域上，通过对两者做交集可以快速得到大值点的真实位置。

3.2 算法参数设计

3.2.1 混叠因子B及降采样因子m设计

在步骤2 中，为保证频域混叠结果Rcd(k)中各点叠加的数据长度一致，最好满足B可以整除N，即

如当N=10404时，B合适的取值有B={153，289，306，578，612，867，1734.......}等。B越小，算法的计算量越小，但算法抗噪性能也会随之下降，因此B的选择应综合考虑算法的计算量和抗噪性能要求。

为保证步骤4 的定位结果I2与步骤3 的定位结果I1仅有一个交点，需满足m≤B，则m的最终取值范围可表示为m∈[1，B]。同时由于参与IFFT 变换的信号长度由原来的N降到了N/m，因此会使得算法产生约10 log10(m)dB 的信噪比损失，在实际应用中需根据算法的信噪比要求对参数m加以选择。

3.2.2 窗函数参数设计

为保证步骤2的频域混叠不会导致时域降采样结果产生信息损失，取平坦窗函数的时域主瓣宽等于时域降采样间隔N/B。同时由于去除了定位过程的log2N次循环，本文算法的计算复杂度与窗函数长度w（w=supp(F)，supp(x)表示信号x的支撑集）的关系由原来的O(wlog2N)降为了O（w），我们可以选择更长的窗函数来对输入信号进行滤波，在此我们取w=N。此时平坦窗F（k）可由高斯窗g（k）和标准窗h（k）相乘得到［7］，即

其中δ表示平坦窗函在其通带内的波动幅度，一般取δ=1/N。

3.3 算法性能分析

3.3.1 信噪比性能分析

本节主要对去除定位循环的频谱重排过程所带来的信噪比增益进行分析，加窗后信号Rc(k)在整个频域上的信噪比可近似表示为

其中f=2π/w表示信号频率，Af表示频域信号幅值，fe表示本地信号与输入信号的频差，表示频域信号噪声功率。假设窗函数在频域的截止频率为fc，且频谱重排后信号能量近似均匀分布在整个变换域上，那么在窗函数的主瓣内，由去除定位循环的频谱重排过程所带来的信噪比增益可近似表示为

公式（19）的信噪比增益随采样率fs及窗函数截止频率fc的变换关系如图5所示。

结合式（18）、（19）和图5可知，当窗函数截止频率fc一定时，SNRgain，avg（去频谱重排所带来的信噪比增益）与采样率fs成正相关，这是因为信号的采样率越高，频谱重排会造成频域信号R(k)的能量越分散，进而导致加窗信号的能量损失越大，本文去除频谱重排的信噪比性能优势就更加明显。当采样频率fs一定时，SNRgain，avg与窗函数截止频率fc呈负相关，这是因为窗函数的主瓣范围越宽，频谱重排对加窗信号能量损失的影响越弱。当窗函数截止频率fc=fs时，SNRgain，avg近似为0，这是因为此时整个频域都被窗函数的通带所包含，频谱重排对加窗信号能量损失的影响不大。

结合式（15）至（17）可知，平坦窗函数在频域上的截止频率可近似表示为fc=3Bfs/N（窗函数90%以上能量集中在此范围内）。为保证算法的低运算量，要求B远小于N，即fc取值较小，则由图5可知此时本文算法与SFFT-Correlate 算法的频谱重排变换相比，会有较大的信噪比性能提升。

由图3 与步骤5 可知，为最终确定大值点位置，算法需同时得到正确的定位集合I1和I2。则算法的最终捕获概率PSFFT-DT与步骤3 定位成功的概率PSFFT和步骤4定位成功的概率PDFFT成正比，即

因此当步骤3 的信噪比增益为SNRgain，avg时，本文算法最终的抗噪性能也会得到相同分贝的提升。

3.3.2 计算复杂度分析

若混频信号可以表示为x∈CN，则步骤1 需要2N+Nlog2N次复数乘法和2Nlog2N次复数加法，步骤2 需要次复数乘法和(Blog2(B)+N-B)次复数加法，步骤3 线性映射的计算量为2（逆映射区间是连续的，不需一一映射）。步骤4 需要B1log2B1次复数加法和B1/2 log2B1次复数乘法，其中B1=N/m，步骤5 的计算量为m，m表示降采样因子。假设整个搜索过程的非相干累加次数为S，伪码FFT结果预先存储在接收机中，由于步骤4和步骤5在整个捕获过程中参与运算的次数很少，因此本文算法的计算复杂度可为O(SNlog2N+Blog2B+2N-B)，FFT-Capture 算法的计算复杂度为O(SNlog2N+Nlog2N)，SFFT-Correlate 捕获算法的计算复杂度为，a为一常数。

4 仿真实验

为验证本文算法的抗噪性能和捕获速度，本节利用仿真数据对设计算法的性能进行验证分析，具体仿真参数如表1所示。

表1 实验仿真参数Tab.1 Experimental simulation parameters

首先根据3.2.1 节对频域混叠因子B进行取值，然后对不同B下步骤3 定位成功的概率PSFFT进行统计，若哈希逆映射结果I1包含大值点位置，则认为步骤3 变换成功。在不同信噪比下各进行1000 次仿真，仿真结果及不同B下算法的计算复杂度分别如图6、图7所示。

从图6 可以看出，随着B的增大，在相同信噪比下步骤3得到正确结果的概率PSFFT也随之增加。但由于B的大小与算法的计算复杂度成正相关，如图7 所示，综合考虑算法计算复杂度及PSFFT，取B=612。则结合式（19）、（20）及图5 可知，本文算法去除频谱重排所获得的信噪比增益大约为4.5 dB。

在不同的降采样因子m下，对步骤4 定位成功的概率PDFFT进行仿真，在不同信噪比下各进行1000次独立实验，统计结果如图8所示。

从图8 可以看出，步骤4 的定位成功概率PDFFT与m的取值成反比。如当m=2 时，PDFFT在输入信号信噪比大于-19.5 dB 时达到了95%以上。而当m=3 时，PDFFT在输入信号信噪比大于-18 dB 时才达到了95%以上。在实际捕获中，应根据实际需要对m的取值进行选择。

现在我们对算法的总体抗噪性能PSFFT-DT进行仿真验证，在不同信噪比下对上述三种算法分别进行1000 次独立仿真，并对其捕获概率进行统计，结果如图9所示。

从图9 可知，当m=1 时，本文算法与FFTCapture 算法的捕获概率均在输入信号信噪比大于-22 dB 时达到了95%以上。当m=2 时，本文算法的捕获概率在输入信号信噪比大于-19 dB 时达到了95%以上。当m=4时，本文算法与SFFT-Correlate算法的捕获概率均在输入信号信噪比大于-17 dB时达到了95%以上。通过上述对比可知，在捕获概率高于95%的前提下，本文算法的抗噪性能最大可比SFFT-Correlate 算法高5 dB 左右。这是因为本算法去除了SFFT-Correlate 算法中对噪声容忍能力较差的定位循环过程，使得加窗后信号的能量得到了更好的保留。此时三种算法的计算量对比如表2所示。

由表2可以看出，本文算法的计算量较文献［6］的FFT 捕获算法减少了约43%，较文献［17］的SFFT-Correlate 算法减少了约19%。同时由于本文算法在IFFT 过程中没有复杂的定位循环和估值循环，因此硬件实现的复杂度更低，更利于工程实现。

结合3.3 节分析、表2、图6 至图9 的仿真结果可知，本文算法的抗噪性能与文献［17］的SFFT 捕获算法相比有较大提高。与经典的FFT 捕获算法相比，当两者抗噪性能近似相同（捕获概率大于95%的前提下）时，本文算法计算量更小。

表2 运算量对比Tab.2 Comparison of calculation amount

5 结论

本文针对SFFT 捕获算法中频谱重排过程对捕获算法抗噪性能的影响进行了分析，并利用伪码相关信号大值点唯一的特征，提出了一种抗噪性能更好的高抗噪性快速捕获算法。该算法用DFFT 替代了SFFT 捕获算法中原有的对噪声容忍能力较弱的定位循环过程，使得加窗后频域信号的能量得到了最大程度的保留。理论分析及仿真结果均表明，本文算法不仅进一步降低了捕获算法的计算量，而且与已有的SFFT 捕获算法相比本文算法的抗噪性能也得到了较大提升，适用于导航信号的快速捕获。