基于校驗矩陣的BCH碼譯碼方法的研究

姜恩華，馬 琳

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

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

1 校驗矩陣H

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

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

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

(1)

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

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

(2)

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

(3)

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

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

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

K≤t.

(4)

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

Spark(H)≥2t+1.

(5)

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

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

Spark(H)≥2K+1.

(6)

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

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

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

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

2 基于校驗矩陣H的BCH碼譯碼方法

2.1 求解校驗矩陣

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

2.2 求解測量信號

由收碼R和校驗矩陣H，通過(7)式計算出伴隨式S，把伴隨式S作為壓縮感知理論中的測量信號，公式為

S=R·HT.

(7)

2.3 求解差錯圖案

欠定方程為

S=E·HT.

(8)

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

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

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

2.4 求解碼字C的估值

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

(11)

3 BCH碼譯碼仿真實驗

3.1 仿真實驗設(shè)計

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

圖1 線性分組碼的編碼和譯碼過程

3.2 糾正2位錯誤的BCH碼的譯碼效果分析

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

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

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

3.3 糾正3位錯誤的BCH碼的譯碼效果分析

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

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

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

4 結(jié)論

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