導航系統BCH 碼軟判決譯碼方案與實現

汪 峰，李金海，孫金海，閻躍鵬

（中國科學院微電子研究所，北京100029）

0 引 言

目前衛星導航接收機對信號靈敏度要求越來越高，在捕獲與跟蹤算法已經相對成熟固定的情況下，通過其它手段來提高系統靈敏度是研究的熱點。其中導航電文糾錯碼目前普遍采用傳統硬判決方案，針對BCH （15，11）碼進行譯碼，可以糾正1 比特傳輸錯誤。軟判決Chase算法是一種基于軟信息的次優譯碼算法，適用于中短碼長的線性分組碼，適用于作為電文譯碼的方案，取代硬判決方案。

通過改善電文糾錯碼譯碼算法，結合算法復雜度與系統增益，得到適用于此系統的配置參數，可以給系統帶來1.2dB（BER＝10－5情況下）的增益，盡管譯碼的算法復雜度變大，但帶來的性能提升是更有利的。

1 導航系統的BCH 碼介紹

1.1 線性碼介紹

為了改善和提高數字通信系統的傳輸質量，我們經常采用信道編碼。在分類眾多的編碼方案中，線性分組碼是使用較廣的一類。

線性分組碼將信息分成k位為一組，并按照一定規律加上認為冗余碼元，構成n （n＞k）位碼元，可采用 （n，k）表示，其中n為碼組總長度，k表示信息位，那么n－k個多余碼元是可供接收端檢查糾正傳輸中的錯誤使用，成為監督碼元。線性分組碼的信息碼元與監督碼元之間的關系為線性關系，其具有兩個重要的性質：

（1）任意兩許用碼之和仍為一許用碼，也就是說，線性分組碼具有封閉性；

（2）碼組間的最小碼距等于非零碼的最小碼重。

1.2 BCH 碼介紹

BCH 碼是線性分組碼的重要子類，是編碼理論尤其是糾錯碼中研究得比較多的一種編碼方法，由Bose等在上世紀六十年代提出，用于校正多個隨機錯誤模式的多級、循環、錯誤校正、變長數字編碼［1］。

BCH 碼具有構造方便、編碼簡單以及譯碼易于實現等優點，而且BCH 碼有完備的代數理論支持。BCH 碼的生成多項式與最小距離d有密切關系，使設計者可以根據d的需要輕易構造出具有預定糾錯能力的編碼方案。其糾錯能力強，中短碼長下的性能接近理論值。

對BCH 碼的后續研究主要集中在譯碼算法的簡化，如減少迭代次數、快速譯碼算法、提高糾錯能力、軟判決譯碼等。

1.3 BCH 編碼方案

導航電文中采用的BCH （15，11）碼，其為循環碼，碼長為15，信息位為11，生成多項式為g（x）＝x4＋x＋1。可以證明，該BCH 碼的最小Hamming距離為3，采用傳統的硬判決譯碼具有糾正1位錯誤的能力。

由于BCH （15，11）碼是循環碼，其編碼可以采用多項式除法進行，編碼過程包括下面3個步驟：

步驟1 將待編碼的信息序列構成信息多項式m（x），并與xr相乘得到u（x）＝xrm（x），其中，r＝deg（g（x））＝4。

步驟2 將u（x）除以生成多項式g（x）得到商多項式q（x）和余式r（x），其中，deg（r（x））＜4。

步驟3 生成碼字多項式s（x）＝u（x）＋r（x）＝xrm（x）＋r（x）。

至此，編碼過程完成。在實際中，上述過程可以用移位寄存器實現，其結構框架如圖1所示。

圖1 北斗系統BCH 碼編碼器結構框架

1.4 傳統的硬判決譯碼算法

BCH （15，11）碼糾正1 比特錯誤的硬判決譯碼算法［2］可以采用基于伴隨式 （syndrome）的查表法，其譯碼過程包括如下步驟：

步驟1 將接收序列多項式v（x）＝s（x）＋e（x）除以生成多項式g（x），得到余式r（x），其中，deg（r（x））＜4。

步驟2 將r（x）與預先在ROM 中存儲的伴隨式集合相比較，搜索syn（j）（x）＝r（x）。

上述譯碼過程的實現框架如圖2所示。

對于上述硬判決譯碼算法，當傳輸過程中出現多比特錯誤時，譯碼器會將其當作1比特錯誤來糾正，因此會導致錯誤不能完全被糾正，甚至會出現錯誤增加的可能。因此，BCH （15，11）碼采用上述硬判決譯碼算法獲得的編碼增益較小，譯碼失敗門限較高。下面，利用BCH 碼的結構特點，設計一種低復雜度軟信息譯碼方案。

2 BCH 碼低復雜度軟信息譯碼方案

2.1 譯碼方案設計

圖2 傳統糾正1比特錯誤的硬判決譯碼器結構框架

編碼理論表明，若接收端可以得到解調后的軟信息作為譯碼器的輸入，則可以改善譯碼性能。對于線性分組碼，Chase算法是一種重要的基于軟信息的次優譯碼算法。下面，利用Chase算法的原理設計導航系統中的BCH （15，11）碼的軟信息譯碼方案［3］。

Chase算法的譯碼基本流程如圖3 所示。其基本原理是，根據接收軟信息向量r找出p 個不可靠的位置，產生2p個測試圖樣，分別與r的硬判決序列相加，進行代數譯碼得到碼字，之后計算接收向量與碼字的度量，并選擇度量最小值進行判決輸出。

基于算法軟硬件實現要求，把圖3細化后，BCH （15，11）碼的Chase算法譯碼步驟如下：

圖3 Chase算法的譯碼基本流程

輸入：接收序列r，參數p，修正因子α和β。

步驟1 對接收序列r進行判決，得到硬判決序列y，其中

步驟2 選擇r中最不可靠的p 個位置；

步驟3 產生2p個測試圖樣ti（i＝1，2，…，2p）。每個測試圖樣為長度為n 的向量，在步驟2中所選擇的p 個位置上遍歷所有2p種可能，其余位置為0；

步驟4 將硬判決與2p個測試圖樣相加，得到2p個序列zi（i＝1，2，…，2p）；

步驟5 分別對這2p個序列進行譯碼，得到2p個候選碼字si（i＝1，2，…，2p）；

步驟6 分別計算這2p個碼字與r的度量mi＝－（si，r），其中 （，）表示內積；

步驟7 選擇mi中的最小值作為譯碼器的輸出。

可以看出，Chase算法的復雜度由參數p 決定，其量級關系為2p。

2.2 仿真結果及分析

為了驗證BCH （15，11）碼的Chase算法的性能，基于MATLAB平臺進行Chase算法的仿真，并與傳統的硬判決算法進行比較。圖4給出了傳統硬判決譯碼算法與Chase算法在AWGN 信道下的誤碼率 （BER）浮點性能對比，其中Chase算法的參數p＝2。

從圖4 中可以看出，在BER＝10－5下，參數p＝2 的Chase算法的性能相對于傳統的硬判決譯碼算法性能獲得了約1.2dB的增益。

圖5給出了不同參數p 取值下Chase算法的性能對比。

從圖5中可以看出，對于Chase算法，p＝2下的性能相對于p＝1的性能有明顯提高，但是，p＝3與p＝2的性能幾乎一致。由前面的分析可知，Chase算法的復雜度和p之間呈指數關系，因此在實際中，建議Chase算法的參數p取值為2。

圖4 BCH （15，11）碼傳統硬判決譯碼算法與Chase算法的性能對比

圖5 不同參數p 取值下Chase算法的性能對比

3 Chase譯碼算法的量化方案

3.1 量化方案設計

由于實際中使用的譯碼器的輸入數據的位寬是有限的，因此，需要給出Chase算法的有效量化方案。通過大量仿真分析，我們發現如下自適應量化方案對于Chase譯碼的性能損失最小。

假定Chase譯碼器的接收向量為r，將其元素按照從小到大的順序排列后的向量記為r→。首先，將r→的最小cl個數值和最大的cl個數值刪去，其中，cl為一事先給定的數值。記刪除后的數組中的最小值為Lb，最大值為Ub。若N 為量化電平數，則量化間隔

具體量化采用均勻量化，設計如下：

（1）若ri＜－Qr／2，則量化后＝0；

（2）若ri＞Qr／2，則量化后＝N－1；

3.2 仿真結果及分析

為了驗證上述量化方案，對參數p＝2下的Chase算法進行性能對比。其中參數cl＝2，量化電平數N＝16。圖6給出了Chase算法的定點和浮點的性能對比。

圖6 Chase算法的浮點和定點性能對比 （p＝2）

從圖6中可以看出，量化后的Chase算法的性能相對于浮點性能幾乎沒有任何損失。

4 硬件實現

4.1 實現說明

基于上節的理論與仿真分析，參數p＝2時，相比p 取3或者更大，信噪比的提升并不大；并且采用3.1章節自適應量化方案，定點量化所帶來的性能損失也基本可以忽略不計。因此在硬件實現過程中我們采用p＝2。

根據3.1節量化方案，輸入碼片采用4bit自適應量化，對于一組碼片（15chip）來說，總輸入比特量為4×15＝60比特；輸出15比特；在碼片輸出時放出使能信號out＿en，通知下級設備接收數據，高電平有效。

我們采用3.2節的參數進行軟判決算法的FPGA 硬件實現。編譯環境是Altera公司的Quartus II v11.1；FPGA器件采用Cyclone IV EP4CE115F29C7［4］。

4.2 前端仿真結果

軟判決Chase算法的硬件使用modelsim 進行仿真，結果如圖7所示，由于輸出結果是輸入數據逐位移位生成的，所以輸出要延時若干個時鐘才能得到，從實際仿真結果中看到從輸入開始到輸出使能，一共經過了36個時鐘周期。輸出的結果與理論分析一致，正確無誤。

4.3 硬件綜合規模

根據上節仿真代碼，我們進行硬件綜合，綜合結果如圖8所示。

圖7 硬件仿真結果

圖8 軟判決算法的資源占用

由于軟判決Chase算法的復雜度和參數p 之間呈指數關系，所以較之傳統硬判決方案，Chase算法的硬件規模大10倍左右，但硬件規模的絕對值并不大。

一般導航類接收機工作頻率不會超過100 MHz，如圖9所示，本設備可以工作在107.84 MHz，完全滿足接收機的性能要求。

圖9 綜合時鐘頻率

5 結束語

對比傳統硬判決譯碼方案，本文設計的BCH 碼軟判決算法可以將系統增益提高1dB－2dB，在在對于靈敏度要求很高的衛星導航領域，無疑是個不小的提高；硬件實現情況表明與理論結果一致，適用于衛星導航接收機中；算法復雜度提高帶來的硬件規模增大，也完全在可承受范圍之內。此算法方案可以應用于對靈敏度敏感的衛星導航接收機電文譯碼之中，并適用于所有中短碼長的線性分組碼的譯碼方案。

［1］ZHOU Jiongpan，PANG Qinhua，XU Dawo，et al.Communication principles（volume II）［M］.Beijing：Beijing University of Posts and Telecommunications Press，2002：103－110（in Chinese）. ［周炯槃，龐沁華，續大我，等.通信原理（下）［M］.北京：北京郵電大學出版社，2002：103－110.］

［2］LIAN Shuai，YAN Lijun，SUN Ke.Design and simulation of correction and parity in ephemeris for BeiDou No.2navigation satellites［J］.Computer Measurement ＆ Control，2010，18（10）：2344－2347 （in Chinese）.［連帥，閆利軍，孫科.北斗2代衛星導航電文糾錯校驗設計與仿真 ［J］.計算機測量與控制，2010，18 （10）：2344－2347.］

［3］Chase D.A class of algorithms for decoding block codes with channel measurement information ［J］.IEEE Trans Inf Theory，1972 （18）1：70－179.

［4］Altera Corporation.Cyclone IV device handbook ［OL］.http：／／www.altera.com.cn／literature／hb／cyclone－iv／cyclone4－handbook.pdf，2013.

［5］Lin S，Costello D.Error control coding：Fundamentals and applications［M］.Prentice－Hall，2004.

［6］ZHANG Yan，LI Shujian，CUI Jin.Design and implementation of BCH encoder／decoder［J］.Communications Technolo－gy，2010 （12）：24－25 （in Chinese）. ［張彥，李署堅，崔金.一種BCH 碼編譯碼器的設計與實現 ［J］.通信技術，2010（12）：24－25.］

［7］CHEN Jinping，WANG Mengli，QIAN Shuguang.Analysis of modernization GNSS navigation message’s designing［J］.Journal of Electronics ＆Information Technology，2011，33 （1）：211－217 （in Chinese）. ［陳金平，王夢麗，錢曙光.現代化GNSS導航電文設計分析 ［J］.電子與信息學報，2011，33（1）：211－217.］

［8］Beyerle G，Ramatschi M，Galas R，et al.A data archive of GPS navigation messages［J］.GPS Solution，2009，13 （1）：35－41.

［9］GAO Yudong，XI Xiaoning，WANG Wei.Progress of navigation satellite broadcast ephemeris algorithms in China ［J］.Journal of Spacecraft EE ＆C Technology，2008，27 （4）：79－84 （in Chinese）. ［高玉東，郗曉寧，王威.我國導航星廣播星歷參數算法研究進展 ［J］.飛行器測控學報，2008，27（4）：79－84.］

［10］ZHANG Yongguang，ZHENG Shilian.Research on parameter identifucaton of BCH codes［J］.Journal of Xidian University，2013，40 （5）：72－77 （in Chinese）.［張永光，鄭仕鏈.BCH 碼的參數識別研究 ［J］.西安電子科技大學學報，2013，40 （5）：72－77.］