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

姜恩華，馬 琳

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

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

1 校驗矩陣H

1.1 校驗矩陣的構成

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

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

(1)

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

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

(2)

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

(3)

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

1.2 校驗矩陣的性質

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

K≤t.

(4)

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

Spark(H)≥2t+1.

(5)

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

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

Spark(H)≥2K+1.

(6)

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

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

證明根據(4)式可知，BCH碼的最小距離dmin≥2K+1，由定理1可知，校驗矩陣H線性無關的最大列數為dmin-1，從校驗矩陣H任意抽取2K列必線性無關，所以校驗矩陣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 求解校驗矩陣

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

2.2 求解測量信號

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

S=R·HT.

(7)

2.3 求解差錯圖案

欠定方程為

S=E·HT.

(8)

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

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

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

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

(9)

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

(10)

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

2.4 求解碼字C的估值

把差錯圖案E與收碼R進行模2加運算，由

(11)

3 BCH碼譯碼仿真實驗

3.1 仿真實驗設計

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

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

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

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

圖2 糾正2位錯誤的BCH碼譯碼的誤碼率 圖3 糾正2位錯誤的BCH碼重構碼字的成功率

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

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

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

圖4 糾正3位錯誤的BCH碼譯碼的誤碼率 圖5 糾正3位錯誤的BCH碼重構碼字的成功率

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

4 結論

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