2 2 小 型 微 型 计 算 机 系 统 Journal of Chinese Computer System s GPS信号串行捕获算法研究 武建锋 1, 2 ,胡永辉 1 ,蔡成林 1, 2 1 (中国科学院 国家授时中心 ,陕西 西安 710600) 2 (中国科学院 研究生院 ,北京 100049) E m ail: w ujianf@126. com 2 2010年 1月 第 1期 Vol 31 No. 1 2010 摘 　要 : 传统串行搜索算法在时域内对所有可能的频点和相位进行串行搜索 ,搜索的过程只需要加法和乘法运算 ,无论是在硬 件还是软件中都容易实现 ,在 G PS接收机设计中得到大量应用. 但由于串行搜索算法在实际接收机中实现时 ,捕获过程需要大 量的相乘 、累加运算 ,需要较长的捕获时间. 文中从降低相乘和累加运算个数入手 ,提出一种改进算法 ,使得捕获速度得到明显 提高. 利用 M A TLAB 分别对传统的和改进的算法进行了算法仿真 ; 根据信号捕获理论结合仿真实验结果 , 对两种算法进行了 比较和分析 ,认为改进算法可以有效的应用于 G PS信号捕获 ,而且提高了捕获的速度. 该算法对于其它系统的伪随机码捕获也 是适用的. 关 键 词 : 时域 ; 相乘累加 ; 抽取 ; 串行搜索 ; 捕获时间 中图分类号 : TP391　　　　　文献标识码 : A 　　　　　　文 章 编 号 : 1000 1220 ( 2010) 01 0186 04 Study on the Ser ia l Search A lgor ithm for GPS S igna l feng1, 2 , HU Yong W U J ian 1 (N a tiona l Tim e Service Center, C hinese Academ y of Sciences, Xi′an 710600, C hina) 2 ( G radua te U niversity of C hinese Academ y of Sciences, B eijing 100049, China ) hui1 , CA I C heng lin1, 2 Abstract: The serial search algo rithm searches for a satellite sequen tially at each p ossible code delay and D opp ler shift in tim e dom ain. it is easy to im p lem en t in tim e dom ain. Th is app roach has been ex ten B ecause on ly add ition and m ultip lication operations are needed, sive app lications in G PS receivers. B ecause the serial search algo rithm has to do m uch glide co rrelation in a real G PS receiver, this exhausting correlation also tends to be the m ain w eakness of the serial search acquisition. To overcom e the sho rtage of the serial search algo rithm , It can decrease the a m ount acquisition tim e efficien t. the serial search algo rithm w ill becom e m ore feasib le and p opu lar. The rev isited algo rithm aim s at not on ly the G PS signal, but also is suitable for o ther CDM A system s. Key words: tim e dom ain; addition and m u ltip lication; sam p le; serial search; acqu isition tim e the ob jective of the study is to sho rten the co rrelation tim e, and a new algo rithm is g iven. If this algorithm is im p lem en ted in civ il G PS receivers, 1　引 　言 G PS卫星信号采用组合码调制技术 ,将卫星导航电文经 伪随机码扩频成为组合码 ,再对 L 频段的载波进行相移键控 调制. 采用这种格式不仅提高了系统导航定位的精度 ,并且使 系统具有很高的抗电子干扰能力和极强的保密能力 , 而所用 的关键技术是伪随机码的扩频技术. 在 G PS 用户端 , 实现对 伪随机码的捕获至关重要 , 对其捕获算法的研究一直是 G PS 接收机研究的一个热点. 2　传统串行搜索捕获算法原理 G PS信号主要的捕获算法有三种 :串行搜索捕获算法 、循 环相关捕获算法以及延迟与累积捕获算法. 串行捕获算法一 般都在时域内用硬件实现 [ 1, 2 ] , 它对可能存在的码相和频点 进行串行搜索 ,由于其在时域中很容易实现 ,在实际设计中得 到大量应用. 循环相关捕获算法是一种基于快速傅立叶变换 ( FFT)的算法 [ 3 5 ] ,是在频域内实现信号的捕获 , 这种算法的 捕获速度优于传统的滑动捕获算法 ,但由于 FFT在硬件上实 现时难度较大 、比较耗费资源等缺点 ,因此在普通接收机中应 用不多 ,而在软件接收机中应用较多. 延迟与累加算法的出发 点是消除输入信号中的频率信息 [ 3, 6 ] ,只需要用本地 C /A 码 去搜索输入信号 C /A 码的起始点 , 找到起始点后 , 可由 FFT 或 D FT得到其频率 ,从理论角度上看 , 这是个非常吸引人的 方法 ,但是运用到实际 G PS 信号处理中 , 还需要做进一步研 究. 前面提到 ,串行捕获算法在实际中应用较多 ,但缺点是捕 获速度较慢 ,捕获时间较长. 本文从降低捕获时间的角度出 发 ,提出一种改进的串行捕获算法 , 可以有效地提高捕获速 度 ,降低捕获时间. G PS 信号的捕获是基于 PN 码的自相关特性 , 捕获过程 是对所有的可能信号搜索单元进行搜索估计 ,确定信号是否 　　收稿日期 : 2008 01　基金项目 :中科院青年专项资助项目资助 ; 湖南省自然科学基金项目 ( 07JJ6105)资助. 　作者简介 :武建锋 ,男 , 1976 年生 ,硕士 ,助理研究员 ,研究方向为高动态 、多模卫星导航算法 ; 胡永辉 ,男 , 1952年生 ,研究员 ,研究方向为时间统一系统 , GPS导航、定位、授时 终端研究 ; 蔡成林 ,男 , 1969年生 ,硕士 ,副教授 ,研究方向为全球定位系统的局域和广域差分增强技术. 08 

1期 　　　　　　　 武建锋 等 : GPS信号串行捕获算法研究 　　 781 出现的过程. 其过程为 :接收机本地信号发生器调整码相位与 多普勒频移估计 ,使产生的信号对准某一搜索单元 ,信号检测 器开始进行检测 ,若信号未超过捕获阈值 ,则码相位步进一单 元 ,信号检测器继续进行检测 ,重复上述过程 ,直到信号超过 捕获阈值 ,则捕获成功 ,停止搜索 ,进入跟踪环 ; 若整个码域搜 索完毕信号仍未捕获 ,则多普勒频移估计步进一个单元 ,重复 上述过程. 假定输入信号用 5M hz数字化 ,最大多普勒频移 ± 5KH z,频率搜索步长一般选为 500H z, 搜索频点为 21个. 串 行捕获算法在实际接收机中的结构图如图 1所示 [ 3, 7 ]. 输入信号为经过下变频的中频信号 ,表示为 s ( t) = AC ( t) D ( t) cos [ 2π ( fIF +Δf) t + ( 1) 式中 , A 为信号幅度 , C ( t)是数值为 ±1的伪随机码信号 , D fIF为中频频率 ,Δf ( t)是数值为 ±1的数据码 , 频率为 50H z, 0 为初始载波相位. 输入信号经过 5M H z数 为多普勒频移 , 字化采样后 ,表示为 : 0 ] sIF ( tk ) = AC ( tk ) D ( tk ) cos [ 2π ( fIF +Δf) tk + (2) 1m s内产生 5000个点 ,本地产生的载波信号 、C /A 信号为了 实现与它对应相乘 ,也就必须 1个 m s内产生 5000个点. 中频 数据分别与本地同相载波和正交载波相乘进行支路的解调 , 解调后的中频信号再与本地 C /A 码信号相乘完成信号的解 扩 ,经过积分累加后 ,第 i次相关后输出为 : 0 ] 量的相乘累加工作 ,这是影响捕获时间的重要原因. 从图 1可 以看到 ,输入信号经 5M H Z采样后 , 1m s将产生 5000个点 ,这 5000个点包含了一个完整的码周期. 本地 C /A 码信号为实现 和它对应 , 在 1m s 内也必须产生 5000 个点 , C /A 码周期为 1m s, 1023个码片 ,码频为 1. 023 ×106M H z. 对这 1m s的数据 在一个频点上进行捕获需要的相乘累加运算个数为 : 1023 ×( 5000乘法操作 + 5000 加法操作 ) , 1023 为基码 码片个数. 如果搜索完 21个频点 ,总共需要的相乘累加运算 个数为 : 21 ×1023 ×( 5000乘法操作 + 5000加法操作 ). 很显然这 是一个很大的数 ,是影响捕获时间的重要因素. 下面提出一种 基于抽取的滑动捕获算法 ,在不影响捕获结果的前提下 ,可以 有效地降低相乘累加运算个数. 对于 G PS的 C /A 码信号 ,周期为 1毫秒 ,如果采样频率 是 5M H z,那么 1m s内将产生 5000个采样数据点 , 而这 5000 个点必然包含了一个完整的 C /A 码周期. 这 5000个点是由 1m s上 1023个 C /A 码片上采样得到的 ,图 2所示为 C /A 码 信号经 5M H z采样后的实际结果. I ( i) ≈ 0. 5AD ( i) R (τi ) Q ( i) ≈ 0. 5AD ( i) R (τi ) s in (πΔfi T) πΔfi T s in (πΔfi T) cos (Δ i ) πΔfi T s in (Δ i ) (3) (4) Δfi 为多普勒频移估计残差 ,τi 为码相位偏差 , R (τ)为伪 i 为载波 随机码理想的自相关函数 , T为预检测积分时间 ,Δ 相位. 信号检测采用包络检测器 ,检测值通过下式确定 : H ( i) = I2 ( i) + Q2 ( i) = 0. 25A2 R2 (τi ) s in2 (πΔfi T) (πΔfi T) 2 (5) 由上面的公式分析可知 ,相关峰值 H ( i)随码相位误差和多普 勒频移估计误差的降低而增大. 利用这个原理 ,设定检测阈值 Ta ,对 H ( i)和阈值进行比较 ,当相关峰值 H ( i)超过 Ta 之后 , 图 1　传统串行捕获算法实现框图 F ig. 1 B lock diag ram of the conven tional acqu isition algorithm 就认为本地码和接收码已基本对正 , 此时接收机本地码不再 在频域和时域上与接收到的码相对滑动 , 开始进入伪码和载 波的跟踪过程. 3　基于抽取的串行搜索捕获算法 图 2　C /A 码片上采样结果 Fig. 2　R esult of C /A up sam p led 对于 C /A 码的码片来说 , 5000 /1023 的结果是 4. 89, 则 采样数据有以下两种可能 :一个 C /A 码码片采样 5个点 ; 二 是一个 C /A 码码片采样 4 个点. 假设采样起始时刻与 C /A 码第 1个码片严格对齐时 ,共有 908个基码片采样为 5个点 , 115个基码片采样为 4个点. 如果每 5个点抽取 1个 , 可以得 到 1000个点 ,但丢失了 23个码相 , 这种抽取是不可行的. 采 取每 4个点抽取 1个 , 可以得到 1250个点 , 包含了一个完整 的 C /A 周期. 经过抽取后 ,共有 227个基码片采样为 2个点 , 796个基码片采样为 1个点 , 经过捕获后得到的基码相位公 式为 : n ×1023 /1250,其中 n为对应 1250点的滑动捕获结果. 基于上面抽取的思想 ,改进的捕获算法结构图如图 3所示. 输 入信号经过与本地同相载波和正交载波相乘进行支路的解调 后 ,进行 4 个取 1 的抽取 , 在 1m s 内的 5000 点下降到 1250 点 ,本地 C /A 在 1m s内不用产生 5000个点 , 产生 1250个点 即可. 在一个频点上进行捕获需要的相乘累加运算个数为 : 1023 ×( 1250乘法操作 + 1250加法操作 ) ,搜索完所有的 频点的相乘累加运算个数为 : 在实际的接收机中 ,传统的串行搜索捕获算法需要做大 21 ×1023 ×( 1250乘法操作 + 1250加法操作 ) ,运算量降 

2 　　　　　　 881 小 　型 　微 　型 　计 　算 　机 　系 　统 　　　　　　2010年 低为原来的 1 /4,理论上说可以将捕获时间提高 4倍. 对于一般的情况 ,假设采样频率为 fsamp le , 码率为 fcode , 则 在改进的捕获算法中 ,输入信号经过与本地同相载波和正交 载波相乘进行支路的解调后 , 对其采用每 ceil ( fsamp le / fcode )个 点抽取一个的方法 ,其他部分保持不变 ,这种对码抽取的思想 对于基于 FFT捕获的算法也是适用的. 收的数字中频的中心频率 ( 1. 405M H z)和预设的载波多普勒 频率合成决定. 捕获算法分别按图 1和图 3的算法框图实现 , 先实现载波解调 ,然后实现码解扩 ,经过累加平方后对相关峰 值进行检测. 在仿真程序中如果相关峰值大于噪声低限 6db 时 ,认为已经捕获到相关峰. 图 5是两种算法相关器的频响比较. 图 3　改进后的串行捕获算法实现框图 Fig. 3　M od ified acqu isition algo rithm 4　算法仿真实验与分析 为了对前面所作的分析进行仿真验证 ,本文在 M A TLAB 环境对 G PS信号的码捕获过程进行仿真 ,仿真数据采用真实 的 G PS中频信号数据 , 采样频率 5M hz, 用 2 B it的精度分别 对采样信号的符号和幅度进行量化 , 最终得到 1. 405M hz包 含符号和幅度的数字化中频信号 , C /A 码频 1. 023M hz, 仿真 实验主要针对相关器频响 , 码相捕获结果 , 捕获时间做出比 较. 此次 G PS信号搜索和捕获过程的仿真实验分别对时域串 行搜索捕获方法和改进的时域串行搜索捕获方法分别进行 M atlab仿真. 仿真实验软件部分由 M atlab实现 ,主要模块有 G PS C /A 码序列和载波序列仿真 、信号搜索及捕获和实验结果数据处 理输出. 图 4为其软件设计流程示意图. 图 5　频响比较图 Fig. 5　C om parison of frequency resp onse 常规相关器的频响为 1 M 　　　　Gc ( fd ) = s in (πfd TsM ) s in (πfd Ts ) 其中 , Ts 为采样周期 , fd 为载波多普勒频偏 , M 为 C /A 码码 长 1m s内对应的积分累加点数. 对于传统的算法 , M = 5000, Ts = 1 /5e6; 对于本文所提出的算法 , M = 1250, Ts = 4 /5e6. 从 图中可知 ,两者的归一化的频响图是一致的 ,即改进算法对相 关器的频率响应没有影响 ,没有降低捕获频率的分辨率. 图 4　软件设计流程图 Fig. 4　Flow chart of softw are design 实际仿真实验过程中 ,为了提高信号搜索捕获的效率 ,所 有 G PS卫星 ( 1 32)的一个周期的 C /A 码序列事先在 M atlab 中分别生成后存入一个文件供需要时调用. 对于图 1中传统 算法的情况 ,本地 C /A 码序列必须从 1023点上采样到 5000 个点. 对于图 3中改进算法的情况 , 本地 C /A 码序列必须从 1023点上采样到 1250个点. 本地载波的生成同样根据 G PS 信号搜索捕获原理 , 由 M atlab生成两路正交的正弦和余弦数字序列 ,信号频率由接 图 6　捕获的码相比较 Fig. 6　C om parison of acquisition code phase 图 6中 ( a) 、( b)分别为两种方法对 8号 G PS卫星的搜索 捕获结果. 表 1所示为两种算法所得捕获参数. 

2 1期 　　　　　　　 武建锋 等 : GPS信号串行捕获算法研究 　　 981 传统串行搜索算法捕获结果 ( a)中 , 峰值处对应的码相 为 501,转换到基码码相为 : 501 ×1023 /5000≈ 103. 在图 ( b) 中 ,峰 值 处 对应 的 码 相 为 126, 转换 到 基 码 码 相 为 : 126 × 1023 /1250≈ 103. 两者所得的码相是一致的 ,即改进算法是可 行的 ,可以得到与传统串行搜索算法相同的捕获结果. 在图 ( a)中所得峰值为 6 ×106 ,噪底值为 1. 6 ×105 ,峰值 与噪底值之比为 37. 5; 图 ( b)中峰值与噪底值之比为 25,与图 ( a)相比有所下降 ,这主要是因为每 4个点抽取 1个点致使一 些能量损失 ,但在大多情况下为了提高捕获时间 ,这种能量损 失是可以容忍的. 1250点的滑动相关无论是在硬件中实现还 是在软件中实现都比 5000点的滑动相关速度更快. 表 1　捕获的参数 Table 1　A cqu isition p aram eters 码相 (采样 ) 基码码相 峰值 6 ×106 7 ×105 102. 5046 103. 1184 501 126 噪底 1. 6 ×105 2. 8 ×104 传统 改进 的减少计算量 ,减少捕获时间 ,提高捕获速度. 5　结束语 本文对 G PS 信号的传统串行搜索算法进行了详细讨论 , 提出一种基于抽取的改进算法 , 并从理论上以及仿真实验中 证明了改进算法的可行性和合理性. 仿真结果表明 ,改进后的 串行搜索算法有效的减少相乘累加个数 ,减少捕获时间 ,提高 捕获速度. 本算法已在作者设计的 G PS 软件接收机的硬件相 关器中得到应用 ,实验结果表明 ,该算法是行之有效的 , 该算 法的抽取思想也可以应用于 FFT捕获的情况 ,这有待于进一 步研究. 这种改进的串行搜索算法对 GLONA SS、GAL IL EO、 北斗导航接收终端的研发工作具有很好的借鉴作用. References: [ 1 ] Parkinson B , Sp ilker J. G lobal positioning system : theory and ap p lication [M ]. W ashington D. C. : A IAA , 1996. [ 2 ] N esreen I Ziedan. GNSS receivers for w eak signals [ M ]. N or w ood, M A : A RTECH HOUSE, 2006. 图 7所示为两者的捕获时间比较 ,图中对搜索 1个频点 [ 3 ] Tsui J B Y. G lobal positioning system receiver: a softw are ap 到 21个频点都进行了统计 ,图中纵坐标 log10 (计算时间 ). p roach [M ]. N ew York: John W iley & Sons, 2000. [ 4 ] V annee D J R, Coenen A J R M. N ew fast GPS code acquisition technique using FFF [ J ]. E lectronics L etters, 1991, 27 ( 17) : 158 160. [ 5 ] S tarzyk J, Zhu Z. A veraging correlation for C / A code acquisition and tracking in frequency dom ain [ C ]. MW SCS. Fairborn, O hio: 2001, 905 908. [ 6 ] L in D M , Tsui J B Y. A cquisition schem es for softw are GPS re ceiver[ C ]. Proc. ION GPS. N ashville, 1998, 317 325. [ 7 ] Kai B orre, D ennis M A kos, N Icolaj B ertelsen, et al. A softw are defined GPS and galileo receiver[M ]. B oston: B irkhauser, 2007. [ 8 ] Zhang Yong, L in B ao jun, Xu Zhi han. S tudy on sim ulation of signal search and acquisition in softw are G PS receiver[ J ]. of System S im ulation, 2006, 18 ( 9) : 2646 264. Journal 附中文参考文献 : [ 8 ] 张 　勇 , 林宝军 , 徐志瀚. 软件 GPS 接收机信号搜索捕获的仿 真实验研究 [ J ]. 系统仿真学报 , 2006, 18 ( 9) : 2646 2649. 图 7　捕获时间比较 F ig. 7　C om p arison of acqu isition tim e 从实际的统计数据来看 ,改进算法比传统串行搜索算法 快 3. 95倍. 随着需要捕获的频点数的增加 , 改进算法的优势 越来越明显 ,当搜索频点数达到 21个时 ,改进算法可以节约 7. 5秒的捕获时间. 从以上的实验结果可以看出 ,基于抽取的 改进算法可以实现和传统算法一样的功能 ,优点是可以有效