基于组合FFT的多核北斗软件接收机并行捕获算法

曾庆喜，张鹏娜，祝雪芬，潘树国，裴 凌

（1. 南京航空航天大学 车辆电子研究中心，南京 210016；2. 东南大学 仪器科学与工程学院，南京 210096；3. 上海交通大学 北斗导航与位置服务上海市重点实验室，上海 200240）

基于组合FFT的多核北斗软件接收机并行捕获算法

曾庆喜1，张鹏娜1，祝雪芬2，潘树国2，裴 凌3

（1. 南京航空航天大学 车辆电子研究中心，南京 210016；2. 东南大学 仪器科学与工程学院，南京 210096；3. 上海交通大学 北斗导航与位置服务上海市重点实验室，上海 200240）

目前数字信号处理器已经由单核系统发展为多核并行系统，可通过并行执行任务加快信号处理速度。北斗CB2I码是GPS C/A码码长的两倍，若使用传统捕获算法将会延长信号捕获时间。基于此问题，提出了一种基于组合 FFT的并行捕获算法。该算法将信号奇偶点分开进行并行处理，可将单次FFT变换点数减半，并通过高效利用多核资源加快信号捕获速度。为了验证算法性能，对比了传统算法和改进后算法的PTP值。仿真结果表明，两算法PTP均值分别为2.961和2.938，改进后算法未降低捕获精度。最后，以多核嵌入式平台为基础分析了两算法的单核运算量，结果表明：当待处理的信号点数由1000增加到256 000时，改进后算法单核乘法运算量减少比例由33%增加到了40%，而加法计算量始终减少50%，改进后算法可达到快速捕获的效果。

软件接收机；北斗B2信号；快速捕获算法；组合FFT

智能车辆是一个集规划决策、自动驾驶等于一体的综合系统，涉及环境感知、导航定位及决策控制等科学领域，受到世界各国的高度重视。卫星定位导航技术是智能车辆不可缺少的关键技术之一，北斗卫星导航系统是我国正在实施的自主发展、独立运行的全球卫星导航系统，目前已经逐渐开始应用于汽车导航领域。为了保证无人驾驶车辆导航的可靠性，现多采用卫星导航和多个辅助传感器配合使用来增强系统的稳定性[1]。因此要求卫星定位接收机具有良好的开放性便于与其他传感器信息进行深度耦合来进一步提高定位导航精度。软件接收机基于通用嵌入式平台，可深入到接收机信号通道内部控制卫星信号的处理过程，具有良好的开放性，现已成为未来定位接收机的发展方向。随着卫星信号长度的增加和接收机处理算法的复杂化，对信号处理平台处理性能的要求也越来越高。为了满足信号处理系统的硬件实现需求，数字信号处理器（DSP）已经从一开始的单处理器多板卡系统发展为现在的多处理器并行系统，大大提高了算法运算速度。2015年德州仪器对多核DSP大点数FFT运算时间做了测试，相较于单核运算多核运算性能均有了不同程度的提高，其对比如图1所示[2]。因此通过改进卫星信号捕获算法合理的利用嵌入式平台的硬件资源，将能达到快速捕获的效果。

图1 多核运算性能对比Fig.1 Multi-core computing performance comparison

本文在分析了北斗 B2信号结构及调制原理和传统并行码相位算法的基础上，提出了基于组合FFT的北斗B2信号快速捕获算法。该算法可将单次FFT运算点数减半，将信号处理任务合理的分配到不同核中并行处理，可有效减少信号捕获时间，为后续北斗软件接收机嵌入式实现提供理论基础。

1 北斗B2信号结构

2013年12月，中国卫星导航系统管理办公室公布了北斗卫星导航系统空间信号接口控制文件公开服务信号（2.0 版），正式阐述了北斗B2信号的结构、基本参数、测距码特征和导航电文格式等相关内容[3]。不同于 GPS信号的相移键控( Binary Phase Shift Keying，BPSK)调制方式，北斗二代采用正交相移键控( Quadrature Phase Shift Keying，QPSK)的调制方式，由调制在I支路的普通测距码（C码）和调制在Q支路的精密测距码（P码）、导航电文机载波组成。其数学模型为：

式中：上角标j表示卫星编号；AB2I、AB2Q分别为I、Q支路信号强度；CB2I、CB2Q为I、Q支路伪随机码，DB2I、DB2Q为I、Q支路导航电文；fB2为B2信号载波速率，大小为1207.14 MHz；φB2I、φB2Q为信号I、Q支路载波初相。由于Q支路为授权信号，不对民用开放，因此本文只研究I支路信号。

在软件接收机基带信号处理算法开发过程中，需要卫星号、载噪比等各种参数确定的数字中频信号用于测试算法的性能。因此，本文使用Matlab软件产生伪随机码和载波信号，通过叠加噪声、带通滤波等处理模拟产生北斗卫星中频信号。图2为北斗卫星中频信号产生流程图。

图2 北斗中频信号产生流程图Fig.2 Flowchart of Beidou intermediate frequency signal generation

北斗B2信号I支路信号结构与GPS L1信号结构相似，均采用码分多址的信号复用方式。不同的是B2信号CB2I码由11个线性移位产生，L1信号C/A码由10个线形移位寄存器产生，CB2I码速率是C/A码速率的两倍，两信号周期相同，因此CB2I码是C/A码长的两倍。为了保证信号捕获的精度，相应的 B2信号采样频率较L1信号也会有所提高。

2 现有的算法以及存在的问题

卫星信号经射频前端下变频、重采样后，由软件接收机完成信号捕获工作。传统的信号捕获算法有顺序搜索捕获算法、并行频域捕获算法和并行码相位捕获算法。由于并行码相位捕获算法计算量较小，实时性较好，目前软件接收机广泛采用该算法对卫星信号进行捕获。该算法由Nee D.V.于1991年提出，其将码相位的时域相关运算通过FFT运算转换为频域的乘法运算，从而很大程度上降低了算法的运算量，提高了捕获速度[4]。算法原理如下所示。

两个长度为N的有限序列x(n)与h(n)的时域相关形式如式(2)所示，其中x(n)、h(n)分别对应输入信号和本地测距码CB2I，N为一周期内信号的采样点数。

长度为N的有限序列x(n)的离散傅里叶变换为

根据公式(2)和公式(3)可将时域相关运算转换为频域相乘运算，具体过程如式(4)所示：

式中，H*(k)为H(k)的复共轭。

利用公式(5)即可得到信号时域相关结果。基于FFT的并行码相位捕获算法只需对多普勒频率进行一维搜索，无需对信号码相位进行顺序搜索，从而很大程度上降低了算法的运算量。

基于FFT的并行码相位捕获算法原理图如图3所示：第一步，根据卫星信号中频频率和多普勒频移范围确定本地载波频率fd和搜索步长，并对输入中频信号进行去载波操作得到混频信号；第二步，取1 ms混频信号和本地测距码h(n)进行 FFT变换和取共轭操作，得到X(k)和H*(k)；第三步，将两信号FFT结果相乘，通过频域相乘运算得到频域相关结果Y(k)；第四步，对频域相关结果Y(k)进行IFFT操作，即可得到该频率下信号捕获码相位结果。如果相关结果超过所设门限值，则捕获成功，否则调整本地载波频率重复上述操作。

由并行码相位捕获算法原理图可知FFT运算是算法的核心，当单次FFT运算的点数较大时，算法的运算复杂度和硬件的实现难度都会有所增加，进而影响信号捕获的实时性。

北斗B2信号CB2I码码速率是GPS L1信号C/A码速率的两倍，为了保证信号捕获的精度需提高信号采样频率，这样将使捕获算法运算量大大增加。本文中设置的中频信号采样频率为18.073 MHz，每个CB2I码周期（1 ms）就有18073个采样点，计算量较大硬件资源耗费较高，不利于卫星信号的实时处理。

图3 传统并行码相位算法原理图Fig.3 Traditional parallel code phase acquisition algorithm

2012年，文献[5]将FIR滤波器原理与并行码相位捕获算法相结合对 GPS L1信号进行了捕获[9]，并在FPGA平台上实现了该算法，达到了快速捕获的效果。但该算法基于 FPGA硬件逻辑结构，不利于发挥软件接收机的灵活性。2013年，文献[6][7]将分段FFT算法应用到了GPS L2C信号的捕获中，有效解决了信号FFT运算点数较大的问题[5-6]。该算法可有效减少单次 FFT运算点数，但算法组合结果步骤较复杂，B2信号CB2I码是CM码码长的1/10，使用该算法将增加捕获算法的复杂度。同年，文献[8]提出了基于分段折叠算法的北斗 CB2I码快速捕获算法，通过折叠信号可将算法处理点数减半，加快信号捕获速度。但是该算法在折叠过程中也引入了噪声，降低了捕获算法的灵敏度，在信号较弱的环境下将无法使用。针对上述算法存在的问题，本文提出一种基于组合FFT的并行捕获算法。

3 基于组合FFT的并行捕获算法

3.1 算法原理

2005年Marvi Teixeira将DFT矩阵因式分解应用到了循环卷积算法中，减小了单个循环矩阵的维数[9]。将该思想与传统并行码相位捕获算法相结合可减少单次FFT变换的点数，达到快速捕获的目的。

算法具体原理如下所示：首先对式(2)中y(n)进行z变换，将结果由频域变换到复频域，如式(6)所示：

同时Y(z)可表示为

同理有：

将式(2)带入式(6)有：

将公式(8)带入公式(9)中有：

当i为0时为偶序列频域值，当i为1时为奇系列频域值。

得到Y0(k)与Y1(k)后通过 FFT逆变换即可到时域相关结果y0(n)与y1(n)。

将y0(n)、y1(n)进行组合得到最终捕获结果。以y0(n)为例分析信号相关运算的过程。由式(12)可知，在频域内Y0(k)为混频信号偶序列与测距码偶序列对应相乘，再与奇序列对应相乘值做加和；对应在时域内，两信号偶序列与偶序列做互相关运算，奇序列与奇序列做互相关运算，然后再进行加和。两信号互相关运算过程如图4所示。

图4中，当n增加1时，测距码奇序列与偶序列均向左移动一位，相应地作相关运算的两序列相对于原序列移动了两个采样点。当n=m时，y(n)代表第m个采样点处两信号的相关值，yi(n)则代表第2m+i个采样点处的相关值。基于上述分析，y0(n)、y1(n)组合方式如式(15)所示，y(n)为最终捕获结果。

图4 B2信号相关运算过程Fig.4 B2 signal correlation operation process

3.2 算法实现步骤

算法实现步骤及原理图如图5所示。

图5 基于组合FFT的并行捕获算法原理图Fig.5 Parallel acquisition algorithm based on combined FFT

步骤 1：首先根据接收卫星信号中频频率和多普勒频移范围确定本地载波频率fd和搜索步长，产生本地载波信号和本地伪随机码h(n)，并对输入信号x(n)进行去载波操作产生混频信号。然后，将混频信号和本地测距码奇偶采样点分开，分别h0(n)构成奇序列x1(n)、h1(n)和偶序列x0(n)、h0(n)。

步骤2：对x1(n)、x0(n)、h1(n)并行进行FFT和IFFT变换，将信号由时域变换到频域，其中IFFT变换等同于对序列进行FFT变换再取共轭操作。

步骤3：通过融合算法获得相关结果Y0(k)、Y1(k)。

步骤4：对Y0(k)、Y1(k)进行IFFT运算得到时域相关结果y0(n)、y1(n)，将时域相关结果组合得到信号最终捕获结果y(n)。当y(n)峰值超过门限值时，则捕获成功，未超过门限值时则改变载波频率重复步骤1到步骤4过程。

由步骤2和式(12)(13)可知，基于组合FFT的并行捕获算法单次FFT变换点数为N/2，相比于传统算法减少了一半。从算法原理图可知，四个N/2点序列独立进行FFT变换中间没有数据交换，因此可利用多核数字信号处理平台并行对四个序列进行FFT变换，可有效利用多核嵌入式平台资源加快信号捕获速度[10]。

4 算法性能分析

4.1 算法仿真结果

根据第一节模拟产生北斗B2中频信号的方法，用Matlab仿真出北斗中频信号，信号相关参数如表1所示。仿真信号一周期内时域波形和时域自相关图如图6所示。

表1 北斗卫星中频信号相关参数Tab.1 Parameters of Beidou intermediate frequency signal

图6 北斗B2信号时域波形和自相关图Fig.6 Waveform and correlation of Beidou B2 signal

使用组合FFT并行捕获算法对北斗B2中频信号进行捕获。设置输入信号码相位位于第 1547个码片处，多普勒频率偏移为 1 kHz。卫星信号最终捕获结果如图7、图8所示。图7(a)、图7(b)为y0(n)与y1(n)结果，图7(c)为y0(n)与y1(n)组合结果。从图7中显示的峰值数据可知，y0(n)第6831个采样点处的相关值大于y1(n)第6832个采样点处的值，因此最终捕获码相位位于第6831×2=13662个采样点处，即位于第(13662/18073)×2046≈1547个码片处，与预设码相位相同。图8为多普勒频移图，峰值位于第12个采样点处。在捕获算法中设置的多普勒频移范围为±10 kHz，搜索步长为1 kHz，因此该采样点处对应的多普勒频移值为(12-11)×1 kHz =1 kHz。与预设多普勒频率偏移 1 kHz相同，改进后算法可成功地对北斗 B2信号进行捕获。

图7 北斗B2信号捕获码相位图Fig.7 Code phase diagram of B2 signal

图8 多普勒频移图Fig.8 Doppler shift map

4.2 算法灵敏度对比

信号时域的相关运算对应频域的相乘运算，FFT变换可将信号由时域变换到频域。为了验证组合 FFT运算与传统基 2-FFT运算具有相同的运算结果，分别基于传统FFT和组合FFT对北斗B2信号测距码进行自相关运算，当组合FFT运算与基2-FFT变换结果不同时，CB2I码自相关值也将有所区别。为了便于观察，将码相位设置在第10001个采样点处。CB2I码自相关结果如图9所示，由图形峰值显示值可知，自相关值相同，因此组合FFT与传统基2-FFT变换结果相同，组合FFT在将信号由时域变换到频域的过程中未引入误差。

图9 CB2I码相关结果Fig.9 Correlation result of CB2Icode

为了对比改进后算法与传统算法的捕获效果，本文引入峰峰值PTP（最大相关峰值和次相关峰值的比值）对两算法捕获性能进行分析。首先模拟产生100 ms北斗B2信号，相关参数如表1所示。使用两捕获算法对该信号进行捕获。如此循环一百次，可得到2×100个PTP值，如图10所示，

图10 两算法PTP值Fig.10 PTP values of two algorithms

图10中水平虚线表示两算法的平均PTP值。经计算，基于组合FFT的并行捕获算法PTP平均值为2.938，传统捕获算法PTP平均值为2.961。两者捕获效果基本相同，改进后算法未降低捕获灵敏度。

4.3 运算量及处理速度分析

为了对比传统捕获算法和基于组合FFT并行捕获算法的信号处理速度，均以多核信号处理器平台为基础，分析两算法的总运算量和单核运算量，其中单核运算量对应算法的执行时间[11]。

由算法原理图图5可知，基于组合FFT的并行捕获算法并未减少算法整体处理的信号采样点数，而是通过减少单次FFT变换点数，多核并行处理的方法加快了算法处理速度。因此两算法总运算量相当。

当基于组合FFT的并行捕获算法在多核嵌入式平台上实现时，算法计算量较大的FFT和IFFT部分可由四核并行进行处理[12]。计算量较小的部分如去载波、组合结果等可由主核完成。当在多核嵌入式平台上实现传统捕获算法时，其FFT运算部分执行流程与改进后算法类似，均可利用多核进行处理。不同的是，由图3及图5可知，传统算法同时对两个N点序列进行FFT变换，改进后算法同时对四个N/2点序列进行FFT变换。由于单个FFT变换序列各点间运算相互关联，因此仅可由多核数字信号处理平台中单核完成N点序列的FFT变换，两个N点序列FFT变换可由双核并行完成。同样，去载波等运算量较小的操作由主核完成。相应的两算法执行过程中对于的运算量如表2所示。当信号采样频率为18.073 MHz时，一个周期内的采样点数为 18073，对于基-2FFT算法，需将信号采样点数补0为2的次幂，因此32768，ceil()为向右取整函数。此时传统算法单核加法次数为983 040，乘法次数为557 056；组合FFT并行捕获算法单核加法次数为491 520，乘法次数为344 064。在该采样频率下，加法运算量减少了约 50%，乘法运算量减少了约38%。

当信号的采样频率或者所需处理的信号周期数发生变化时，即捕获算法处理的信号采样点数发生变化时，两算法单核乘法计算量变化趋势如图11所示。

图 11包含了两算法单核乘法计算量的对比和改进后算法单核乘法次数减少的比例。由图11可知，随着算法处理的采样点数由1000增加到256 000，改进后算法乘法次数减少比例由33%增加到了40%，加法运算次数始终减少50%左右。当时钟频率相同时，基于组合FFT的并行捕获算法相较于传统算法处理时间也将会相应减少。基于多核的软件接收机即可达到快速捕获的目的。

表2 两算法总运算量和单核计算量对比Tab.2 Comparison on total computational load and single-core computational load of two algorithms

图11 同采样点下两算法单核乘法计算量变化趋势Fig.11 Single-core multiplication calculation’s trend of two algorithms with different sampling points

5 结 论

本文针对北斗 B2信号测距码码速率高于 GPS C/A码码速率，采样频率较高，使用传统算法捕获速度较慢的问题，提出了基于组合FFT的并行捕获算法。该算法将单次FFT变换点数减少为原来一半，可有效利用多核嵌入式平台的资源，加快信号捕获速度。而在进行快速捕获的同时，算法并未降低信号捕获精度。仿真结果表明传统算法与改进算法PTP值基本相同。

最后，本文以多核嵌入式平台为基础分析了两算法的运算量，结果表明：当算法单次处理的信号点数由1 000增加到256 000时，改进后算法单核乘法运算量减少比例由33%增加到了40%，而且加法计算量始终减少50%。因此，改进后算法可达到快速捕获的目标，提高了软件接收机初始定位速度。

（References）：

[1] Wang Hong-yu, Zhang Xiao-xia, Li Xiao-lin, et al. GPS/DR information fusion for AGV navigation[C]// World Automation Congress Proceedings. IEEE Computer Society. 2012: 1-4.

[2] Texas Instruments. Very large FFT for TMS320C6678 processors[Z]. 2015: 1-5.

[3] 中国卫星导航管理办公室. 北斗卫星导航系统空间信号接口控制文件公开服务信号[M]. 2.0版. 北京: 中国标准出版社, 2013. China Satellite Navigation Office. BeiDou navigation satellite signal in space interface control document open service signal[M]. Version 2.0. Beijing: China Standardization, 2013.

[4] Nee D V. A New Fast GPS Code-acquisition technique using FFT[J]. Electronic Letters, 1991, 27(2): 158-160.

[5] Leclère J, Botteron C, Farine P A. Improving the performance of the fft-based parallel code-phase search acquisition of GNSSS signals by decomposition of the circular correlation[C]//25th International Meeting of the Satellite Division of the Institute of Navigation ION. Nashville TN, 2012: 1406-1416.

[6] 曾庆喜, 唐琳琳, 王庆, 等. 基于分段FFT的GPS L1/L2C信号快速捕获算法[J]. 中国惯性技术学报, 2013, 21(5): 640-645. Zeng Qing-xi, Tang Lin-lin, Wang Qing, et al. Algorithm of GPS L1/L2C fast acquisition based on segmented FFT[J]. Journal of Chinese Inertial Technology, 2013, 21(5): 640-645.

[7] Zeng Qing-xi, Tang Lin-lin, Huang Yu-hua, et al. GPS L1 aided fast acquisition of L2C signal based on segmented split-radix FFT[J]. Journal of Chinese Inertial Technology, 2015, 23(1): 93-97.

[8] 曾庆喜, 徐亮, 唐琳琳, 等. 基于分段折叠算法的北斗CB2I码快速捕获[J]. 中国惯性技术学报, 2015, 23(4): 505-510. Zeng Qing-xi, Xu Liang, Tang Lin-lin, et al. Beidou CB2I code fast acquisition based on dividing and folding algorithm[J]. Journal of Chinese Inertial Technology, 2015, 23(4): 505-510.

[9] Teixeira M, De Jesus M, Rodriguez Y. Parallel FFT and parallel cyclic convolution algorithms with regular structures and no processor intercommunication[J]. High Performance Embedded Computing, 2005: 1-2.

[10] Kuan C B, Wang S C, Shih W L, et al. Parallelization of a Boken application on embedded multicore DSP systems[J]. Embedded Systems for Real-Time Multi-media, 2011, 9(10): 13-14.

[11] 袁琪, 杨康, 周建江, 等. 大点数FFT算法C6678多核DSP的并行实现[J]. 电子测量技术, 2015, 38(2): 74-80. Yuan Qi, Yang Kang, Zhou Jian-jiang, et al. Implementation of large points FFT based on C6678 multi-core DSP[J]. Electronic Measurement Technology, 2015, 2(38): 74-80.

[12] Vityazev S, Kharin A, Kalinkin A, et al. Parallel form of FIR filter for implementation on multicore DSP[C]//2014 3rd Mediterranean Conference on Embedded Computing. Budva: IEEE Press, 2014: 177-179.

Parallel acquisition algorithm for multi-core Beidou software receiver based on combined FFT

ZENG Qing-xi1, ZHANG Peng-na1, ZHU Xue-fen2, PAN Shu-guo2, PEI Ling3
(1.Department of Vehicle electronic, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China; 2. School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China; 3. Shanghai Key Laboratory of Navigation and Location Based service, Shanghai Jiao tong University, Shanghai 200240, China)

The digital signal processor has been developed from single-core system into multi-core parallel system, which can speed up the signal processing by executing task in parallel. The length of Beidou CB2Icode is twice that of GPS C/A code, thus the acquisition time would be extended if using the traditional algorithm. Aiming at this problem, a parallel acquisition algorithm based on combined FFT is proposed, which separates the signal to odd and even sequences and processes them in parallel. By this way, the single FFT points are halved and the speed is increased by efficiently using the multi-core resource. In order to verify the algorithm’s performance, the PTP values of the two algorithms are compared. Simulation results show that the mean PTP values of the two algorithms are 2.961 and 2.938, respectively. Therefore the proposed algorithm does not reduce the acquisition accuracy. Finally, the computational loads of the two algorithms are analyzed based on the multi-core embedded platform, and the results show that the single-core multiplication computational load is decreased by 40% from the original 33%, and the addition computational load is decreased by 50% when the signal sampling points needed to be processed are increased to 256 000 from 1000. Thus the proposed algorithm can achieve the effect of fast acquisition.

software receiver; Beidou B2 signal; fast acquisition algorithm; combined FFT

V448.2

：A

2016-04-17；

：2016-07-27

国家自然科学基金（51505221）；南京航空航天大学研究生创新实验竞赛（5645004）

曾庆喜（1980—），男，讲师，从事智能车辆高精度导航研究。E-mail: jslyzqx@163.com

1005-6734(2016)04-0496-08

10.13695/j.cnki.12-1222/o3.2016.04.014