FFT在导航信号捕获中的应用分析∗

徐 浩 曾芳玲（电子工程学院合肥230037）

FFT在导航信号捕获中的应用分析∗

徐 浩 曾芳玲
（电子工程学院合肥230037）

针对伪码捕获过程中，传统的滑动相关捕获方法存在捕获时间长，捕获精度低等问题，选择了将FFT应用于伪码捕获中，提高了捕获的时间以及速度。并对两种方法进行分析比较和仿真验证，证实了FFT的使用大大减少了捕获时间，提高了捕获速度。最后对于在FFT捕获过程中的问题，提出了一些改进措施。

相关；FFT；运算量；捕获时间

ClassNumber TN927.1

1 引言

全球定位系统（GPS），是一种典型的直接序列扩频系统，它可以为用户提供全天候、连续、实时、高精度的位置、速度和时间（PVT）服务［1］。而这一切服务的基础，从本地接收机方面来看，便是来源于对GPS信号的捕获，信号捕获成功之后才能进行接下来的跟踪、观测量提取和定位解算等。

GPS是直扩系统［2~3］，而且导航星一直处于高速运动状态，接收机与卫星之间有很大的距离，这就使得接收到的信号产生很大频率的偏移以及码相位的偏移，对GPS信号的捕获就是对伪码相位偏移和频率偏移的粗确定。

传统的相关捕获算法，虽然实现比较简单，硬件资源占用比较少，但是其运算量很大，因此相应的捕获时间也会很长，无法满足实时性的要求［4~5］。根据数字信号处理的知识，进行L点相关的结果可以通过使用2次FFT和1次IFFT求得，这使得运算量下降，捕获时间减少，满足实时性的要求，这种方法是基于FFT捕获方法。

2 传统的相关捕获方法

传统相关捕获方法是利用伪码的优良的自相关特性［6~7］，将本地信号与接收信号做相关处理，对相关结果进行门限检测，超过门限则完成捕获；否则将本地码移位，继续进行相关和峰值检测，直到峰值超过阈值。

2.1 捕获原理及时间分析

对GPS信号的捕获是二维的捕获过程，那么捕获过程中就要进行二维的搜索，一维是多普勒频移的搜索，另一维是伪码相位的搜索，每一次二维的搜索为一个搜索单元。如图1所示。

接收机采用相关技术进行捕获，捕获的成功与否就是通过匹配程度来衡量。在频率和伪码相位的二维搜索中，通常情况下，码的匹配度阈值δt£ 0.5个码元，多普勒频率的阈值δf一般设定为250Hz，当两者同时满足要求时，认定捕获成功。对应二维捕获过程中的搜索单元设定为δf×δt，D F表示的是多普勒频率的搜索范围，也就是捕获时本地载波与接受信号频率的最大偏差，D F表示要搜索的伪码相位范围，也就是本地伪码和接受信号伪码之间的最大偏差。因此捕获时要搜索的最大的单元个数为

其中NC为搜索的最大单元个数，PEA表示的是虚警概率，PD为检测概率，τ(PEA×PD)表示的是在虚警概率为PEA，检测概率为PD的条件下每个搜索单元的驻留时间。

2.2 捕获过程及计算量分析

根据二维捕获原理，需要对信号进行频率和码相位的二维搜索［9］，其捕获过程如图2所示。

信号捕获时，首先将接收信号分为I路和Q路两路分别处理，之后将两路信号分别与本地载波相乘，一方面是对多普勒频率的搜索，另一方面是完成载波剥离，之后将剥离载波后的信号与本地伪码进行相关运算，经过积分和累加滤波器（IDF）进行累加，然后把两路的积分和进行平方后相加，最后进行阈值的比较。若超过阈值，则捕获成功，否则将调整本地载波和伪码相位，重复以上步骤，直到捕获完成。

时域相关法和FFT方法除伪码相关模块外，其余的模块进行的处理相似，运算量也大致相等，所以研究运算量之间的关系时主要针对码相关模块。根据相关捕获流程图，对包含L个码元的信号，完成一个单元搜索时，需完成L次乘法和L-1次加法。在一个载波频率下要完成所有L个码元相位的搜索，需要的计算量为L2次乘法和L() L-1次加法。为了保证频率匹配度在δf以内，那么应当以2δf为步进频率要完成D F频率范围内的搜索，需要完成的加法计算量MAC1为

由此可知，当码元个数确定时，其加法运算量和乘法运算量的大小均与频率搜索范围成正比；当频率范围确定时，加法运算量的大小和L()L-1的乘积正比例关系，乘法运算量的大小和码元个数的平方成正比。

3 基于FFT的捕获方法

3.1 FFT捕获原理

实现从时域到频域的转换进行捕获，其理论原理是基于信号的互相关、线性卷积以及循环卷积之间的关系［10~11］。对于两个信号x(n)和h(n)，它们之间的L点互相关函数为

而对于一个线性时不变的系统，两者的线性卷积为

根据两者的关系，可以推得：

另外L点的循环卷积Rxh(k)是线性卷积rxh(k)以L为周期的周期延拓序列的主值序列。循环卷积定义为［12］

由上边的几种关系，可以得到信号相关和信号FFT之间存在如下的关系：

根据上式将时域相关运算转换到了频域进行计算，2次FFT和1次IFFT运算可以求得相关结果，减少了运算量，提高了捕获速度。

3.2 基于FFT捕获过程

根据FFT和信号相关之间的关系，将信号捕获过程中的时域运算转换到了频域，其捕获流程如图3所示。

与时域相关捕获相似，将接收信号分为I和Q两路，然后分别进行频域搜索和载频剥离。但不同的是载频剥离后，将两路信号混频得到I+jQ，之后对I+jQ进行FFT变换，同时对本地伪码信号也进行FFT变换，并取共轭，将两者进行相乘后的结果，进行FFT反变换。最后将反变换的结果求和相加，进行阈值判决，若大于阈值，则捕获成功，否则调整载波频率和伪码相位重新捕获，直到捕获成功。

3.3 运算量和捕获时间分析

FFT的运用使得信号捕获过程中的运算量以及捕获时间大大减少，原本相关过程中的多次乘法以及加法运算，现在只需进行2次FFT和一次IFFT运算就可以完成。同样只考虑伪码的相关过程模块，对于拥有L个码元的信号，完成在一个频率上的所有码元相位搜索，需要的运算量为2次FFT，1次IFFT，而通常情况下本地码的FFT可以在捕获之前已经完成并储存，认为只进行2次FFT变换的运算量就可以。1次的L点FFT变换需要进行复数加L logL2次，需要进行复数乘0.5×L次。两个2加法器构成1个复数加，3个加法器4个实数乘法器构成一个复数乘。那么以2δf为步进频率要完成D F频率范围内的搜索，所需的加法运算量为

根据上式，基于FFT的信号捕获过程其加法运算量和乘法运算量的大小与频率搜索范围成正比，与搜索的码元个数成正比，但是比例关系却是比时域相关运算少很多，这也是FFT减少运算量的根本原因。

用TD表示进行1次FFT所用的时间，那么完成捕获所需要的最长时间，即搜索完所有频率才捕获到的时间为

最短的用时，即一次频率搜索就捕获到的用时为

4 两种捕获方法的比较分析

4.1 运算量的比较

为了保证比较更加合理，必须要保持两种方法是在同样的搜索频率范围，和同样的码元个数下进行比较。另外通过上边的分析，可以明显发现两种方法的运算量差别主要来源于码元个数L。对于一般接收机来说，通常产生的多普勒频移在±10KHz内，因此我们取搜索范围D F=20KHz。为保证频率匹配度在250Hz之内，那么频率步进为500Hz。表1和表2分别给出了在L分别等于512、1024、2048时加法运算量和乘法运算量的大小比较。

表1 加法运算量的比较

表2 乘法运算量的比较

为了更加直观的显示运算量的差异，使用MATLAB进行了仿真，仿真结果分别如图4所示。

结果显示无论是加法还是乘法，在运算量上基于FFT的方法要比时域相关捕获法少几个数量级。也就是说FFT的应用使得捕获过程中的计算量大大降低。并且捕获码元数越多，计算量相差越大。

4.2 捕获时间的比较

进行时间比较时，为使比较更加合理，仍然选定频域范围是20KHz，频域搜索步进为500Hz，码元搜索步进为1个码元。那么同样对于L个码元而言，设定积分累加时间为1ms，而相应的1次傅里叶变换时间在系统频率下不会超过1ms。根据捕获平均时间计算公式，在一定的范围内，码元个数的改变对FFT方法捕获时间的影响极小，对相关捕获影响比较大。表3给出了码元个数为512、1024和 2048时的用时比较。

表3 两种方法的捕获时间比较

其仿真结果如图5所示。

根据仿真结果，在捕获时间上，基于FFT捕获方法的用时相比相关捕获方法少二到三个数量级，甚至更多。并且码元数越多，两者相差时间越大。

5结语

导航信号捕获过程中，相关捕获方法，虽然计算量大，捕获时间较长，但是实现简单，使用硬件资源较少，资源利用率高。FFT的应用减少了运算量，也使捕获时间减少了几个数量级，更加满足了信号捕获的实时性要求，但是也存在硬件要求高，资源消耗高，利用率低功耗大的缺点。因此对于捕获方法，还有根据目的性和综合各方面的考虑，选择最优化的方法。

［1］邱致和，王万义.GPS原理与应用［M］.北京：电子工业出版社，2002：45-56.

［2］尚晓琉，胡修林，杨灵.直接序列扩展频谱通信系统仿真［J］.系统工程与电子技术.2003，25（2）：154-159

［3］Akopian，D.Fast FFT based GPS satellite acquisition methods［J］.IEEE Proceedings-Radar，Sonar and Naviga⁃tion，2005，152（4）：277-286.

［4］蔡凡，尹燕，张秀忠.GPS接收机的中频信号处理算法研究［J］.天文学进展，2007，25（1）：84-95.

［5］张勇，林宝军，徐志翰.软件GPS接收机信号搜索捕获的仿真实验研究［J］.系统仿真学报，2006，18（9）：2646-2649.

［6］Chen Zhiguo，Chen Pei，Han Chao.GPS signal acquisi⁃tionmethodsusing sample-basedshiftingand FFT［J］.Per⁃vasive Computing Signal Processing and App lications，2010，9：1005-1008.

［7］陈熙源，张昆鹏.基于MATLAB的GPS软件接收机捕获与跟踪算法实现［J］.中国惯性技术学报，2007，8：423-426.

［8］李菊，陈禾，金俊坤，等.基于FFT的两种伪码快速捕获方案的研究与实现［［J］.电子与信息学报，2006，28（10）：1778-1781.

［9］魏玲玲，范胜林.高灵敏度GPS软件接收机捕获算法［J］.指挥控制与仿真2012，10：50-54.

［10］胡广书.数字信号处理理论算法与实现［M］.北京：清华大学出版社有限公司，2003：33-54

［11］AbdulqadirTracking forAlaqeeli，Janusz Starzyk，Frank van Graas.Real-time Acquisition andGPS receivers［J］. Circuitsand Systems，2003，5：500-503

［12］赵琳，高帅和，丁继成.基于FFT的高动态GPS信号捕获方法优化［J］.系统工程与电子技术，2011，33（01）：151-156.

那么基于FFT的捕获方法，平均捕获时间是：

Application Analysisof FFT in Navigation SignalAcquisition

XU Hao ZENG Fangling
（SchoolofElectronic Engineering，Hefei 230037）

Aiming at the problem that the traditional sliding correlation acquisitionmethod has long capture time and low ac⁃quisition precision in the process of pseudo-code acquisition，the FFT is applied to the acquisition of PN code，and the acquisition time and accuracy are improved.The analysisand comparison of the twomethodsand the simulation results show that the FFTmeth⁃od greatly reduces the acquisition time and improves the acquisition speed.Finally，some improvementmeasuresare put forward in the processof FFT acquisition.

correlation，FFT，computation，capture time

TN927.1 DO I：10.3969/j.issn.1672-9730.2017.05.009

2016年11月7日，

2016年12月20日

徐浩，男，硕士研究生，研究方向：导航与定位和卫星信号捕获。曾芳玲，女，教授，博士生导师，研究方向：导航与时统。