基于FFT的GPS信号快速捕获算法研究

曲丽娜，顾成虎，季 强

(1. 哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001；2. 沈阳飞机设计研究所，沈阳 110035)

基于FFT的GPS信号快速捕获算法研究

曲丽娜1，顾成虎1，季 强2

(1. 哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001；2. 沈阳飞机设计研究所，沈阳 110035)

GPS信号捕获是GPS接收机信号处理的关键技术之一，选择合适的捕获方法对接收机的工作性能有很大改善.传统的串行捕获算法计算量大，捕获时间长，无法满足GPS接收机实时处理的要求，而基于FFT的GPS信号快速捕获算法弥补了串行捕获算法的不足.通过MATLAB仿真对基于FFT的GPS信号快速捕获算法进行了仿真实验，并采用Monte Carlo方法对算法的频偏及码偏估计性能进行验证.仿真结果验证了FFT捕获算法的有效性和可靠性.

全球定位系统 ；串行捕获算法；FFT捕获算法

GPS(Global Positioning System)即全球定位系统，在GPS接收机中，直接序列扩频技术应用最为广泛[1].近几年来，世界各国对扩频技术的研究与应用达到高潮，尤其是信号的捕获跟踪，作为扩频通信的核心技术，也越来越受到重视[2-6].

现针对GPS信号的捕获有大量算法，文献[7]在无线电导航接收机的环境下，对基于FFT的捕获算法的捕获性能进行分析，该算法在低信噪比情况下仍具有较好的捕获性能.文献[8]分析了在GPS接收机的环境下，采用FFT捕获技术可以使捕获速度得到显著提高.文献[9]分别从伪码特性、FFT栅栏效应和信道影响三方面分析了基于FFT捕获算法的性能，在-15 dB低信噪比下FFT捕获算法仍具有良好的捕获性能[10].

本文在上述研究的基础上，对串行捕获算法和FFT的快速捕获算法进行了进一步的理论分析和比较，对基于FFT的捕获算法的频偏及码偏估计性能进行了统计分析，并对实验结果进行了分析.

1 串行搜索捕获基本原理

串行搜索捕获算法根据捕获原理，在码域和频域上进行二维搜索，算法结构框图如图1所示.首先，将经过下变频的中频采样信号与本地C/A码做相乘运算.其次，将第一步得到的信号分别与同相载波cos(ωn)和正交载波sin(ωn)分量相乘，进行支路解调.再次，在一个周期或多个周期内积分累加后求平方和，再将两分量相加.最后，将上一步得到的结果与设定的检测阈值进行比较，如果相关能量值大于该检测阈值，则成功完成捕获，将此时得到的C/A码和载波频率参数传给后面的跟踪环；反之，则通过调整码相位和载波频率，重复进行以上步骤，直至捕获成功.

图1 串行搜索捕获算法结构框图

图1的计算过程表示为：

(1)

其中：f是本地载波频率，n是采样点序号，m是复现的C/A码相位偏移，R(m)是相关运算结果，L是一个C/A码周期内的采样点数，N为使用一次相关运算中使用N周期长的数据，K为进行K次相关计算.虽然串行搜索捕获计算简单，是一种非常有效的捕获算法，但它是以一定的步长遍历所有可能的多普勒频移，同时在每个频率单元内遍历所有的码相位，因此数据量和运算量都很大，致使捕获速度变慢.因此，人们提出了基于FFT快速捕获算法.

2 基于FFT的快速捕获法

GPS信号的捕获是先求输入信号与C/A码做相关运算，然后将得到的相关结果与设定的阈值门限进行对比，判断是否成功捕获到该信号，若成功则进入跟踪状态.对于离散数字信号，它的相关可以写成：

(2)

如果信号x(n)输入到一个线性时不变系统，假定该系统的冲击响应为h(n)，那么输出y(n)表示成时域卷积或者是频域的傅立叶变换形式为：

(3)

Y(K)=X(K)H(K)

(4)

因为式(2)和卷积类似，故选用相似的方法进行分析，对式(2)作离散傅立叶变换得到:

(5)

其中X(-1)(K)表示离散傅立叶逆变换(IFFT)，若x(m)为实数，则有x*(m)=x(m)，于是可得到X*(k)=X-1(K)，其中X*(K)是X(K)的共轭.同理可得到，Z(K)=H-1(K)X(K).于是

Z(K)=H(K)X*(K)=H*(K)X(K)

(6)

因此，z(n)可由Z(K)作傅立叶反变换得到，即：

(7)

通过以上公式推导，只需将相关函数中的x(n)换成GPS信号，h(n)换做本地C/A码即可完成信号捕获.在实际处理中，离散傅立叶变换一般采用快速傅立叶变换(FFT)实现.图2是基于FFT的快速捕获算法结构框图.

图2 基于FFT的快速捕获算法结构框图

在实际使用FFT快速捕获算法中，C/A码的FFT值可以提前计算好并存储在存储单元中，这样既能减少一个FFT的运算量，又能减少捕获时间.

基于FFT快速捕获的具体步骤为：

步骤1：将输入的中频信号分别与本地载波同相和正交分量相乘，并通过低通滤波器滤除高频分量，得到复信号；

步骤2：对步骤1得到的信号做傅立叶变换；

步骤3：将步骤2得到的结果和已计算好的C/A码的FFT共轭值相乘，并将乘积值做反傅立叶变换；

步骤4：对步骤3得到的结果取模并取平方，然后对结果进行门限判决，如果有相关峰值超过门限值，则说明完成了信号捕获.相关峰值所对应的位置就是伪码相位，这时本地载波的频率值就是信号的载波频率；如果没有相关峰值超过门限值，则多普勒频率步进一个单元，并重复以上步骤.

基于FFT的快速捕获算法在载波频率上采用了直接搜索方式，但在码相位上，只需进行一次FFT和一次IFFT运算，就可求出C/A码一个周期内所有采样点对应的相关值，而不用像串行搜索捕获法中将码相位逐次滑动来求相关值.假设用一个C/A码周期的数据来捕获，捕获所用的采样点数为N，当采用传统的串行搜索捕获算法时，每计算一次相关结果就需要进行N次相乘和N-1次相加，要计算所有的N个码相位，总共需要N2次乘加；采用基于FFT的快速捕获方法，需要的全部运算量大概为2次FFT的计算量，即2Nlog2N次乘加，大大减少了运算量.

本文分析的基于FFT的快速捕获算法是基于GPS系统，根据本文设定的参数，该算法需要N1=21次频率步进量(频率步进为500 Hz)，1 ms信号对应的采样点为N2=2 046，抽样后的采样频率为fs=2.046 MHz，假设FFT的延迟时间约为Tc=5μs，所以，最大捕获时间为：

(8)

而串行捕获法要进行N1=21次频率和N3=2 046个码相位的搜索，则串行捕获法的最大捕获时间为：

(9)

通过式(8)、(9)可知，基于FFT的快速捕获算法大大缩短了捕获时间.

在实际运用该方法的时候，对N个采样点进行FFT变换，因为FFT蝶形运算的递归特性，只有在N为2的整数幂条件下才能达到算法的最高效率，所以需对输入信号作预处理，可以有效解决采样点数与FFT处理的不匹配问题，但是降低了相关输出值，对噪声的适应能力下降.

3 MATLAB仿真分析

本节通过两个MATLAB仿真实验来验证基于FFT快速捕获算法的优越性.实验一是基于FFT的快速捕获算法的捕获结果，实验二是采用MonteCarlo方法来仿真分析FFT捕获算法的频偏及码偏估计性能.

实验1：基于GPS系统，C/A码长为1 023，码速率为2.046MHz，选取积分时间为1ms，即一个码周期，中频载波为4.092MHz，多普勒频率范围为±5kHz，这里假定输入多普勒频率值为1 500Hz，多普勒频率步进量为d=500Hz，时间延迟为100μs.由图3可以看到，此算法在信噪比为-15dB的条件下，仍然有很好的捕获性能，这是因为FFT具有把所有点能量集中在一个单元的特性.当出现最大相关峰值时，认为捕获到了多普勒频率值和码相位.图3中X轴表示码相位，坐标值为215，每个码相位为0.489μs，由于FFT运算会使时间延迟5.134 5μs，则信号时延为t=215×0.489-5.1345=100.005μs， Y轴表示多普勒步进，坐标值为14，则得到多普勒频率值为f=(14-11)×d=3×500=1 500Hz.

图3 基于FFT捕获算法仿真结果

基于实验1的仿真条件，多普勒步进量为500 Hz，得到多普勒频移步进单元与相关峰值的关系图如图4所示，从图4中可以看到明显的相关峰，进而判断出多普勒频率.

图4 不同多普勒频率步进的相关能量值

实验2：基于实验1的仿真条件，输入信噪比为-15 dB，加入范围内的随机多普勒频率和的随机时延，采用Monte Carlo方法，对基于FFT快速捕获方法的频偏估计性能和码偏估计性能进行评估.

由图5可知，频偏估计误差基本位于-250～250 Hz范围内，最大多普勒频移估计残差为250 Hz.实际由于信噪比较低，最大估计残差约为300 Hz.对于码偏估计，理论上精度为一个采样点的时间，即1/2046MHz=0.489 μs，由图6仿真结果可以得出，时延最大估计误差约0.30 μs，即存在约一个采样点的码相位偏移.

图5 基于FFT的频偏估计误差统计仿真结果

图6 基于FFT的时延估计误差统计仿真结果

4 结 语

本文讨论了串行搜索算法和FFT快速捕获算法的基本原理，并对两种方法进行了对比分析.通过MATLAB仿真分析了基于FFT的快速捕获算法的性能，并利用Monte Carlo方法对算法的频偏和码偏估计性能进行了统计分析.仿真结果表明，基于FFT的快速捕获算法捕获精度高，运算量小，并且在很大程度上缩短了捕获时间.

[1] 冯永新, 刘 芳, 潘高峰. 直接序列扩频信号同步新机理[M]. 北京: 国防工业出版社, 2011.

[2] PSIAKI M L. Block acquisition of weak GPS signals in a software receiver [J]. ION GPS, 2001, 9: 1-13.

[3] CHEN C, WU Y, MENG Y. Fast acquisition technology to the speatrum based on the FFT [J]. Space Electronic Technology, 2009(2): 13-18.

[4] 徐卫明, 刘雁春, 朱穆华. GPS中频信号快速捕获技术分析[J]. 测绘科学, 2007, 32(5): 98-100.

[5] 董智红, 吴嗣亮. 大多普勒偏移下直接序列扩频信号捕获新方法[J]. 系统工程与电子技术, 2008, 30(8): 1424-1426.

[6] 钟 志, 冯阳凯, 孙铭芳. 一种新的载波频率估计方法[J]. 哈尔滨商业大学学报：自然科学版, 2007, 23(3): 340-342.

[7] 王 伟, 徐定杰. 基于FFT的伪码快速捕获[J]. 哈尔滨工程大学学报, 2003, 24(6): 646-650.

[8] 薛文芳, 邵定蓉, 李署坚. GPS接收机中伪随机码快速捕获技术的研究[J]. 北京航空航天大学学报, 2003, 29(6): 489-492.

[9] 杨正民, 高玉斌. 基于FFT的扩频信号捕获仿真[J]. 中北大学学报, 2010, 31(2): 156-160.

[10] 陈 真，董丹丹.基于PMF的伪码捕获改进算法[J].哈尔滨商业大学学服：自然科学版，2015，31(4)：477-480，485.

Study on GPS signal fast acquisition algorithm based on FFT

QU Li-na1, GU Cheng-hu1, JI Qiang2

(1. School of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China;2. Shenyang Aircraft Design and Research Institute, Shenyang 110035, China)

GPS signal acquisition is one of the key techniques of GPS receiver signal processing, selecting the appropriate method can improve the performance of the receiver. The traditional serial acquisition algorithm has a large amount of calculation and the capture time is long, unable to meet the requirement of real-time processing of GPS receiver, but rapid acquisition algorithm for GPS signal based on FFT can make up for the lack of serial acquisition algorithm. This paper simulated the GPS signal fast acquisition algorithm based on FFT through the MATLAB simulation experiments. The simulation results further verified the reliability of this algorithm, and used the Monte Carlo method to verify the estimation performance of the frequency offset and partial code. The simulation results verified the validity and reliability of the FFT acquisition algorithm.

global positioning system; serial acquisition algorithm; FFT acquisition algorithm

2014-06-05.

中央高校基本科研费专项基金(HEUCF140803).

曲丽娜(1988-)，女，硕士，研究方向：扩频通信的伪码捕获和跟踪.顾成虎(1989-)，男，在读硕士，研究方向：宽带信号检测与识别，雷达信号侦察与干扰技术。

TN972

A

1672-0946(2015)05-0578-05