姜恩華，馬 琳

(淮北師范大學(xué)物理與電子信息學(xué)院，安徽 淮北 235000)

BCH碼是循環(huán)碼的一個(gè)子類，屬于線性分組碼的范疇.對(duì)于二進(jìn)制本原的BCH碼，在給定碼長(zhǎng)n的條件下，可以根據(jù)糾錯(cuò)能力t，設(shè)計(jì)出二元本原BCH碼.BCH碼通用的經(jīng)典譯碼算法是Berlekamp(BM)迭代譯碼算法.[1]近年來(lái)，BCH被應(yīng)用于北斗系統(tǒng)中，并提出了相應(yīng)的譯碼算法.[2-4]本文借助無(wú)噪條件下的壓縮感知理論[5-7]，提出了BCH碼的一種譯碼方法，該方法通過(guò)收碼R和校驗(yàn)矩陣H求出伴隨式S，把S作為測(cè)量信號(hào)、H作為測(cè)量矩陣，通過(guò)基追蹤BP算法重構(gòu)出差錯(cuò)圖案E，把E與收碼R進(jìn)行模2加運(yùn)算，求出發(fā)碼C的估值. 本文研究了BCH碼的校驗(yàn)矩陣H的稀疏度Spark和約束等距性RIP[8-9]，設(shè)計(jì)了基于校驗(yàn)矩陣H的BCH碼譯碼的仿真實(shí)驗(yàn)方案，以(15，5)、(15，7)、(31，16)和(31，21)BCH碼為例，通過(guò)誤碼率和碼字C重構(gòu)的成功率，分析比較了本文提出的算法和BM迭代譯碼算法的譯碼效果.

1 校驗(yàn)矩陣H

1.1 校驗(yàn)矩陣的構(gòu)成

BCH碼的校驗(yàn)矩陣H可以通過(guò)生成矩陣G的系統(tǒng)形式直接生成[10]，公式為

G=[Ik，P]，H=[PT，In-k]，

(1)

BCH碼的生成矩陣G可以通過(guò)其生成多項(xiàng)式g(x)求出.根據(jù)BCH碼的碼長(zhǎng)n和信息元組長(zhǎng)度k，通過(guò)MATLAB語(yǔ)句bchgenpoly(n，k)直接求得生成多項(xiàng)式g(x). 以(15，7)BCH碼為例，通過(guò)MATLAB函數(shù)bchgenpoly(15，7)求得生成的多項(xiàng)式為

g157(x)=x8+x7+x6+x4+1.

(2)

根據(jù)生成多項(xiàng)式g157(x)，求出其生成矩陣G，化簡(jiǎn)為系統(tǒng)形式G157，根據(jù)(1)式，求出其校驗(yàn)矩陣H157，公式為：

(3)

(15，7)BCH碼的糾錯(cuò)能力t為2，有1位和2位差錯(cuò)的收碼R能夠被糾正，即差錯(cuò)圖案E的稀疏度K的最大值為2，由(3)式可知，校驗(yàn)矩陣H157的稀疏度Spark為5.[11]

1.2 校驗(yàn)矩陣的性質(zhì)

對(duì)于隨機(jī)差錯(cuò)來(lái)說(shuō)，BCH碼的差錯(cuò)圖案E可以看做是一維稀疏數(shù)字信號(hào)，只要差錯(cuò)圖案E的稀疏度K小于或等于糾錯(cuò)能力t，就可以在譯碼時(shí)實(shí)現(xiàn)對(duì)收碼的糾錯(cuò).完全糾錯(cuò)時(shí)，稀疏度K與糾錯(cuò)能力t的關(guān)系為

K≤t.

(4)

定理1校驗(yàn)矩陣H的稀疏度Spark與糾錯(cuò)能力t的關(guān)系為

Spark(H)≥2t+1.

(5)

證明校驗(yàn)矩陣H的稀疏度Spark為校驗(yàn)矩陣H中線性相關(guān)的最小列數(shù)，若BCH碼的最小距離為dmin，校驗(yàn)矩陣H線性無(wú)關(guān)的最大列數(shù)為dmin-1[10]，所以，校驗(yàn)矩陣H線性相關(guān)的最小列數(shù)為dmin，而B(niǎo)CH碼的最小距離為dmin≥2t+1，所以(5)式成立.

定理2校驗(yàn)矩陣H的稀疏度Spark與差錯(cuò)圖案E的稀疏度K的關(guān)系為

Spark(H)≥2K+1.

(6)

證明把(4)式代入(5)式求得(6)式成立.

定理3校驗(yàn)矩陣H滿足2K階約束等距性RIP，其中K為差錯(cuò)圖案E的稀疏度.即任意從校驗(yàn)矩陣H抽出2K列必線性無(wú)關(guān).

證明根據(jù)(4)式可知，BCH碼的最小距離dmin≥2K+1，由定理1可知，校驗(yàn)矩陣H線性無(wú)關(guān)的最大列數(shù)為dmin-1，從校驗(yàn)矩陣H任意抽取2K列必線性無(wú)關(guān)，所以校驗(yàn)矩陣H滿足2K階約束等距性RIP.

可以驗(yàn)證(15，7)BCH碼的校驗(yàn)矩陣H157滿足定理1、定理2和定理3.(15，7)BCH碼的糾錯(cuò)能力t為2，有1位和2位差錯(cuò)的收碼R能夠被糾正，即差錯(cuò)圖案E的稀疏度K的最大值為2，由(3)式可知，校驗(yàn)矩陣H157的稀疏度Spark為5，可以驗(yàn)證校驗(yàn)矩陣H157的稀疏度Spark符合定理1和定理2，滿足2K階的約束等距性RIP.

2 基于校驗(yàn)矩陣H的BCH碼譯碼方法

2.1 求解校驗(yàn)矩陣

根據(jù)BCH碼的碼字C的長(zhǎng)度n和信息分組m的長(zhǎng)度k，借助MATLAB函數(shù)bchgenpoly(n，k)求得BCH碼的生成多項(xiàng)式g(x)，根據(jù)g(x)求出(n，k)BCH碼生成矩陣G的系統(tǒng)形式，然后求出(n，k)BCH碼的校驗(yàn)矩陣H，把校驗(yàn)矩陣H作為壓縮感知理論中的測(cè)量矩陣.

2.2 求解測(cè)量信號(hào)

由收碼R和校驗(yàn)矩陣H，通過(guò)(7)式計(jì)算出伴隨式S，把伴隨式S作為壓縮感知理論中的測(cè)量信號(hào)，公式為

S=R·HT.

(7)

2.3 求解差錯(cuò)圖案

欠定方程為

S=E·HT.

(8)

(8)式有n個(gè)未知數(shù)，有n-k個(gè)方程.把S代入(8)式，求解差錯(cuò)圖案E.

在二元域內(nèi)，每個(gè)伴隨式S，可以代入(8)式求出2k個(gè)差錯(cuò)圖案E，根據(jù)最佳概率譯碼的準(zhǔn)則，選取重量最輕的E作為其估值.

在二元域內(nèi)，差錯(cuò)圖案E的重量為差錯(cuò)圖案E中1的個(gè)數(shù)，即差錯(cuò)圖案E的l0范數(shù)或l1范數(shù)的值，求重量最輕的差錯(cuò)圖案E為求差錯(cuò)圖案E的l0范數(shù)或l1范數(shù)的最小值.可以借助壓縮感知理論，把伴隨式S作為測(cè)量信號(hào)，校驗(yàn)矩陣H作為測(cè)量矩陣[12-13]，通過(guò)壓縮感知重構(gòu)算法求解差錯(cuò)圖案E的l0范數(shù)或l1范數(shù)的最小值，重構(gòu)差錯(cuò)圖案E的壓縮感知模型為：

min‖E‖0s.t.H·ET=ST；

(9)

min‖E‖1s.t.H·ET=ST.

(10)

求解(9)式可以采用OMP重構(gòu)算法，求解(10)式可以采用基追蹤BP重構(gòu)算法.本文選用基追蹤BP算法根據(jù)(10)式重構(gòu)出差錯(cuò)圖案E.

2.4 求解碼字C的估值

把差錯(cuò)圖案E與收碼R進(jìn)行模2加運(yùn)算，由

(11)

3 BCH碼譯碼仿真實(shí)驗(yàn)

3.1 仿真實(shí)驗(yàn)設(shè)計(jì)

由于BCH碼屬于線性分組碼，所以可按照線性分組碼的編譯碼過(guò)程實(shí)現(xiàn)基于校驗(yàn)矩陣的BCH碼的編譯碼實(shí)驗(yàn)設(shè)計(jì)[10].首先，借助BCH碼的生成多項(xiàng)式求出其生成矩陣G和校驗(yàn)矩陣H.其次，隨機(jī)產(chǎn)生10 000個(gè)信息分組m，按照C=mG生成BCH碼的碼字；碼字C也可以調(diào)用MATLAB的函數(shù)bchenc生成[14].再次，對(duì)碼字C進(jìn)行2PSK調(diào)制，已調(diào)信號(hào)通過(guò)高斯白噪聲信道AWGN，信噪比SNR取值為0～12 dB，每個(gè)SNR點(diǎn)取10 000個(gè)碼字.最后，在接收端對(duì)接收信號(hào)進(jìn)行2PSK解調(diào)，得到收碼R；代入式(7)求出伴隨式S，把S作為測(cè)量信號(hào)，校驗(yàn)矩陣H作為測(cè)量矩陣，通過(guò)基追蹤BP算法[15-16]重構(gòu)出差錯(cuò)圖案E，將E與收碼R進(jìn)行模2加運(yùn)算，求得碼字C的估值；也可以調(diào)用MATLAB函數(shù)bchdec譯碼[10]，求得碼字C的估值，函數(shù)bchdec采用BM迭代譯碼算法實(shí)現(xiàn)譯碼.仿真實(shí)驗(yàn)方案如圖1所示.通過(guò)誤碼率和碼字C重構(gòu)的成功率分析譯碼效果.

圖1 線性分組碼的編碼和譯碼過(guò)程

3.2 糾正2位錯(cuò)誤的BCH碼的譯碼效果分析

以(15，7)和(31，21)BCH碼為例，按照仿真實(shí)驗(yàn)步驟，借助MATLAB軟件編寫(xiě)腳本程序，進(jìn)行仿真實(shí)驗(yàn)，分別采用BP算法和BM迭代譯碼算法完成譯碼，仿真實(shí)驗(yàn)求得的誤碼率如圖2所示，碼字重構(gòu)的成功率如圖3所示.

圖2 糾正2位錯(cuò)誤的BCH碼譯碼的誤碼率 圖3 糾正2位錯(cuò)誤的BCH碼重構(gòu)碼字的成功率

從圖2可以看出，相同碼長(zhǎng)n情況下，BP算法的誤碼率低于BM迭代譯碼算法；當(dāng)SNR為8 dB 時(shí)，BP算法的誤碼率低于10-4；當(dāng)SNR為9 dB時(shí)，BM迭代譯碼算法的誤碼率低于10-4.從圖3可以看出，相同SNR情況下，BP算法的重構(gòu)碼字的成功率高于BM迭代譯碼算法，當(dāng)SNR為6 dB時(shí)，BP算法的重構(gòu)碼字的成功率近似為100%；當(dāng)SNR為7 dB時(shí)，BM迭代譯碼算法的重構(gòu)碼字的成功率近似為100%.

3.3 糾正3位錯(cuò)誤的BCH碼的譯碼效果分析

以(15，5)和(31，16)BCH碼為例，分別采用BP算法和BM迭代譯碼算法完成譯碼.按照仿真實(shí)驗(yàn)步驟，編寫(xiě)MATLAB腳本程序進(jìn)行仿真實(shí)驗(yàn)，誤碼率如圖4所示，碼字C重構(gòu)的成功率如圖5所示.

圖4 糾正3位錯(cuò)誤的BCH碼譯碼的誤碼率 圖5 糾正3位錯(cuò)誤的BCH碼重構(gòu)碼字的成功率

從圖4可以看出，相同信噪比SNR條件下，基追蹤BP算法的誤碼率低于BM算法，當(dāng)SNR為9 dB時(shí)，基追蹤BP算法的誤碼率低于10-4，BM迭代譯碼算法譯碼的誤碼率近似為10-4.從圖5 可以看出，相同信噪比SNR條件下，基追蹤BP算法的重構(gòu)碼字的成功率高于BM迭代譯碼算法；當(dāng)SNR為6 dB時(shí)，基追蹤BP算法重構(gòu)碼字的成功率近似為100%；當(dāng)SNR為7 dB時(shí)，BM迭代譯碼算法重構(gòu)碼字的成功率近似為100%.

4 結(jié)論

本文提出了基于校驗(yàn)矩陣的BCH碼譯碼方法.首先，證明了校驗(yàn)矩陣H滿足壓縮感知的測(cè)量矩陣的2K階約束等距性RIP，并提出了3個(gè)定理；其次，提出了重構(gòu)BCH碼差錯(cuò)圖案E的壓縮感知模型；再次，設(shè)計(jì)了基于校驗(yàn)矩陣的BCH碼譯碼實(shí)驗(yàn)方案，以糾正2位錯(cuò)誤的(15，7)和(31，21)BCH碼和糾正3位錯(cuò)誤的(15，5)和(31，16)BCH碼為例，分析比較了基追蹤BP算法和BM迭代譯碼算法的譯碼效果.仿真實(shí)驗(yàn)表明，基于校驗(yàn)矩陣的BCH碼譯碼方法是可行和有效的.