朱建鋒安建平 王愛華

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

1 引言

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

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

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

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

2.1 算法原理

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

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

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

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

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

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

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

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

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

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

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

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

證畢

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

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

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

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

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

則有

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

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

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

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

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

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

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

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

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

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

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

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

3.2 性能仿真與分析

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

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

碼性能如圖2所示。

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

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

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

4 結(jié)論

北斗B1I信號(hào)是北斗系統(tǒng)的第1個(gè)公開服務(wù)信號(hào)，其目標(biāo)是面向廣大民用市場(chǎng)提供普遍服務(wù)，B1I信號(hào)BCH譯碼算法研究在研制面向區(qū)域服務(wù)的北斗導(dǎo)航接收機(jī)中具有重要作用[15]。校正子輔助的列表譯碼算法在誤碼率 10-5時(shí)，與最大似然譯碼的信噪比僅差0.08 dB，性能非常接近最大似然譯碼算法和Chase譯碼算法，是一種近優(yōu)的軟判決譯碼算法。新算法具有計(jì)算復(fù)雜度低、不要排序運(yùn)算和可并行優(yōu)化等特點(diǎn)，適合工程化實(shí)現(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] 陳金平, 王夢(mèng)麗, 錢曙光. 現(xiàn)代化GNSS導(dǎo)航電文設(shè)計(jì)分析[J].電子與信息學(xué)報(bào), 2011, 33(1): 211-217.

[3] 連帥, 閆利軍, 孫科. 北斗2代衛(wèi)星導(dǎo)航電文糾錯(cuò)校驗(yàn)設(shè)計(jì)與仿真[J]. 計(jì)算機(jī)測(cè)量與控制, 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屆中國(guó)衛(wèi)星導(dǎo)航學(xué)術(shù)年會(huì)(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.