精度改进的B1频点快速捕获算法及FPGA实现

胡铁乔，韩煜昕，杨焕芹

（中国民航大学智能信号与图像处理重点实验室，天津 300300）

精度改进的B1频点快速捕获算法及FPGA实现

胡铁乔，韩煜昕，杨焕芹

（中国民航大学智能信号与图像处理重点实验室，天津 300300）

北斗静止轨道卫星电文传输速率高，电文翻转导致捕获算法的相关增益和频移搜索精度降低。针对这一问题，结合传统部分匹配滤波器与FFT捕获算法的优点，提出一种能够消除导航电文翻转提高频移搜索精度的快速捕获方法。首先给出算法的理论论证；然后将算法的有效性同传统算法比较；最后对算法的工程实用性通过FPGA平台进一步验证。算法仿真以及FPGA平台的测试结果表明，在获得相同伪码搜索精度的条件下，该方法能够消除电文翻转对多普勒频移搜索精度的影响，实现北斗B1信号的高精度快速捕获。

B1频点；电文翻转；捕获算法；FPGA

中国卫星导航系统管理办公室公布的北斗卫星导航系统空间信号接口控制文件指出，静止轨道卫星（geostationary orbit satellites,GEO）的电文传输速率是500 bps[1]，是GPS电文传输速率的10倍。如此高的传输速率，要求接收机基带信号处理模块有更高的处理性能。而捕获是导航定位接收机基带信号处理的前端，捕获的精度和速度关系到接收机能否实现快速准确定位。随着北斗接收机的普遍应用，尤其在一些复杂场景中，对捕获速度和精度提出了更高的要求。

根据时域和频域二维空间搜索方式的不同，可以分为4种搜索方式：二维串行搜索[2]虽然理论基础简单，实现复杂度低，占用资源少，但是捕获速度慢，工程建设上一般不用；基于差分处理的二维并行搜索在文献[3]中进行了详细分析，该算法能极大降低捕获时间，资源占用也较小，不足之处是该算法自身引起很大的信噪比损失，且信噪比损失随着信号扩频码长度的增加而增大，实验表明该算法不能完成常规环境下B1频点的捕获；第3种捕获方法是并行搜索码相位的捕获算法[4]，该算法首先步进式设置本地载波完成频移的搜索，然后利用FFT实现循环相关来实现伪随机码的并行搜索，是一种经典的捕获算法，在GPS中获得了广泛应用；第4种算法是并行搜索频率的捕获算法，基于该思想的一种捕获方法是部分匹配滤波器与FFT相结合的捕获算法[5]，同方法三一样能够实现长扩频码的捕获。本文提出的改进捕获算法消除了电文翻转的影响，算法和硬件平台的测试结果证明了算法的有效性和实用性。

本文主要内容为：①理论分析了部分匹配滤波器与FFT捕获算法的原理，在此基础上提出本文算法；②结合常用算法的捕获性能，对本文算法进行实验论证；③算法实现和测试，从工程实现的角度论证算法的有效性；④总结全文。

1 捕获算法原理

1.1 传统的部分匹配滤波器与FFT捕获算法

用部分匹配滤波器组完成码相位短时并行解扩，然后在频域通过对频谱进行分析检测得到载波频移。

算法原理如图1所示。下变频信号分为D段，分别进入X阶匹配滤波器，与本地X位信号相关，得到D个相关值。经过X/2次块内滑动相关，得到一个D· X/2的相关值矩阵，对该矩阵的各列补0做M点的FFT。当接收信号与本地信号相位差小于X时，即可完成对当前卫星的捕获；反之，重新进入下一轮捕获。

图1 部分匹配滤波器与FFT捕获算法原理框图Fig.1 Block diagram of part matched filter and FFT acquisition algorithm

相关值矩阵中的每一个相关值都包含了电文、码相位、频移信息，对该矩阵搜索最大值，最大值所在的列坐标就是码相位的位置，不考虑电文翻转，对最大值所在的列进行M点FFT求出频谱，得到含有电文和频移信息的频谱，也就得到了多普勒频移。下面将分析部分匹配滤波器组与FFT的工作原理。

每部分匹配滤波器的输出可记为

其中：Zi表示第i个部分匹配滤波器的输出；A代表该卫星的振幅；D（nts）表示接收到的导航电文；C（nts-τ）表示接收到的测距码。若某一时刻，接收信号的测距码和本地测距码的相位同步，则有

代入式（1），有

测距码同步后，将这D个相关值补0点至M点送入FFT模块，FFT的输出为

通过式（3）可看出，若没有电文翻转，X值越大，相关值Zi越大，同时X的取值要满足Hz。若有电文翻转，不仅影响相关值，也会影响频移搜索精度[6]。重复上面的操作，进行非相干累加，然后门限检测，若满足门限，则结束对当前星的搜索；否则，调整码发生器的延迟，开始下一轮搜索。

1.2 精度提高的部分匹配滤波器与FFT捕获算法

部分匹配滤波器与FFT捕获算法和基于FFT的循环相关算法相比，可以解决时域并行捕获所带来的频域搜索效率低的问题。根据最大取值处的谱线位置，可以得到频偏。当有电文翻转时，相关峰值可能出现在错误的频点处，而且仅靠相关峰的绝对值不足以将此错误位置区分开。针对这一问题，在部分匹配滤波器与FFT捕获算法的基础上，本文提出一种消除电文翻转的同时提高频偏搜索精度的快速捕获方法，即PartialMatched Filter+ Frequency Doubling+Fast Fourier Transformation。该算法首先通过部分匹配滤波器实现接收信号和本地测距码的线性相关；然后，对相关值矩阵进行调整，根据二倍频理论对信号进行重构，消除电文翻转的影响；将重构后的信号送去FFT模块，得到信号解扩后的功率谱，由最大取值处的谱线位置得到频偏。

结合式（3），每个相关值Zi（n）可以简记为Zi（n）= I+jQ，其中

为消除D（nts）的电文翻转，用I、Q构造新的两路信号，构造后的I、Q路为

其中：β、α是处理后迭加到噪声上的系数。从I′、Q′的表达式中可以看出电文翻转的影响得到消除。此外，I′、Q′的表达式中噪声幅度发生了变化，后面将给出算法的性能分析。

2 性能分析比较

本节对改进前后捕获算法的性能进行Matlab仿真，并同经典的基于FFT计算循环相关搜索码相位的方法相比较。仿真参数设置为：多普勒频移的搜索范围为±10 kHz，频移精度在±250 Hz以内，捕获码相位的精度为半个码片；采样率fs=±10 MHz；D、X、M的取值要考虑频移搜索精度、算法增益和运算量的问题，经过前面理论分析和实验，D、X、M分别取值40、250、128。

2.1 捕获灵敏度分析

通过匹配滤波器组计算滑动相关以及用FFT计算循环相关都是线性变化，不会引起信噪比的恶化。那么在相干积分时间和非相干累加次数一样的条件下，上述算法的输出信噪比都有如下表达式

其中：n是相干积分的ms数；G1是1 ms相干积分的积分增益；10 lg（n）是n ms的附加相干积分增益；m是非相干积分的数目;[10 lg（m）-L（m）]是非相干积分的增益，其中L（m）是非相干积分损耗[7]，两种算法不同的地方就在G1。下面通过统计不同信号强度的捕获概率来比较两种算法的灵敏度。

借助实验室B1频点数字中频信号仿真器，产生不同强度的信号进行蒙特卡洛仿真，统计算法在100次实验中对PRN1的检测概率，实验结果如图2所示。信号中频是2.098 MHz，采样率是10 MHz。积分增益的计算都是进行2 ms的相干积分，10 ms非相干累加。

图2 算法灵敏度比较Fig.2 Sensitivity comparison of acquisition algorithm

图2是在相同的条件下，比较分析了3种捕获方法不同信噪比下的检测概率。可以发现，部分匹配滤波器与FFT捕获算法对35 dB稍弱信号的捕获概率是75%，本文提出的捕获算法相对损失了一定的算法增益，对40 dB的捕获概率约为50%。但是考虑到室外卫星信号的载噪比值大致在38～55 dB的范围内变动，而且稍弱的卫星信号会导致定位精度降低，基于此，改进后的算法可以用在常规接收机中。

2.2 频移搜索精度分析

频移搜索精度高的接收机可以不经过牵引直接进入跟踪状态，此外，频率估计残差越大，相关积分峰值越低[8]。这就要求参数的设置尽可能提高频移的搜索精度。按照上面第二节开始处仿真参数设置，PMF+ FD+FFT捕获算法的频移搜索分辨率在156.25 Hz，基于FFT并行搜索码相位算法实现中的频移搜索步长常用500 Hz。显然，前者获得的频移精度高一些，图3统计了3种算法对仿真数据（有7颗卫星可见）的频移搜索残差。可发现在统一的参数设置下，传统的部分匹配滤波器与FFT捕获算法可能会比改进后的PMF+FD+FFT捕获算法获得的频移搜索残差大，甚至超出一般跟踪环路的要求。

图3 两种算法的频移搜索残差比较Fig.3 Searching frequency shift residuals comparison of two methods

通过参数调整，3种算法都可进一步提高频偏搜索精度，相应频域搜索的效率降低，也会牺牲捕获速度和资源的占用，下面对同一捕获精度下的平均捕获时间进行分析。

2.3 平均捕获时间

分析文献[9-10]，得出平均捕获时间为

其中：PD是检测成功概率；PFA是虚警概率；K是证实发生虚警所需要的判决次数，一般取10次。是不考虑捕获概率时的平均捕获时间，q是码相位和频移组成的二维搜索范围的单元数，单次积分驻留时间τ是在每个搜索单元上完成一次搜索的时间。

此处统一捕获指标如下：码片精度在半个码片以内，频偏精度在156.25 Hz，频移搜索范围是20 kHz。那么由二维搜索范围可计算得出搜索的单元数为

如果用基于FFT并行搜索码相位算法，搜索单元数降为128个；如果用部分匹配滤波器捕获算法，搜索单元数为4 092。进一步假设3种搜索方法在每个搜索单元的积分驻留时间一样，那么基于FFT并行搜索码相位算法和部分匹配滤波器捕获算法比二维串行搜索的平均捕获时间短，提高了捕获的速度。另外，在FPGA实现中，部分匹配滤波器捕获算法可实现时域和频域二维的完全并行搜索，换言之，本文提出的PMF+FD+FFT捕获算法不仅能够改善频移搜索精度，还能够实现快速捕获。后面将对该算法的实用性通过实现进一步论证。

3 算法实现

3.1 基于FPGA的算法实现

PMF+FD+FFT捕获方案设计的出发点是要提高多普勒频移的搜索精度、节省资源。基于FPGA的算法实现可通过自上而下的设计思路来完成，结合前面的算法理论分析，给出方案完整的流程图，如图4所示。为节省存储资源，读入FPGA的数据是经过处理的2位0中频数字信号，测距码是根据伪码实时产生的，位宽为1。设置读写地址，将数据和测距码串行送入双端口RAM，分段并行读出，送入部分匹配滤波器模块，实现短时线性相关，然后调整时序和位宽，并行实现2倍频、FFT、模值计算、非相干累加和最大值搜索。

图4 整体功能的实现流程图Fig.4 Algorithm flowchart

部分匹配滤波器模块功能实现如图5所示，首先将0中频的缓存信号和测距码读入，进行相关积分运算，然后缓存相关结果，对其进行FFT变换。该模块是捕获部分信号处理的核心模块。

本地伪码通过伪码延时链，将不同延时的本地伪码和接收信号送入相关器进行相关操作，相关器由乘法器和寄存器组成。每一个并行相关器功能就是前面说的部分匹配滤波器，在并行相关器中进行短时并行相关，到积分器清除的时刻，将相关结果送入寄存器中，当达到相干积分时间后，再将寄存器中的相关结果送至二倍频模块，然后进行频谱分析，得到二维相关结果矩阵。并行相关器的数量决定捕获的速度，相关器越多，一次能够计算的相关结果也越多，同时占用的资源也越多。本文设计2 ms的相干积分，并行搜索相关器的个数是80×5个，得到128×125×5个相关值，搜索最大值，完成5块的并行搜索，串行搜索8次完成整个码相位维的搜索。

图5 部分匹配滤波器模块和FFT模块的细节图Fig.5 Detail of part matched filter module and FFT module

3.2 资源占用

在ISE13.4环境下，实现上述功能，编写Verilog代码，统计整个捕获系统的资源占用情况。表1列出了捕获模块的资源消耗，组合逻辑占用了整个FPGA的16%，块状RAM占用了51%，主要用来完成数据、测距码的分段缓存和相关模值的存储；在倍频部分和模值计算部分消耗了5%的乘法器资源。

表1 资源占用汇总Tab.1 Summary of resource consumptions

3.3 测试结果

捕获模块调通以后，搭建硬件测试环境，如图6所示，由DSP发出捕获控制中断，进行实时信号处理。

图6 系统硬件测试环境Fig.6 System hardware testing environment

图7是某一次系统测试的结果，记录了下午3点的捕获情况。其中图7（a）是截取的PRN1～PRN16在10次捕获结果中获得的最大积分峰值。FPGA将积分峰值送入DSP，由DSP判断当前卫星是否捕获成功。图7（b）是频点信息，每一列对应一颗卫星在10次捕获中获得的频点信息，由频点得出多普勒频偏；图7（c）是码相位的起始位置信息，每一列对应一颗卫星在10次捕获中获得的码相位。在DSP中门限取130，不满足门限的卫星的频点和码相位分别赋值为-1和0。若卫星成功捕获，那么其频点稳定，码相位起始位置规律变化，由图7（b）、图7（c）可知，共搜索到9颗可见卫星，分别是PRN3、PRN4、PRN5、PRN6、PRN8、PRN9、PRN11、PRN13、PRN14。综上，基于FPGA的硬件系统能够完成B1信号的实时捕获任务。

图7 基于FPGA的捕获结果图Fig.7 Diagram of capture results based on FPGA

4 结语

针对GEO卫星电文翻转的问题，本文提出一种消除电文翻转对频谱分析影响的捕获算法，并在FPGA平台上实现了该捕获方案。算法仿真和FPGA系统的测试结果表明，该方法较FFT计算循环相关的算法实现了时/频域二维的并行搜索，提高了捕获速度；同时，较传统部分匹配滤波器与FFT结合的算法提高了频移搜索的精度。另外，算法中的二倍频处理设置在FFT模块之前，在时序上取代了相关值缓存所占用的时间，从而不会明显降低捕获的速度。

[1]中国卫星导航系统管理办公室.北斗卫星导航系统空间信号接口控制文件(ICD)公开服务信号B1I(1.0版)[S].2012.

[2]POLYDOROS A,WEBER C L.A unified approach to serial search spread-spectrum code acquisition—Part I&II：General theory[J].IEEE Transactions on Communications,1984,32(5):542-549.

[3]罗炬锋,王 翔,付耀先,等.基于FFT并行搜索伪码和频偏的快速捕获新方法[J].电子与信息学报,2011,33(3):563-568.

[4]JUN W,WU S,JU W,et al.Direct Acquisition Method of GPS P Code and its Parameter Optimization[C]//International Conference on Communications and Mobile Computing,2010:469-475.

[5]LIU C,ZHANG J,ZHU Y,et al.Analysis and Optimization of PMFFFT Acquisition Algorithm for High-Dynamic GPS Signal[C]//Cybernetics and Intelligent Systems(CIS),2011:IEEE 5th International Conference on.2011：185-189.

[6]商向永,杨 俊,陈 莉,等.扩频信号捕获过程中信息比特跳变对载波频率估计的影响[J].宇航计测技术,2012,32(6):43-46.

[7]JAMES BAO-YEN TSUI.Fundamentals of Global Positioning System Receivers A Software Approach[M].2nd ed.Beijing:Publishing House of Electronics Industry,2007:198-199.

[8]王立冬,胡卫东,郁文贤.时延-多普勒频移对伪码捕获影响的性能分析[J].系统工程与电子技术,2001,23(6):79-81，87.

[9]谢 钢.GPS原理与接收机设计[M].北京:电子工业出版社,2009: 349-352.

[10]HOLMES J K,CHEN C C.Acquisition time performance of PN spreadspectrum systems[J].IEEE Transactions on Communications,1977,25 (8):778-784.

（责任编辑：杨媛媛）

Accuracy-improved B1 signal fast acquisition algorithm and FPGA implementation

HU Tieqiao,HAN Yuxin,YANG Huanqin
（Intelligent Signal and Image Processing Key Lab of Tianjin,CAUC,Tianjin 300300,China）

The high message transmission rate of GEO(geostationary orbit satellites)for BDS may lead to reduced correlation gain and searching precision of frequency shift in acquisition algorithm.In order to solve this problem,combining with the advantage of traditional partial matched filter and FFT acquisition algorithm,a fast acquisition method which can eliminate transition of navigation message and improve the searching accuracy of frequency shift is proposed.Firstly,theoretical demonstration of the algorithm is given;the algorithm validity is then compared with traditional algorithm’s;finally,the engineering practicability of the algorithm is further verified through FPGA platform.Results of algorithm simulation and FPGA platform test show that in the same condition of pseudo code searching precision,the current method can eliminate transition influence of navigation message on the searching accuracy of doppler shift,and fast capture ability of B1 signal is achieved with high precision under the condition of same searching precision of pseudo code.

B1 frequency points;data transition;acquisition algorithm;FPGA

V249.33；P228.1

：A

：1674－5590（2016）06－0015－06

2015-09-16；

：2015-12-10

国家自然科学基金项目（61271404，61471363）；中央高校基本科研业务费专项（3122014D003）

胡铁乔（1970—），男，河南洛阳人，副教授，工学硕士，研究方向为基于FPGA、DSP高速处理平台的阵列信号处理系统.