基于半比特交替和FFT组合的GPS软件接收机弱信号捕获算法

liyf

第20 卷第1 期 中国惯性技术学报 Vol.20 No.1
2012 年2 月 Journal of Chinese Inertial Technology Feb. 2012
收稿日期：2011-09-08；修回日期：2012-01-08
基金项目：自然科学基金（61004125，60874092，60904088）
作者简介：李寅寅（1987—），男，博士生，研究方向为导航、制导与控制。E-mail：[img]mailto:liyinyin19870107@126.com]liyinyin19870107@126.com
联 系 人：徐晓苏（1961—），男，教授，博士生导师。 E-mail：[img]mailto:xxs@seu.edu.cn]xxs@seu.edu.cn
文章编号：1005-6734(2012)01-0046-05
基于半比特交替和FFT 组合的GPS 软件接收机弱信号捕获算法
李寅寅，徐晓苏，刘锡祥
（东南大学 微惯性仪表与先进导航技术教育部重点实验室，南京 210096）
摘要：研究了在弱信号条件下GPS 软件接收机的捕获算法，对传统的捕获算法进行了介绍，分析了其
在弱信号捕获中的不足之处，通过块叠加的方法对传统算法进行改进，使信号检测能力得到了提高，
同时大大降低了捕获的运算量，缩短了长时间积分捕获算法的运行时间。分析了算法的积分增益和损
耗，利用假设检验的思想，根据信号分量会扩散到附近频率的事实，最大峰值和其附近±13 个频率点
上的相关值作为信号分量，以此生成信号检测量，根据此检测量来判定信号的存在。最后利用仿真的
GPS 信号在Matlab 平台上对算法进行了验证。结果表明，通过10 ms 的相干积分和5 次非相干累加，
可以成功捕获信噪比为-35 dB 左右的微弱信号，采用块叠加改进后，算法的运行时间缩短了1/3 以上。
关 键 词：GPS；捕获；半比特；FFT；块累加；相干积分
中图分类号：U666.1 文献标志码：A
Acquisition algorithm based on half-bit alternation and FFT
combination for weak signals of GPS software receiver
LI Yin-yin, XU Xiao-su, LIU Xi-xiang
(Key Laboratory of Micro-inertial Instrument and Advanced Navigation Technology, Ministry of Education,
Southeast University, Nanjing 210096, China)
Abstract: Acquisition algorithm of software GPS receiver for weak signals is studied. Traditional acquisition
algorithm is presented and its drawbacks are analyzed. The traditional algorithm is improved by the method
of block addition, and this improves the ability of detecting signal and reduces the computing amount of
acquisition as well as the executing time of long-time integration acquisition algorithm. The integral gain and
loss of the algorithm are analyzed, and the algorithm is verified with simulated GPS signal in Matlab. Based
on hypothesis test theory, the way of deciding the presence of signal is introduced which shows that the
signals are spread over other ±13 frequency-points. And the signal can be detected based on this way.
Simulation results indicate that feeble signals with SNR of -35 dB or so can be acquired through 10 ms
coherent integration and 5 times of incoherent addition, and the block addition can effectively reduce the
executing time by 1/3 compared to that of the former algorithm.
Key words: GPS; acquisition; half bit; fast Fourier transform(FFT); block addition; coherent integration
随着全球定位系统(GPS)的推广应用，人们对其重
要组成部分——GPS 接收机提出了更高的要求，要求
其在高楼林立的城市中心、树木遮挡的森林公路甚至
室内等信号微弱的环境下，依然能够快速的实现定位。
而在这些环境下，传统的接收机往往不能正常工作。
传统的接收机一般只能工作在信号较强的环境下，载
噪比(carrier noise ratio, C/No)一般高于43 dB-Hz，而
在恶劣的条件下C/No 均在36 dB-Hz 以下[1-2]。
捕获就是使接收机本地参考码和接收到的码的相
位差小于一个码元宽度，同时使载波频率基本一致，
实现输入信号与本地信号的粗同步。为了能够捕获微
弱的信号，传统的串行相关捕获算法通过累加多个C/A
第1 期 李寅寅等：基于半比特交替和FFT 组合的GPS 软件接收机弱信号捕获算法 47
码周期时长的数据来提高捕获的灵敏度，但这将导致运
算量的急剧增加[2]，进而导致接收机的首次定位时间
(TTFF, Time To First Fix)变长，影响接收机的性能。因
此，开发有效的微弱信号快速捕获算法，提高微弱信号
下接收机的捕获能力成为改进接收机性能的首要工作。
本文采取半比特交替法与FFT 并行码相位捕获结合的
方法对载噪比低于36 dB-Hz 的GPS 信号进行捕获，并
对其算法进行了改进使其运行效率得到提高，通过对实
际和仿真的信号进行处理，对算法进行了验证。
1 传统的GPS 信号捕获算法
捕获的主要任务是寻找相对于接收机可视的卫星
的信号，并测出该卫星信号的C/A 码初始相位和载波
频率，为了完成这些功能，接收机通常采用串行时域
相关(常见于传统的硬件接收机)和并行的频域相关捕
获算法(主要用于软件接收机)，由于本文的研究是基
于软件接收机实验平台的，因此只对频域的并行码相
位捕获方法进行介绍。串行时域相关捕获方法可以参
考文献[3-6]。
并行码相位搜索算法的原理如图1 所示[4-6]。
I
Q
图1 并行码相位搜索算法框图
Fig.1 Search algorithm of parallel code phase
设输入的中频数字信号r(n) 为：
0 ( ) ( ) ( )sin[( ) ] ( ) d r n ? Ad n c n ? ?? n ?? ? v n (1)
式中，A 为信号幅度，d(n)为调制的导航数据，c(n)
为C/A 码， 0
? 为中频载波角频率， d
? 为多普勒频移
角频率，? 为载波初始相位，v(n) 为带限高斯白噪声。
由于? 未知，为了抵消本地载波相位与输入载波相位
的偏差，采用同相支路I 与正交支路Q 相结合的方法
剥离载波， I 路和Q 路的本地载波分别为：
,
0 sin[( ) ] d ? ?? n ?? 和 ,
0 cos[( ) ] d ? ?? n ?? ，则经过载波
剥离后的输入信号可以表示为：
( ) ( ) ( ) ( ) exp{ ( , ) } d d x n ? I n ? jQ n ? r n ? j ? ?? n (2)
对其进行FFT 变换可得：
[X (1), X (2),?, X (L)]T ? FFT{[x(1), x(2),?, x(L)]T}
(3)
设本地 C/A码为c(n) ，对其进行 FFT 变换并取共
轭可得：
[C(1),C(2),?,C(L)]T ? conj{FFT{[c(1),c(2),?,c(L)]T}}
(4)
将 X(k)与C(k) 相乘并对其乘积取傅里叶逆变换可得：
, , , T
T
[ (1, ), (2, ), , ( , )]
IFFT{[ (1) (1), (2) (2), , ( ) ( )] }
d d d y y yL
X C X C XL CL
? ? ? ?
? ? ?
?
?
(5)
式中，L 表示1 msC/A 码周期内数字采样点个数，则
[ (1, , ), (2, , ), , ( , , )]T d d d y ? y ? ? y L ? 就表示在 ,
d
? 频点上输
入信号与本地信号的在所有码相位上的相关结果，将
串行时域相关中串行执行的步骤并行实现了[4]。通过比
较所有的相关结果，找出最大值，若最大值大于设定的
检测门限，则判定捕获成功，并给出最大值所在的码相
位和多普勒频移值，若没有检测到信号，调整到下一个
频点，继续上述过程，如果所有设定的频点上都没有检
测到信号，则判定没有捕获到指定卫星的信号，程序将
捕获另外一颗卫星的信号，重复上述过程。
对于一般强度的信号，采用上述的常规算法在一
个C/A 码的周期里进行运算就可以实现信号的捕获，
但在微弱的信号环境下很难捕获到信号，这就需要采
用针对微弱信号的捕获算法。
2 基于半比特交替与FFT 组合的弱信号捕获算法
微弱信号的捕获主要是通过相干积分加非相干积
分的方法提高捕获的灵敏度[4]，用于相干积分的数据
长度越长，则获得的积分增益越高，也即捕获的灵敏
度越高，由于受到导航数据跳变的限制，相干积分的
数据长度不能超过20 ms。在不借助外部辅助的情况
下(如AGPS)，数据跳变的位置是未知的，因此，通
常可选的相干积分长度最大为10 ms[4]，同时选择下一
个10 ms 的数据作为备用，如果其中一个10 ms 数据
中含有导航数据跳变，则另一个10 ms 数据将不包含
跳变，这就是半比特捕获的基本思想。通过相干积分
所获得的额外增益为：
10 lg( ) cG ? ? n (6)
式中，n 为相对于1 ms 的数据长度，由公式(6)可见，
相干积分方法获得的额外增益与所用的数据长度之间
的关系是呈对数线性的，因此相干积分所用的数据越
长，获得的额外增益越多，10 ms 的相干积分获得的
额外增益为10 dB，文献[7]提出了针对一个导航数据位
(20 ms)进行相干积分的方法，即全比特捕获算法，如
前所述，20 ms 的数据中包含数据跳变的可能性很大，
若所用的数据中包含跳变，将使相干积分的增益受到
48 中国惯性技术学报 第20 卷
很大的衰减，相干积分的输出能量将会扩散到附近的
频率分量。因此全比特捕获算法要对所有可能的跳变
进行估计，将输入数据依次滑动1 ms 产生20 组20 ms
长的数据，对这20 组20 ms 长的数据进行依次进行捕
获，产生20 组结果，如果没有跳变，20 组输出的幅
度应当接近，如果有跳变，则20 组输出中最大的应当
为20 ms 数据中没有跳变的情况[7]。由此可见，全比
特捕获算法的计算量是很大的，在实际的工程应用中
得到应用是很难的。
通过对10 ms 的数据进行相干积分只能获得10
dB 的相干积分增益，对于捕获载噪比在34 dB 以上的
GPS 信号足够了，但是要获得更高的捕获灵敏度，就
要借助非相干积分的方法[4]。非相干积分利用若干个
相干积分产生的输出累加来获得额外信噪比增益的,
通过将一组长的输入数据分成许多块，并对每块进行
相干积分操作，相干积分之后，每个输出频率分量都
是复数，计算其幅度，把同一频率的所有相干积分的
幅度相加，结果是，弱信号被增强，就可以获得较高的
信噪比。由于非相干积分中用到了平方操作，信号的幅
度在得到增强的同时，噪声的幅度也得到了增强，信噪
比受到了一定的衰减，此即平方损耗，因此非相干积
分所累加的相干积分数目不是越多越好，是要受到限
制的。非相干积分的损耗可以通过公式(7)进行计算
1 1 9.2 / (1)
( ) 10 lg[ ] dB
1 1 9.2/ (1)
c
c
n D
L n
D
? ? ?
? ?
? ?
(7)
式中，Dc (1)为在特定虚
警概率和特定检测概率
下的理想检测因子。这
里取虚警概率为10e-7，
检测概率为0.9，此时
(1) 21 c D ? [4]。
非相干积分增益等
于相干积分增益减去非相干积分损耗[4]，可以通过公
式(8)进行计算：
( ) ( ) ( ) 10lg( ) ( ) i c G n ? G n ? L n ? n ? L n (8)
由公式(7)可知，非相干积分的损耗随着非相干积
分的数目增长而增长，相应的由公式(8)可知，非相干
积分增益的增大是有限的；同时，随着非相干积分数
目的增多，计算量也增大，因此对于非相干积分数目
的选取，应折中考虑。
本文采用半比特方法，用100 ms 的中频数据进
行微弱信号捕获。将完成载波剥离的100 ms 的数据分
成5 个20 ms 的数据块，每个数据块分成前10 ms 和
后10 ms 两部分。分别对5 个数据块中的前10 ms 进
行相干积分，然后将五个10 ms 的相干积分结果进行
非相干累加；同样，对5 个数据块中的后10 ms 数据
进行同样的操作，这样就得到了两组结果，其中一组
肯定不包括导航数据跳变。
本文对10 ms 的相干积分采用的也是基于FFT 的
循环相关的方法，这样就可以将码相位搜索并行化，
但是对于10 ms 的数据进行FFT，其运算量依然很大，
同时，1 ms 的数据即可覆盖整个码相位周期，因此没
有必要对10 ms 的数据进行全部相关，只需要循环移
位1 ms 的数据点即可。基于上述考虑，本文采取文献
[8]所提出的块累加的方法，对算法进行改进。由于FFT
运算是线性运算，即两个序列的FFT 变换之和等于序
列之和的FFT 变换[9]，因此基于块叠加的运算不会影
响最终的相干积分结果。具体实现过程如下：
1）在特定的多普勒频移点上对100 ms 的数据进
行载波剥离；
2）将100 ms 剥离载波的数据分成5 个20 ms 数
据块，将每个数据块分成前10 ms 和后10 ms 两部分，
如图2 所示。
3）将数据块A、B、C、D、E 中的数据块1 累
加成1 ms 长的数据块，称为A1、B1、C1、D1、E1；
将五个数据块中的第二部分数据累加成1 ms 数据块，
称为A2、B2、C2、D2、E2。
4）分别对A1、B1、C1、D1、E1 进行FFT 操作，
并将FFT 结果分别与本地C/A 码的共轭FFT 相乘，
对相乘结果进行快速傅里叶逆变换，即可得到5 个10
ms 数据的相干积分结果，对5 组相干积分结果求平
方，然后将平方结果累加成1 ms 长的结果；对A2、
B2、C2、D2、E2 进行同样的操作，这样就得到了两
组相干加非相干积分的结果。
5）分别取两组结果中的最大值，比较两个最大值
的大小，较大的一个所在的数据块组为没有导航数据
跳变的组，对该组结果进行捕获判决。整个算法的原
理图可以用图3 表示。
3 捕获的判决方法
常用的捕获判决方法是基于假设检验的方法，在
第1 期 李寅寅等：基于半比特交替和FFT 组合的GPS 软件接收机弱信号捕获算法 49
恒虚警概率准则下，利用噪声的统计特性，根据要求的
检测概率设定捕获的判定门限[4]，如果捕获的相关峰值
超过门限，即判定信号存在，捕获成功，否则判定没有
捕获到信号。但是，在实际中，捕获之前并不知道信号
的信噪比，利用噪声统计特性设定捕获判定门限对于不
同环境并不通用[10]。用输出信噪比作为信号检测的统
计量在实际中更为合适，不用考虑输出分布情况。
本文所用的检测方法为：相干积分用10 ms 的数
据，在非相干积分之后，得到时域结果，由于输出的
信号会扩撒到邻近的频率点上，因此本文将最大输出
及其附近的±13 个频率点的输出看作所要的信号，将
其余的输出，均看作噪声。检测信号功率ds P 和检测噪
声功率dn P 定义为：
13
2
13
frq
ds i
i frq
P s
?
? ?
? ? ， 2
dn
N
P ??n N (9)
式中， s 表示输出中的信号部分，其下标i 表示频率
点，j 表示相位点，n 是单个噪声分量，N 是总噪声分
量。对于本文所用到的中频数据，当：
dB ( ds ) 10 lg( ds ) 14.1 dB
dn dn
P P
P P
? ? ≥ (10)
即判定捕获到信号，否则判定没有捕获到信号，此时
可以得到检测概率与虚警概率较好的组合。
4 实验验证和分析
文中的仿真数据是根据实际的GPS L1 频段C/A
码的信号特性和相应的中频信号参数，用Matlab 语言
生成，其生成的仿真信号便于设置输入的信噪比，便
于算法的验证，同时可以避免其他非相关因素的影响，
其主要参数如下：
数字中频频率：4.123 968 MHz；
中频采样频率：16.367 667 MHz。
由于C/A 码信号的输入带宽是2.046 MHz，在这
一带宽下，标称的输入信噪比为-19 dB。结合公式(6)、
(7)和(8)，可得相干积分结合非相干积分方法所能捕获
到的信号的信噪比可以按下式计算：
dB (SNR) ? L(n) ?19 ?10? lg(m) ?10? lg(n) (11)
式中，m 为相干积分的毫秒数，n 为非相干积分的个
数。针对本文的情况，m=10，n=5，根据上述公式可
以得出算法能够捕获到的信号的信噪比能够达到-35
dB，为了验证这一理论，根据信噪比的计算公式：
dB (SNR) 20 log( ) n ? ? A ? (12)
这里A 是信号的幅度，本文的仿真数据中A 为1， n ?
为噪声的标准差，根据公式(12)可以得出n ? 为55。产
生一组标准差为55 的高斯白噪声叠加到仿真信号上，
即可产生信噪比为-35 dB 的信号。本文的算法将采用
这一仿真信号进行验证。
图4 为第18 号卫星的捕获结果，图4（a）显示有
明显的相关峰存在，根据公式(10)计算捕获检测量为
17.66，超出门限14.1，证明捕获到了该卫星的信号。
图4(b)和图4(c)分别为码相位维上的相关峰和频率维
上的相关峰，最大相关值处的码相位和频率点分别为
3670（即1023×3670/16 368 为18 号卫星的初始码相位）
4126 518 Hz（对应第192 频点，多普勒频移为2550 Hz）。
图5 为采用普通的捕获方法对同样的仿真信号进
行捕获的结果，可以看出没有明显的相关峰，信号完
全被噪声淹没。
本文对采用快累加改进后的算法进行了运行时间
的测试，对仿真的18 号星的信号进行处理，所用的PC
机的配置为：Pentium(R)4.3GHz 的处理器，内存为1G；
改进前后的处理时间对比可见表1 所示。由表1 可见，
采用块累加的方法对算法进行改进，在保证捕获灵敏度
不受影响的情况下，其运行的效率得到了很大的提高，
这为弱信号捕获算法能够用于工程实际提供了依据。
表1 改进前后算法的执行时间对比
Execution time of algorithm before and after improving
所用算法 平均执行时间/s
未采用块累加改进的捕获算法 980
采用块累加改进的捕获算法 281
I
Q
? ?2
图3 改进的捕获算法流程图
Fig.3 Flow chart of the modified acquisition algorithm.
50 中国惯性技术学报 第20 卷
5 结 论
本文研究了基于半比特交替法解决导航数据跳变
对相干积分的影响，使得相干积分的时间得以扩到10
ms 长，同时结合非相干积分的方法，使得捕获算法的
灵敏度得到进一步的提高，文中对相干积分加非相干
积分的方法所能够获得的积分增益进行了分析；通过
采用FFT 的方法，使得码相位搜索得以并行化，进一
步通过块累加方法对算法进行改进，可以使算法的执
行效率得到很大的提高。仿真结果表明，通过10 ms
的相干积分并进行5 次非相干累加可以获得16 dB 的
增益的改善，使得算法能够捕获到信噪比为-35 dB 左
右的微弱GPS 信号；基于块累加方法改进后的算法，
其运行时间缩短了1/3 以上。本文的研究也有不足之
处，实验结果是基于仿真的GPS 信号得出的，忽略了
在实际中的非相关因素的影响，同时没有研究多普勒
频移对C/A 码的影响，这些将是未来研究的重点。
参考文献（References）：
[1] 翟传润，张婧. GPS 软件接收机微弱信号捕获算法研究
[J]. 电子测量技术， 2008，31(5)：137-140.
ZHAI Chuan-run, ZHANG Jing. Algorithm for weak
signal acquisition in GPS software receiver [J], Electronic
Measurement Technology, 2008, 31(5): 137-140.
[2] 陈学，徐建华，叶甜春，李思超. 基于FFT 的微弱GPS
信号捕获算法[J]. 微电子学与计算机，2010，27(3)：98-101.
CHEN Xue, XU Jian-hua, YE Tian-chun, LI Si-chao.
FFT-based acquisition for weak GPS receiver[J].
Microelectronics & Computer, 2010, 27(3): 98-101.
[3] Ganguly S. FFT based block processing receiver for fast
acquisition[C]// Proceedings in 2007 Joint Navigation
Conference. Orlando, FL, 2007: 235-246.
[4] O'Driscoll C, Petovello M G, Lachapelle G. Software
receiver strategies for the acquisition and re-acquisition of
weak GPS signals[J]. Journal of Guidance, Proceedings of
the Institute of Navigation, National Technical Meeting,
2008: 843-854.
[5] 唐康华，吴美平，胡小平. 基于射频前端的GPS 软件接收
机设计与验证[J]. 中国惯性技术学报，2007，15(1)：51-54.
TANG Kang-hua, WU Mei-Ping, HU Xiao-ping. Design
and validation of GPS software receiver based on RF
front-end [J]. Journal of Chinese Inertial Technology,
2007, 15(1): 51-54.
[6] 徐晓苏，范金洋. GPS 软件接收机捕获算法[J]. 中国惯
性技术学报，2009，17(2)：165-169.
XU Xiao-su, FAN Jin-yang. Acquisition Algorithm of
GPS Software Receiver[J]. Journal of Chinese Inertial
Technology, 2009, 17(2): 165-169.
[7] Mao Wei-Lung, Chen An-Bang. New code delay
compensation algorithm for weak GPS signal acquisition
[J]. AEU-International Journal of Electronics and
Communications, 2009, 63(8): 665-677.
[8] Heckler G W, Garrison J L. Experimental tests of unaided
weak signal acquisition methods using a software
receiver[C]// Proceedings of the Institute of Navigation -
19th International Technical Meeting of the Satellite
Division, ION GNSS 2006: 1309-1320.
[9] Yang Liu, Tian Jin. Analysis and compare of weak GPS
signal acquisition algorithms[C]// IET International
Communication Conference on Wireless Mobile and
Computing. Shanghai, China 2009: 492-495.
图5 普通的捕获算法结果
Fig.5 Result of the conventional acquisition of satellite 18
(a)
(b)
(c)
图4 18 号卫星的捕获结果
Fig. 4 Acquisition results of satellite 18】
基于半比特交替和FFT组合的GPS软件接收机弱信号捕获算法.pdf (804.92 KB, 下载次数: 0)

2014-10-1 07:26 上传

点击文件名下载附件
下载积分: 银子 -10 两