北斗導航信號BCH譯碼器中校正子輔助的列表譯碼算法

朱建鋒安建平 王愛華

(北京理工大學信息與電子學院 北京 100081)

1 引言

2012年 12月，中國北斗衛星導航系統公布了第 1個公開服務信號B1I的接口控制文檔(Interface Control Document, ICD)，標志北斗衛星導航系統正式提供區域導航定位服務，ICD文件對北斗衛星導航系統的目標和B1I信號結構進行了詳細定義[1]。B1I導航信號選擇 BCH(15,11)碼作為導航電文的糾錯碼，ICD文件給出了建議的編碼、譯碼實現方法。

衛星導航接收機進行定位解算的前提是獲得足夠數量的正確的導航電文，因此BCH碼譯碼是影響北斗B1I導航接收機定位成功率和連續性的關鍵因素之一[2]。BCH碼是一種典型的線性分組碼，其譯碼算法已經進行了許多研究，譯碼算法主要包括：(1)硬判決代數譯碼，以校正子譯碼算法為代表[3]，該算法復雜度低但編碼增益??；(2)軟判決最大似然算法及簡化，以通用最小距離譯碼GMD算法[4]、Chase算法[5]、統計排序算法[6]等為代表，編碼增益接近最大似然譯碼，其中Chase算法應用最為廣泛，但是 Chase算法中不可靠位搜索和排序運算在FPGA等門電路上串行實現的延時較大[7,8]；(3)軟判決格形譯碼，以維特比算法為代表[9,10]，在碼長較大時具有較好編碼增益但是網格數很多。

軟判決最大似然算法及其簡化算法可以統一到列表譯碼算法的范疇，即在一個列表或集合上按照某種判決測度搜索最優的譯碼結果，列表譯碼算法性能決定于譯碼列表的構造和搜索算法的效率，Chase算法是通過不可靠位的排序建立較小的譯碼列表從而獲得效率改善。校正子輔助的列表譯碼算法以相同的校正子和漢明重量為準則構造多個錯誤模式列表，根據接收數據硬判決序列的校正子選擇錯誤模式列表，使用相關函數差作為判決測度搜索最優錯誤模式并譯碼。

2 校正子輔助的列表譯碼算法

2.1 算法原理

北斗系統 B1I導航信號中使用的 BCH(15,11)碼生成多項式為，最小漢明距，可以糾正所有1 bit錯誤，非0的校正子共有15種情況。校正子輔助的列表譯碼算法原理如圖1所示。

圖1 校正子輔助的列表譯碼原理

譯碼過程包括3個基本步驟：數據預處理、選擇錯誤模式列表和最優錯誤模式搜索，數據預處理將接收數據進行硬判決并計算校正子和取絕對值產生置信度序列，根據硬判決序列的校正子選擇15個錯誤模式列表中的1個，按照判決測度搜索最優錯誤模式并完成譯碼。更大錯誤模式列表可以以更大的概率搜索到正確錯誤模式，但是列表元素數的增加需要更多時間計算判決測度和搜索最優錯誤模式，采用何種判決測度則決定了單個列表元素的計算復雜度，因此，錯誤模式列表和判決測度構造是優化列表譯碼算法的關鍵。

2.2 錯誤模式列表構造

列表譯碼算法中列表的構造包含兩項內容：元素內容和元素數量，在最大似然譯碼中，列表中的元素是所有可能的碼字，在Chase算法中通過搜索P個不可靠位置確定列表中的元素是2P個試探碼字，列表構造需要在列表覆蓋能力和規模之間進行折中。對于(N,K)線性分組碼，接收碼字R C E= + ，校正子S滿足：

其中C為正確碼字，E為錯誤模式，式(1)表明校正子S只和錯誤模式E有關，與碼字C無關。錯誤模式E是一個N維的線性空間，通過校驗矩陣H的映射生成一個(N K- )維的線性空間，錯誤模式 E和校正子S之間為多對一的映射關系，分組碼譯碼可以轉化為在N維線性空間上對最佳錯誤模式E的搜索問題[11,12]。校正子輔助列表譯碼算法以錯誤模式作為列表元素，通過搜索最佳錯誤模式進行BCH(15,11)碼的譯碼，錯誤模式列表的構造依照兩個準則：漢明重量和校正子。

在典型的AWGN信道下，碼字中錯誤的個數符合二項式分布，N bit的碼字發生i個錯誤的概率為

其中p為比特誤碼率。式(2)表明：當 1Np＜ 時，碼字錯誤概率隨著錯誤比特數增加而降低，大部分錯誤碼字中錯誤數都在一個特定門限之下。采用實驗仿真的方法分析錯誤模式的分布規律，以 BCH(15,11)碼為編碼方案，在 AWGN 信道下統計錯誤模式分布，信噪比范圍從 1~8 dB，每個信噪比點生成100000個碼字，分別統計漢明碼重W為0,1,2,3和3以上的錯誤模式個數，其中 0W= 代表碼字沒有發生錯誤。

表1中的數據表明：隨著信噪比的增加，BCH(15,11)碼的錯誤模式主要是兩種情況，以作為選擇錯誤模式的門限建立列表可以以很大的概率覆蓋錯誤模式。對于碼的錯誤模式有15種，的錯誤模式有種，錯誤模式列表中元素總數為120個。

表1 不同信噪比下BCH(15,11)的錯誤模式分布

對于(N,K)線性分組碼，校正子和錯誤模式之間存在線性映射關系，因此利用校正子對錯誤模式列表進行進一步的分割。由于從錯誤模式到校正子是一個從N維到N K- 維的映射，因此存在多個錯誤模式對應一個校正子的情況，要利用校正子分割錯誤模式列表需要解決一個錯誤模式對應于多個校正子的問題，即證明不同的校正子對應不同的錯誤模式，證明過程如下。

與假設相矛盾。所以

證畢

性質1表明，不同的錯誤模式可能具有相同的校正子，但是不同的校正子一定對應不同的錯誤模式。

利用性質1的結論將120個 2W ≤ 的錯誤模式細分到15個列表，同一列表中的錯誤模式具有相同的校正子，平均每個列表中有8個元素。

2.3 相關函數差判決測度

歐氏距離是軟判決譯碼最常用的判決測度，碼字C和接收序列R的歐氏距離定義為

對于 BCH軟判決譯碼，首先計算接收序列 R的置信度序列α和硬判決序列β。

則有

定義相關函數差：

式(11)表明最大相關函數準則等價于最小相關函數差，當錯誤模式E的碼重時，的計算只需要1次加法即可完成。

綜合上述分析，最小歐氏距離準則、最大相關函數準則、最小相關函數差準則在BCH譯碼中是等價的，3種不同判決測度的計算復雜度比較如表 2所示，最小相關變化量具有最小的計算復雜度。

表2 不同判決測度的計算復雜度

3 北斗B1I導航信號BCH譯碼實現與性能仿真

3.1 校正子輔助的列表譯碼器實現

綜合錯誤模式列表的構造和判決測度優化改進，北斗系統B1I導航信號BCH碼的譯碼步驟如下：

步驟2 數據初始化。按照式(7)和式(8)處理接收序列r生成硬判決譯碼序列β和置信度序列α；

步驟3 選擇錯誤模式列表。計算硬判決序列β的校正子 s，如果 0s= 將轉入步驟 6，否則按照 s選擇相應的校正子模式列表E；

步驟 5 搜索最優錯誤模式。按照最小相關函數差準則搜索最優錯誤模式 e，譯碼序列為；

步驟 6 譯碼輸出。抽取譯碼序列的前 11 bit作為譯碼結果輸出。

基于校正子估計的譯碼計算復雜度主要在步驟3中的1次校正子計算和步驟4中的EN 次判決測度計算，這兩個步驟都是線性復雜度，EN 個判決測度計算在FPGA和DSP中可并行實現以進一步改善譯碼延時。

3.2 性能仿真與分析

編碼理論表明糾錯編碼存在性能界，與性能界的差距是衡量譯碼算法優劣的主要依據。聯合界是AWGN信道下線性分組碼可實現的性能界[14]，對于線性碼其誤碼率的上界為

為驗證軟判決譯碼算法的性能和計算復雜度，在AWGN信道下對北斗B1I信號BCH碼進行最大似然算法，Chase算法和校正子輔助列表譯碼算法進行了仿真實現。仿真的條件：AWGN信道，BPSK調制，信噪比步進0.01 dB，誤碼率，仿真實驗要求至少100個錯誤碼字以保證置信度，Chase算法不可靠位數 3P= 。不同譯碼算法的BCH(15,11)

碼性能如圖2所示。

最大似然算法，Chase算法和校正子輔助算法的譯碼復雜度比較如表3，校正子輔助算法的復雜度遠小于另外兩種算法。

圖2 BCH(15,11)碼不同譯碼算法性能比較

表3 BCH(15,11)碼不同譯碼算法的復雜度比較

4 結論

北斗B1I信號是北斗系統的第1個公開服務信號，其目標是面向廣大民用市場提供普遍服務，B1I信號BCH譯碼算法研究在研制面向區域服務的北斗導航接收機中具有重要作用[15]。校正子輔助的列表譯碼算法在誤碼率 10-5時，與最大似然譯碼的信噪比僅差0.08 dB，性能非常接近最大似然譯碼算法和Chase譯碼算法，是一種近優的軟判決譯碼算法。新算法具有計算復雜度低、不要排序運算和可并行優化等特點，適合工程化實現和應用。

[1] China Satellite Navigation Office. BeiDou navigation satellite system signal in space interface control document open service signal B1I (Version 1.0)[S]. 2012.

[2] 陳金平, 王夢麗, 錢曙光. 現代化GNSS導航電文設計分析[J].電子與信息學報, 2011, 33(1): 211-217.

[3] 連帥, 閆利軍, 孫科. 北斗2代衛星導航電文糾錯校驗設計與仿真[J]. 計算機測量與控制, 2010, 18(10): 2344-2347.

[4] Forney G Jr. Generalized minimum distance decoding[J].IEEE Transactions on Information Theory, 1966, 12(1):125-131.

[5] Chase D. Class of algorithms for decoding block codes with channel measurement information[J]. IEEE Transactions on Information Theory, 1972, 18(1): 170-179.

[6] Fossorier M P C and Shu Lin. Soft-decision decoding of linear block bodes based on ordered statistics[J]. IEEE Transactions on Information Theory, 1995, 41(5): 1379-1396.

[7] Skliarova I, Sklyarov V, Mihhailov D, et al.. Implementation of sorting algorithms in reconfigurable hardware[C]. 2012 16th IEEE Mediterranean Electro technical Conference(MELECON), Yasmine Hammamet, Tunisia, 2012: 107-110.

[8] García-Herrero F, Canet M J, Valls J, et al.. High-throughput interpolator architecture for low-complexity chase decoding of RS codes[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2012, 20(3): 568-573.

[9] Honary B and Markarian G. Low-complexity trellis decoding of hamming codes[J]. Electronics Letters, 1993, 29(12):1114-1116.

[10] Michelson A M and Freeman D F. Viterbi decoding of the (63,57) Hamming codeimplementation and performance results [J]. IEEE Transactions on Communications, 1995,43(11): 2653-2656.

[11] Snyders J. On survivor error patterns for maximum likelihood soft decoding[C]. 1991 IEEE International Symposium on Information Theory, Budapest, Hungary, 1991:192.

[12] Snyders J. Reduced lists of error patterns for maximum likelihood soft decoding[J]. IEEE Transactions on Information Theory, 1991, 37(4): 1194-1200.

[13] 朱建鋒, 安建平, 王愛華. 導航電文BCH(15,11)編碼的低復雜度軟判決譯碼[C]. 第4屆中國衛星導航學術年會(CSNC 2013), 武漢, 2013-05-15.

[14] Fossorier M P C, Shu Lin, and Rhee D. Bit-error probability for maximum-likelihood decoding of linear block codes and related soft-decision decoding methods[J]. IEEE Transactions on Information Theory, 1998, 44(7): 3083-3090.

[15] Montenbruck O, Hauschild A, Steigenberger P, et al.. Initial assessment of the COMPASS/BeiDou-2 regional navigation satellite system[J]. GPS Solutions, 2013, 17(2): 211-222.