朱建鋒安建平 王愛華

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

1 引言

2012年 12月，中國北斗衛(wèi)星導(dǎo)航系統(tǒng)公布了第 1個公開服務(wù)信號B1I的接口控制文檔(Interface Control Document, ICD)，標志北斗衛(wèi)星導(dǎo)航系統(tǒng)正式提供區(qū)域?qū)Ш蕉ㄎ环?wù)，ICD文件對北斗衛(wèi)星導(dǎo)航系統(tǒng)的目標和B1I信號結(jié)構(gòu)進行了詳細定義[1]。B1I導(dǎo)航信號選擇 BCH(15,11)碼作為導(dǎo)航電文的糾錯碼，ICD文件給出了建議的編碼、譯碼實現(xiàn)方法。

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

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

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

2.1 算法原理

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

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

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

2.2 錯誤模式列表構(gòu)造

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

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

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

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

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

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

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

與假設(shè)相矛盾。所以

證畢

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

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

2.3 相關(guān)函數(shù)差判決測度

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

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

則有

定義相關(guān)函數(shù)差：

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

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

表2 不同判決測度的計算復(fù)雜度

3 北斗B1I導(dǎo)航信號BCH譯碼實現(xiàn)與性能仿真

3.1 校正子輔助的列表譯碼器實現(xiàn)

綜合錯誤模式列表的構(gòu)造和判決測度優(yōu)化改進，北斗系統(tǒng)B1I導(dǎo)航信號BCH碼的譯碼步驟如下：

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

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

步驟 5 搜索最優(yōu)錯誤模式。按照最小相關(guān)函數(shù)差準則搜索最優(yōu)錯誤模式 e，譯碼序列為；

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

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

3.2 性能仿真與分析

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

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

碼性能如圖2所示。

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

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

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

4 結(jié)論

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

[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] 陳金平, 王夢麗, 錢曙光. 現(xiàn)代化GNSS導(dǎo)航電文設(shè)計分析[J].電子與信息學報, 2011, 33(1): 211-217.

[3] 連帥, 閆利軍, 孫科. 北斗2代衛(wèi)星導(dǎo)航電文糾錯校驗設(shè)計與仿真[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] 朱建鋒, 安建平, 王愛華. 導(dǎo)航電文BCH(15,11)編碼的低復(fù)雜度軟判決譯碼[C]. 第4屆中國衛(wèi)星導(dǎo)航學術(shù)年會(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.