基于分段折疊算法的北斗CB2I碼快速捕獲

曾慶喜，徐 亮，唐琳琳，王 慶

（1. 南京航空航天大學 車輛工程系，南京 210016；2. 東南大學 儀器科學與工程學院，南京 210096）

基于分段折疊算法的北斗CB2I碼快速捕獲

曾慶喜1，徐 亮1，唐琳琳1，王 慶2

（1. 南京航空航天大學 車輛工程系，南京 210016；2. 東南大學 儀器科學與工程學院，南京 210096）

以最新公布的北斗B2信號為研究對象，針對采樣頻率較高時，利用傳統的并行碼相位搜索捕獲算法對北斗CB2I碼進行捕獲存在總運算量和單次FFT運算點數較大的問題，提出了一種基于分段折疊的基帶信號快速捕獲算法，即利用本地CB2I碼前后兩段折疊處理形成本地折疊CB2I碼進行捕獲運算。利用仿真的北斗B2信號源對本文提出的改進算法進行了驗證，仿真結果表明，和傳統的捕獲算法相比，改進的快速捕獲算法將捕獲過程的總運算量以及單次FFT運算的點數降低了約一半，提高了北斗CB2I碼的捕獲速度。此外，可以根據信號強度的不同對捕獲速度和捕獲靈敏度進行權衡，保證北斗B2I信號捕獲性能的最優。

北斗CB2I碼；分段折疊；快速捕獲；運算量

《北斗衛星導航系統空間信號接口控制文件(2.0版)》于2013年底正式公布，該文件新增了北斗系統B2頻點的信號內容，標志著北斗系統已經成為世界上首個擁有兩個民用頻點并已經形成服務能力的衛星導航系統[1]。本文以最新公布的北斗B2信號為對象，對其基帶信號處理的首要環節——捕獲的快速實現算法進行了研究。對于任何一種捕獲算法而言，影響捕獲速度的主要因素之一是算法的總運算量。對于基于頻域計算的捕獲算法，單次FFT運算點數的大小也會在很大程度上對捕獲速度造成影響。因此如何有效地減少捕獲算法的總運算量和單次FFT運算點數是提高捕獲速度的關鍵。目前廣泛采用的捕獲算法是基于FFT的并行碼相位搜索捕獲算法，但是當采樣頻率較高時，該算法的總運算量和FFT運算點數都非常大[2-4]，不僅導致捕獲速度較慢，而且算法在嵌入式系統上實現時實現難度也非常大。針對上述問題，本文在對B2信號的結構和相關特性進行深入研究的基礎上，提出一種改進的基于分段折疊的北斗B2I信號基帶信號快速捕獲算法。

1 北斗B2信號的結構及相關特性分析

根據《北斗衛星導航系統空間信號接口控制文件(2.0版)》中對北斗B2信號的描述，與北斗B1信號類似，B2信號也是由I、Q兩個支路上的“測距碼+導航電文”通過正交調制在載波上構成的[1]，并可以用如下的數學表達式表示：

由此可見，北斗B2信號的組成和結構均與GPS L1信號非常類似，而且兩者均采用碼分多址的信號復用方式和右旋圓極化的極化方式，但是在調制方式、測距碼結構等方面兩者仍存在著顯著差異[5]。與GPS L1信號所采取的BPSK（相移鍵控）的調制方式[6]不同，北斗B2信號采用的是QPSK（正交相移鍵控）調制方式，具有較高的頻譜利用率和較好的抗干擾能力。

圖1 北斗CB2I碼發生器示意圖Fig.1 Generator of Beidou code

由于北斗B2頻點Q支路的信號是授權信號，即不對民用開放，因此本文只針對I支路的信號進行研究。北斗B2信號I支路測距碼CB2I的產生是通過兩個11位的移位寄存器G1和G2，G1和G2產生長度為211-1=2047位的最大長度偽碼，描述G1和G1的多項式分別為G1=1+X+X7+X8+X9+X10+X11和G2=1+X+X2+X3+X4+X5+X8+X9+X11。CB2I碼是由 G1的直接輸出和G2的延遲輸出經過模二相加產生平衡Gold碼，然后該Gold碼截短一個碼片生成的，如圖1所示，即CB2I碼的碼長為2046個碼片，是GPS C/A碼碼長的2倍。

2 傳統的并行碼相位搜索捕獲算法

1991年，Nee D.V.在文獻[7]中提出了基于FFT的并行碼相位搜索捕獲算法，將碼相位的時域相關運算轉換為頻域的乘法運算，因而只需要對多普勒頻率進行一維搜索從而很大程度上降低了算法的運算量，提高了捕獲速度。利用傅里葉變換實現時域循環相關的數學原理如下：

長度為N的有限長序列x(n)傅里葉變換的結果為

長度為N的有限長序列x(n)和y(n)的互相關結果為

根據公式(2)和公式(3)可以得出兩個有限長序列頻域互相關的計算公式：

式中，X*(k)表示X(k)的復共軛。

公式(4)得到的是輸入信號和本地復現信號的頻域相關結果，對該結果求傅里葉逆變換就可以得到所需要的時域相關結果。

基于FFT的并行碼相位搜索捕獲算法原理如圖2所示。基于該算法進行捕獲[8-9]的具體實施方法如下：

① 步驟1：首先在多普勒頻率搜索范圍內選定一個頻率值fd，然后1ms長的輸入中頻信號x和該頻率下的等長的本地載波loc=e-j2π(fIF+fd)n相乘得到混頻信號，并對混頻信號進行FFT變換。

② 步驟2：本地偽碼產生器產生一個周期的本地復制碼CAlocal，并作FFT變換，然后對FFT的結果進行共軛處理。

③ 步驟3：上述兩個FFT的結果相乘并進行IFFT，然后將IFFT取模后得到的相關結果的峰值與預先設定的門限值進行對比。如果大于門限值，則捕獲成功；否則移動到下一個本地載波多普勒頻率[10]，并重復步驟①和②；

并行碼相位捕獲算法的核心是FFT運算[11-12]，雖然相對于時域串行搜索捕獲算法，該算法已經明顯提高了捕速度。但是當FFT運算的點數較大時，算法的運算復雜度和硬件的實現難度都會有所增加，從而對捕獲的實時性產生影響[13]。以本文11.428 MHz的采樣頻率為例，如果直接采用傳統的并行碼相位搜素捕獲算法，單次FFT運算的點數高達11428個采樣點[14]，運算量非常大。針對上述問題，本文提出了一種分段折疊的快速捕獲算法，將頻域并行搜索捕獲和單點的時域串行搜索捕獲相結合，單次FFT運算的點數可以減少為原來的一半。

圖2 并行碼相位搜索捕獲算法原理Fig.2 Principle of parallel code phase search acquisition algorithm

3 改進的基于分段折疊的北斗B2I信號快速捕獲算法

3.1 算法原理

本文在對本地CB2I碼分段的基礎上進行一次折疊處理，將傳統直捕算法中相關運算所需要的輸入信號的長度由1 ms變為0.5 ms，然后將頻域并行搜索捕獲和單點的時域串行搜索捕獲相結合減少算法的運算量，該算法的原理如圖3所示。算法的具體實現步驟如下：

① 步驟1：首先在北斗B2I信號多普勒頻率搜索范圍內選定一個頻率值fd，然后0.5 ms長的輸入北斗B2I中頻信號x和該頻率下等長的本地載波loc=e-j2π(fIF+fd)n相乘得到混頻信號，記為y，最后對其求FFT；

圖3 基于分段折疊的CB2I碼快速捕獲算法Fig.3 Algorithm of Beidou CB2Icode fast acquisition based on dividing and folding

其中，y(k0)表示所取的0.5 ms的混頻信號的起始采樣點，N0.5ms為0.5 ms內的采樣點。

② 步驟2：產生一個周期的本地CB2I碼（1 ms），并平均分成前后兩段，分別記為和，將和線性疊加得到長度為0.5 ms的本地折疊CB2I碼，記為，然后對求FFT并進行共軛處理；

③ 步驟3：將步驟①和步驟②得到的結果相乘后進行IFFT變換，得到N0.5ms個不同碼相位對應的相關值的集合R。如果R中有相關值超過設定的門限值，則可以獲得該相關峰值所對應的CB2I折疊碼的碼相位Pf并繼續步驟4；如果R中所有相關值均小于門限值，則需要改變多普勒頻率fd并重復步驟①～步驟③。

④ 步驟4：在混頻信號中，以得到的CB2I折疊碼的碼相位Pf作為起點取0.5 ms長的混頻信號，然后該混頻信號與步驟2中的本地CB2I碼和分別進行點對點相乘累加，將得到兩個相關峰值P1和P2。對P1和P2的大小進行比較，如果P1＞P2，則輸入信號中CB2I碼的碼相位就等于CB2I折疊碼的碼相位Pf；反之，如果P1＜P2，則輸入信號的碼相位就等于Pf+N0.5ms，N0.5ms為0.5 ms的采樣點數。

3.2 計算復雜度對比分析

按上述兩種捕獲算法的捕獲步驟，分別對兩種算法每一步計算中的乘法和加法運算量進行了統計，并計算出了每種算法的總計算量，如表1所示。

表1 北斗B2I信號傳統捕獲算法及改進捕獲算法運算量對比Tab.1 Comparison on calculation amount between traditional Beidou B2I code acquisition algorithm and improved acquisition algorithm

為了更直觀地對上述兩種算法的運算量進行對比觀察，本文以從1 MHz到20 MHz，每隔1 MHz取一個采樣頻率，然后基于該采樣頻率對兩種算法的運算量進行仿真對比，對比結果如圖4所示。

由圖4可以看出，相比傳統的捕獲算法，本文所改進的捕獲算法在加法和乘法計算量上均減少了大約一半，而且由于折疊方法的引入，使得單次FFT運算的點數由N變為N/2，降低了算法的實現難度。

圖4 傳統捕獲算法及本文改進算法的運算量對比Fig.4 Comparison between traditional algorithm and improved algorithm in calculated amount

4 仿真結果及分析

如圖5所示是北斗B2頻點中頻信號發生器的原理示意圖，基于該原理利用MATLAB仿真模擬了北斗B2頻點的中頻信號源，并利用該仿真信號源對本文所改進的算法進行了仿真驗證。

圖5 北斗B2頻點中頻信號發生器原理Fig.5 Principle of Beidou B2 intermediate frequency signal generator

在仿真的中頻信號源中，衛星為北斗1號GEO衛星，設置的信號最小接收功率為-163 dBW，載噪比為45 dB/Hz，載波中頻為3 MHz，采樣頻率為11.428 MHz（80 MHz信號的7分頻），多普勒頻移為2 kHz，CB2I碼偏移量為3212個采樣點。

基于上述設置的北斗B2中頻仿真信號源，分別利用傳統的并行碼相位搜索捕獲算法以及本文改進的基于分段折疊的快速捕獲算法對北斗B2I信號進行了捕獲驗證，捕獲結果如圖6～圖7所示。

圖6 基于傳統捕獲算法的北斗B2I信號碼相位捕獲結果Fig.6 Results of Beidou B2I code phase acquisition based on traditional acquisition algorithm

圖7 基于改進的分段折疊捕獲算法的北斗B2I信號碼相位捕獲結果Fig.7 Results of Beidou B2I code phase acquisition based on improved acquisition algorithm

由圖6可以直接看出基于傳統捕獲算法所捕獲到的CB2I碼的碼相位為3213；由圖7(1)可以得到基于改進的分段折疊捕獲算法所捕獲到的CB2I折疊碼的碼相位為3213，然后根據4.1節中的步驟4進行時域相關得到圖8(2)所示的仿真結果，根據4.1節中所介紹的改進的分段折疊算法的捕獲原理，可以最終得到CB2I碼的碼相位為3213。由此可見，兩種捕獲算法的捕獲結果完全一致，均與標準設置的碼相位相比偏移了1個采樣點。由于采樣頻率為11.248 MHz，故1個CB2I碼片對應5或6個采樣點，捕獲結果偏移1個采樣點屬于正常的誤差范圍之內。

圖8 傳統捕獲算法及本文改進算法捕獲結果峰峰值對比Fig.8 Comparison between traditional algorithm and improved algorithm in PTP

本文利用峰峰值PTP（最大相關峰值和次相關峰值的比值）對本文改進的基于分段折疊的CB2I碼直捕算法的捕獲性能進行分析。取上述100 ms連續的北斗B2仿真信號，利用上述兩種算法對每1 ms的輸入數據進行一次捕獲，總共可以進行100次的CB2I碼捕獲，捕獲結果的峰峰值如圖8所示。經計算可得傳統的捕獲算法的峰峰值的平均值為6.5184，基于分段折疊的CB2I碼快速捕獲算法的峰峰值的平均值為3.3494。因此，與傳統的CB2I碼捕獲算法相比，基于分段折疊的CB2I碼快速捕獲算法的捕獲靈敏度有所下降，這是因為由于對本地CB2I碼進行了折疊，從而引入背景噪聲，進而導致部分捕獲靈敏度降低。

5 結 論

本文以北斗B2I信號為研究對象，針對當采樣頻率較高時，基于傳統的并行碼相位搜索捕獲算法對該信號進行捕獲時總運算量較高，單次FFT運算點數較大的問題，提出了一種改進的基于分段折疊的CB2I碼快速捕獲算法。該算法將傳統的并行碼相位搜索捕獲算法的計算量以及單次FFT運算的點數降低了約一半，大大提高了捕獲速度。但是由于對本地偽碼進行了折疊處理，從而引入背景噪聲，導致捕獲靈敏度降低，因此在北斗B2I信號較強的環境中，應該優先選擇該改進的捕獲算法提高捕獲速度，但是較弱的環境中就應該優先選擇高靈敏度的捕獲算法先保證捕獲成功。所以在選擇捕獲算法時應該對算法的捕獲靈敏度、運算量及實現難度進行綜合考慮，根據信號強度的不同權衡選擇北斗B2I信號最合適的捕獲算法，從而保證捕獲性能的最優。

（References）：

[1] 中國衛星導航系統管理辦公室. 北斗衛星導航系統空間信號接口控制文件公開服務信號[M]. 2.0版. 北京:中國標準出版社, 2013. China Satellite Navigation Office. Beidou navigation satellite signal in space interface control document open service signal[M]. Version2.0. Beijing: China Standardization, 2013.

[2] Duan Xiao-jun, Jiang Kai, Zheng Yan , et al. Combined integrity analysis of GPS, Galileo and COMPASS with comparison of different strategies[C]//24th International Technical Meeting of the Satellite Division of The Institute of Navigation. Portland, 2011: 3217-3226.

[3] 楊元喜. 北斗衛星導航系統的進展、貢獻與挑戰[J]. 測繪學報, 2010, 39(1): 1-6. Yang Yuan-xi. Progress, contribution and challenges of compass/Beidou satellite navigation system[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(1): 1-6.

[4] 朱建良, 王興全, 薄煜明, 等. 提高北斗BOC信號捕獲精度的偽碼相位估計法[J]. 中國慣性技術學報, 2014, 22(1): 79-83. Zhu Jian-liang, Wang Xing-quan, Bo Yu-ming, et al. Pseudo code phase estimation method for improving BOC signal acquisition accuracy of BeiDou[J]. Journal of Chinese Inertial Technology, 2014, 22(1): 79-83.

[5] Sahmoudi M, Amin M G. Fast iterative maximum-likelihood algorithm(FIMLA) for multipath mitigation in the next generation of GNSS receiver[J]. IEEE Transactions on Wireless Communications. 2008, 11(1): 4362-4374.

[6] 劉天旻, 茅旭初. 北斗二代系統B1頻段中頻信號的生成方法[J]. 計算機仿真, 2013, 30(9): 70-73. Liu Tian-wen, Mao Xu-chu. Method of BD2 B1 signal generating[J]. Computer Simulation, 2013, 30(9): 70-73.

[7] Nee D V. A new fast GPS code-acquisition technique using FFT[J]. Electronic Letters, 1991, 27(2): 158-160.

[8] 曾慶喜, 唐琳琳, 王慶, 陳小惠. 基于分段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.

[9] Tsui J B Y. Fundamentals of global positioning system receivers: a software approach[M]. USA: John Wiley & Sons, 2000.

[10] 李豹, 許江寧, 曹可勁. 北斗二代導航信號抗多徑性能分析與仿真[J]．中國慣性技術學報, 2012, 20(3): 339-342, 347. Li Bao, Xu Jiang-ning, Cao Ke-jin. Analysis and simulation on anti-multipath performance of Beidou2 navigation[J]. Journal of Chinese Inertial Technology, 2012, 20(3): 339-342, 347.

[11] Zeng Qing-xi, Tang Lin-lin, Wang Qing, et al. Weak GPS L1 signal acquisition based on BPDC[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2014, 31(3): 331-337.

[12] Starzyk J A, Zhu Z. Averaging correlation for C/A code acquisition and tracking in frequency domain[C]// Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems. Seoul, 2001: 905-908.

[13] 趙琳, 高帥和, 丁繼成. 基于FFT 的高動態GPS信號捕獲算法優化[J]. 系統工程與電子技術, 2011, 33(1): 151-156. Zhao L, Gao S H, Ding J C. Improved acquisition for high dynamic GPS signals based on FFT[J]. Systems Engineering and Electronics, 2011, 33(1): 151-156.

[14] Alaqeeli A, Starzyk J, Frank van Graas. Real-time and acquisition and tracking for GPS receivers[C]//Proceedings of the 2003 IEEE International Symposium on Circuits and Systems. Thailand, 2003: 500-503.

Beidou CB2Icode fast acquisition based on dividing and folding algorithm

ZENG Qing-xi1, XU Liang1, TANG Lin-lin1, WANG Qing2
(1. Department of Vehicle Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China; 2. School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China)

When Beidou CB2Icode based on traditional parallel code phase search acquisition algorithm adopts a higher sampling frequency, there are much more operation points for each FFT, and the total calculation amount is also much larger. Aiming at the above problem, a fast acquisition algorithm based on dividing and folding is put forward, which realizes the acquisition based on the local folded CB2Icode formed by folding the two segments of local CB2Icode. The proposed algorithm is verified by simulated Beidou B2 signal source. Simulation results show that the total computation burden and the operation points of single FFT based on the suggested algorithm is approximately reduced by 50% compared with that of traditional acquisition algorithm, which improves the acquisition speed of Beidou CB2Icode. In addition, the acquisition performance of Beidou B2I signal can be optimized by the trade-off between acquisition speed and acquisition sensitivity under different signal strengths.

Beidou CB2I; dividing and folding; fast acquisition; calculation amount

TN927.23

A

1005-6734(2015)04-0505-06

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

2015-04-28；

2015-07-28

國家自然科學基金資助項目（51505221）；南京航空航天大學研究生創新基地(實驗室)開放基金資助（kfjj201464）

曾慶喜（1980—），男，講師，從事車輛智能高精度導航的研究。E-mail：jslyzqx@163.com