212 2014，50（5） Computer Engineering and Applications 计算机工程与应用 一种改进的基于 FFT 弱信号捕获算法 冯继威，石 敏，易清明 FENG Jiwei, SHI Min, YI Qingming 暨南大学 信息科学与技术学院 电子系，广州 510632 Department of Electronics, College of Information Science and Technology, Jinan University, Guangzhou 510632, China FENG Jiwei, SHI Min, YI Qingming. Improved algorithm of weak signal acquisition based on FFT. Computer Engi- neering and Applications, 2014, 50（5）：212-215. Abstract：A differential coherent accumulated acquisition algorithm based on Fast Fourier Transform（FFT）weak signal block accumulation of the intermediate frequency is presented in this paper. To reduce coherence computation, the pro- posed algorithm performs the block accumulation of the intermediate frequency signal before FFT. To solve the two prob- lems in traditional acquisition algorithms based on FFT weak signal, namely great computation of coherent integral and square loss caused by incoherent accumulation, the proposed algorithm performs the differential coherent accumulation after IFFT. The simulation experimental results show that the algorithm quickly and accurately acquires the input signal with SNR of － 39 dB/2 MHz. The algorithm reduces the calculations, eliminates square loss and improves the signal to noise ratio. Key words：Global Positioning System（GPS）; weak signal; acquisition; block accumulation of intermediate frequency; difference correlation 摘 要：提出一种基于 FFT 弱信号的中频信号块累加的差分相干累积算法。新算法利用中频信号块累加在中频信 号 FFT 之前进行累加，减少相干运算量；利用差分相干累积在 IFFT 之后进行累积，消除平方损耗，解决了传统的基于 FFT 弱信号捕获时相干积分运算量过大和非相干累加算法引起的平方损耗问题。仿真实验表明该算法完成了对输 入信噪比为－39 dB/2 MHz 的信号的快速准确捕获，减少相干运算量，消除了平方损耗，提高了信噪比。 关键词：全球定位系统（GPS）；弱信号；捕获；中频信号块累加；差分相干 文献标志码：A 中图分类号：TP391 doi：10.3778/j.issn.1002-8331.1209-0245 1 引言 近年来，全球定位系统（Global Positioning System， GPS）在军事和民用方面取得极其广泛的应用 [1-2]，用户 对其要求也越来越高。在高楼林立的街道、密封严实的 室内和树木茂密的山峡等信号微弱的环境下，能快速准 确实现定位成为衡量接收机的一个最显著的标准。在 GPS 软件接收机中，GPS 信号的捕获是最耗时最关键的 技术。该技术主要分时域相关法[3]和频域循环相关法[4]： 时域相关法属于常规法，在硬件中完成的，易实现，但运 算量大、捕获精度不理想；频域循环相关法也叫快速傅 氏变换法，适用于软件 GPS 接收机，运算量相对减少，捕 获精度相对增加，但对 GPS 弱信号很难实现快速捕获。 因此，对 GPS 弱信号捕获技术的研究在扩展 GPS 技术 应用范围上具有重要意义。目前传统基于 FFT 的 GPS 弱信号快速捕获算法 [5]及其改进是一个热门研究方向。 传统弱信号捕获主要依赖延长积分时间提高检测增益， 但相干运算量过大，同时非相干累积所造成的平方损耗 会降低信噪比进而影响到捕获精确度。为了解决这些 问题，本文通过中频信号累积技术 [6]和傅里叶线形叠加 性质，提出了基于 FFT 中频信号块累加的差分相干 [7]弱 信号捕获算法。算法通过中频信号的块累加提高算法 的运算效率，并利用差分相干累积方法提高检测增益获 基金项目：广东省突发事件应急中心项目（粤科函社字[2011]733 号）；广东高校产学研结合示范基地重大项目（No.cgzhzd1103）； 广东省工程技术研究中心项目（No.2012gczxA003）。 作者简介：冯继威（1987—），男，硕士，研究领域为卫星导航信号处理；石敏（1977—），通讯作者，女，博士，副教授，研究方向：图像 处理、IC 设计；易清明（1965—），女，博士，教授，研究方向：信号处理、ASIC 设计。E-mail：t_asic_jnu@163.com 收稿日期：2012-09-24 修回日期：2013-01-14 文章编号：1002-8331（2014）05-0212-04 

冯继威，石 敏，易清明：一种改进的基于 FFT 弱信号捕获算法 2014，50（5） 213 得合适信噪比。仿真实验结果和分析表明，该算法在信 号输入信噪比为－39 dB/2 MHz 时能快速准确捕获。 大，非相干累积所造成的平方损耗会降低信噪比。因此 新的算法需要针对相干运算量大和非相干累积降低的 信噪比提出有效解决方案。 2 基于 FFT 弱信号捕获方法 传统基于 FFT 弱信号捕获算法 [8]主要对 GPS 信号 C/A 码进行捕获，将射频模组输出的数字中频采样作为 软件接收机中输入信号，其数字表达式如下： n n n IF - τ)D(t - τ)cos[w = 2P C(t 是采样时间 t n ) 是信号中的 C/A 码；D(t y n 其中，y 率；C(t n 是伪码起始时间，表示伪码相位；w 其值由 RF 电路和多普勒频移 w 相位；V (t D n n 0 n D t + φ - (w )] + ν(t ) （1） 时刻的射频输出；P 是信号功 ) 是导航电文比特；τ 是中频载波频率， n ) 是白噪声，其功率谱密度被认为是常量 N /2 。 对数字中频信号进行某一假定多普勒频移补偿，忽 略高次谐波得到 I，Q 两路信号。假设相干积分时间为 L ms，1 ms 的中频采样数为 N。 0 决定；φ 是初始载波 0 IF 3 基于 FFT 中频信号块累加的差分相干弱信 号捕获算法 3.1 中频信号块累加 前面提到的传统捕获算法中，采用相干累积算法。 如果对 1 ms 的相干运算结果进行相干累积运算，进行 多少次相干累积就进行多少次相关运算。假设相干积 分时间为 L ms，1 ms 的中频采样数为 N，在 L ms 内相同 相位的采样点进行块累加，即每个点累加 L 次。由式（4） 和式（5）可知，传统方法有 NL 次相关运算 NL 次累加，但 是运算量巨大。 在 GPS 弱信号捕获过程中，若先将中频信号进行块 累加，再进行去载波和相关运算等，便可在减少运算量 的情况下兼顾信号处理增益，步骤分解如下： cos[(w - w' D )t n ] + v(t ) I n IF n sin[(w y n - w' D )t n ] + v(t ) n Q IF 本地伪码发生器输出 L(t ) = C(t n n ) ，则 I 和 Q 路的积 分器输出为： NL - 1 I = å y n = 0 NL - 1 Q = å n = 0 NL - 1 I ' = å y n = 0 NL - 1 Q' = å n = 0 C(t n n - τ ')cos[(w - w' D )t n ] + v(t )' I n IF C(t y n n - τ ')sin[(w - w' D )t n ] + v(t )' n Q IF 其中 τ ' 为捕获伪码初始时间，可换算成码相位；w' D 获载波频率。 ) = I ' + jQ' 组合成复信号输出为： Z(τ 'w' D 根据 FFT 相关性质[9]，式（6）转换成图 1 所示方法： Z(τ 'w' D ) = IFFT {FFT (y exp[-j(w - w' D ]) × )t IF n n （6） n - τ '))*} FFT (C(t （7） 经过以上过程之后，如果非相干结果超过判决门 限，则本星捕获成功。否则，重新对本地载波进行多普 勒频率补偿，继续捕获。 传统基于 FFT 弱信号捕获算法依赖延长积分时间 提高检测增益，算法相对简单易实现，但相干运算量过 中频信 号 y n I(t) + jQ(t) I(t) Q(t) FFT IFFT abs（） 累加 门限 判决 复共轭 本地载波 产生器 本地 C/A 码产生器 FFT 搜索控制 图 1 基于 FFT 的 GPS 弱信号捕获框图 （2） （3） （4） （5） 为捕 Ù I ' NL - 1 = ( å y Ù Q' n = 0 NL - 1 = ( å n = 0 )cos[(w n - w' D )t n ]C(t n IF - τ ') + v(t )' I n )sin[(w y n - w' D )t n ]C(t n IF - τ ') + v(t )' n Q （8） （9） 在同样假设条件下，由式（8）和式（9）可知本文所用 方法共有 NL 次累加 N 次相关运算，相比传统方法的 NL 次累加 NL 次相关运算，虽然累加次数不变都是 NL 次， 但相关运算减少 NL - N 倍。 3.2 差分相干累积算法 前面提到的传统捕获算法中，采用非相干积分法。 其将相干积分输出（同向输出和正交输出）进行平方处 理后再累加，正负电文数据位被平方，在不保留相位信 息的情况下，消除了导航比特跳变的影响，同时平方处 理去除了相位误差的影响，在理论上实现了积分时间无 限长。但是噪声也被平方导致噪声能量的增加，使处理 增益受到平方损失的影响，进而影响捕获灵敏度。针对 以上问题，目前常用的解决方法是差分相干累积算法， 其公式如下： K S = å Z *(k + 1)Z(k) = å K k = 1 I k k + 1 + Q Q ) k + 1 k k = 1 K å (I k = 1 conj(I + jQ )*(I k + 1 + jQ ) = k k k + 1 （10） 为了进一步改进算法，本文采用差分相干累积算法 消除导航比特跳变的影响在相邻数据累加时进行模处 理，其表达式为： K S = å |Z *(k + 1)Z(k)| = å K |(I k = 1 k = 1 I k k + 1 + Q Q )| k + 1 k （11） 其中，Z(k + 1) 和 Z(k) 是相邻的相干输出，通过前者的共 相乘之后再取模累加，消除了导航比特跳变的影响。 传统方法中非相干积分通过平方累加处理消除导 

214 2014，50（5） Computer Engineering and Applications 计算机工程与应用 航比特跳变带来的平方损耗影响，结构原理简单，易实 现，信号噪声均被平方处理，存在较大平方损耗。本文 采用的方法通过相邻相干输出共乘后取模累加来消除 导航比特跳变的影响，结构原理相对复杂，实现有难度， 但是，增强了信号的功率，降低了对噪声能量的增加，进 而减小了处理增益受到的平方损失，提高了信噪比。 3.3 算法框图与步骤 本文基于 FFT 的中频块累加差分相干累积算法模 型如图 2 所示，其具体步骤如下所述： 0 ca （1）对输入采样频率 f 的中频序列进 = 1 ms 码周期的累加，组合成 K 个 1 ms  载波中频 f S 行连续 L 个 T 的累加数据段，并转化成 K 行，( f ) 列的矩阵。 （2）对步骤（1）的累加结果进行本地初始频率 w = 0 Hz 同相和正交支路的载波相乘，剥离载波，并组合成 复信号。 ´ T D0 S ca （3）对步骤（2）的复信号进行 FFT 变换，并分别与本 地产生的 C/A 码 FFT 变换后的共轭信号相乘，然后进行 IFFT 变换，得到相干积分矩阵。 S （4）对步骤（3）得到的相干积分的 K ´ ( f ´ T ca 进行式（11）的差分相干累积取模处理，得到新 1 ´ ( f ) ca 矩阵并存储到对应频率的 41 ´ ( f ) 矩阵中，其中 41表 示多普勒频率范围 [ - 1010]（单位：kHz）步进为 500 Hz 的频率点。若 41 个频率点搜索完成，跳至步骤（6），否 则进行步骤（5）。 ) 矩阵 ´ T ´ T ca S S （5）对步骤（2）的输入信号进行时域频率补偿，方法 ± 500 Hz 处理，然后继续步 是依次对本地载波频率 w 骤（2）。 D （6）对差分相干累积结果的矩阵取最大相干峰值， 若超过设置门限，则本星捕获成功，得到多普勒频率和 码相位。否则，更换本地 C/A 码转入步骤（2）重新进行 搜索。 中频信 号 y n å L 个 码周 期块 累加 I(t) Q(t) 本地初始 载波 本地 C/A 码产生器 FFT 复共轭 延迟 1 ms Z * 共轭 Z k k + 1 Z IFFT 搜索控制 FFT Y (k) å | Z | Z * k + 1 k 门限判决 图 2 改进的基于 FFT 微弱 GPS 信号捕获算法 4 仿真实验与分析 在 Matlab平台下，采用 Simulink工具搭建 GPS数字中 频信号源模块，生成 GPS弱信号，其中采样率 16.368 MHz， 中频频率 4.092 MHz，量化位数 2 bit，卫星号 13，输入信 噪比－39 dB/2 MHz，码相位 9 237，多普勒频偏 5 945 Hz。 在实际捕获前信号的信噪比未知，而利用噪声统计特性 设定的捕获门限的适用范围有限，所以本文仿真采用后 处理信噪比 [10]表示最大相关值和其他码相位上的相关 均值的比值。若后处理信噪比超过捕获门限则认为成 功捕获到卫星信号。 表 1 分析了传统方法相干累加与本文所用方法中 频信号块累加在运算量上的比较。 表 1 相干累加部分的比较 累加运算 相关运算 相干累加 中频块累加 N×L N×L N×L N 在仿真实验中，L = 10 msN = 16.368 MHz 根据表 1 可以计算出本文方法在相干累加部分的运算量上是传 统方法的 1/L，即 1/10。 表 2 分析了传统的弱信号捕获方法与本文方法在 运算量上的比较。 表 2 算法运算量的比较 传统方法 本文方法 FFT IFFT 32×21×L×K 32×21×K 等效总数 672（L+1）K 32×1×K 32×41×K 1 344K 在仿真实验中，L=10 ms，K=10，根据表 2 可计算出 本文方法在 FFT/IFFT 运算量上是传统方法的 2/11。 由表 1、2 可知本文方法在减少运算量上具有优势， 理论上可以在一定程度提高捕获速度减少时间。 （1）以上参数标准，传统基于 FFT 弱信号捕获方法 仿真结果。 由图 3（a）可知该星的码相位捕获结果显示在 9 273 附近，与 GPS 数字中频信号源模块设置的码相位参数基 本符合。图 3（b）是该星的三维捕获，可知该弱信号有相 对明显的相关峰值。 （2）相同参数标准，采用本文算法进行捕获，在中频 块累加时间 L=10 ms、差分相干累积数据段 K=10、多普 勒频偏 [ - 1010]（单位：kHz）和 1 023 个码相位下搜索 该星信号。根据捕获峰值获得信噪比设置后处理信噪 比 14 dB 作为捕获门限，此时捕获的虚警概率小于 10－5。 图 4（a）可知仿真的后处理信噪比为 14.483 3 dB，超 过门限设置 14 dB，码相位是 9 273、频偏 6 000。图 4（b） 该星的码相位捕获结果与 GPS 数字中频信号源模块设 置的码相位参数相符合。图 4（c）是该星的三维捕获，可 知该弱信号有明显的相关峰值。 综上所述，可知传统基于 FFT 弱信号捕获算法可以实 现弱信号的捕获，但是对－39 dB/2 MHz 的弱信号捕获其 码相位的捕获不够精准、门限判决后的相关峰值相对不明 

冯继威，石 敏，易清明：一种改进的基于 FFT 弱信号捕获算法 2014，50（5） 215 CA 码相位捕获结果 中频信号捕获图 5 0 1 / 值 关 相 6.0 5.5 5.0 4.5 4.0 3.5 3.0 2.5 2.0 0 5 0 1 / 值 关 相 6 5 4 3 2 40 30 20 多普勒频移 0 0 0 2 0 0 0 4 0 0 0 6 0 0 0 8 0 0 0 0 1 0 0 0 2 1 0 0 0 4 1 0 0 0 6 1 码相位点 （a）传统方法码相位捕获图 卫星号： 13 码相位： 9 273 参考码相位： 捕获的最高相关峰值 1.041 9E+006 频偏： 捕获后处理信噪比 9 273 6 000 14.483 3 参考频偏： 5 945 （a）在 Command Window 中截图 图 3 传统方法捕获结果图 CA 码相位捕获结果 11 10 9 8 7 6 5 4 5 0 1 / 值 关 相 0 0 0 0 2 0 0 0 4 0 0 0 6 0 0 0 8 0 0 0 0 1 0 0 0 2 1 0 0 0 4 1 0 0 0 6 1 码相位点 15 000 10 0 5 000 10 000 码相位 （b）三维捕获图 中频信号捕获图 5 0 1 / 值 关 相 10 8 6 4 40 30 20 多普勒频移 15 000 10 0 5 000 10 000 码相位 （c）三维捕获图 （b）码相位捕获 图 4 本文方法捕获结果图 显。本文弱信号捕获方法能够实现对－39 dB/2 MHz 弱 信号的捕获，且码相位精准、频偏在允许的范围内、门限 判决后的相关峰值非常明显。 5 结束语 本文在 GPS 软件接收机的捕获方面提出了一种基 于 FFT 中频信号块累加的差分相干微弱 GPS 信号捕获 算法。该算法对中频信号进行块累加，用时域上的频域 补偿搜索，最后用差分相干累积的方法减小平方损耗提 高信噪比。实验结果表明，相对于传统的基于 FFT 的弱 信号捕获算法，该算法能准确迅速地捕获到输入信噪比 为－39 dB/2 MHz 的弱信号。 参考文献： [1] 季建玲，刘宏立.基于 GPRS/GPS 的多功能公交车载终端系 统[J].计算机系统应用，2011，20（6）：113-116. [2] 张琦.露天矿 GPS 实时动态测量验收系统[J].露天采矿技 术，2011（6）：81-83. [3] 林庆恩，茅旭初.一种用于微弱 GPS 信号处理的快速捕获 方法[J].计算机仿真，2010，27（10）：330-334. [4] 徐卫明，韦林海，王志光，等.一种基于 FFT 的中频信号捕 获方法[J].测绘科学与工程，2010，30（2）：20-23. [5] Lin W H.Acquisition of GPS software receiver using split redix FFT[C]//2006 IEEE International Conference on System Man and Cybernetics，Taibei，China，2006： 4608-4613. [6] 黎山，易清明，陈庆，等.适用于 GPS 软件接收机的弱信号 捕获方法[J].计算机应用，2012，32（3）：816-818. [7] Yu Wei，Zheng Bo，Watson R，et al.Differential combining for acquiring weak GPS signals[J].Signal Processing，2007， 87（5）：824-840. [8] Tsui J B.GPS 软件接收机基础[M].陈军，潘高峰，译.北京： 电子工业出版社，2007. [9] 胡广书.数字信号处理[M].北京：清华出版社，2010. [10] Tsui J B.Fundamentals of global positioning system receiv- ers：a software approach[M].2nd ed.New York：Wiley， 2004：72-79，258-263.