BCH编码与译码简析.doc

BCH编码自1950年汉明发表了纠正单个随机错误的码以来，几乎用了近十年的时间，才于1959年由霍昆格姆（Hocquenghem），1960年由博斯（Bose）和雷-查德胡里（Ray-Chaudhuri）分别提出了纠正多个随机错误的循环码BCH码（Bose、Ray-Chaudhuri与Hocquenghem的首字母缩写）的构造方法。BCH 码是用于校正多个随机错误模式的多级、循环、错误校正、变长数字编码，是迄今为止所发现的一类很好的线性纠错码类。它的纠错能力很强，特别在短和中等码长下，其性能接近于理论值，并且构造方便，编码简单。特别是它具有严格的代数结构，因此它在编码理论中起着重要的作用。BCH码是迄今为止研究得最为详尽，分析得最为透彻，取得的成果也最多的码类之一。1960年皮德逊（Peterson）从理论上解决了二进制BCH码的译码算法，奠定了BCH码译码的理论基础。稍后，格林斯坦（Gorenstein）和齐勒尔把它推广到了多进制。1966年伯利坎普（Berlekamp）利用迭代算法解BCH码，从而大大加快了译码速度，从实际上解决了BCH码的译码问题。由于BCH码性能优良，结构简单，编译码设备也不太复杂，使得它在实际使用中受到工程技术人员的欢迎，是目前用得最为广泛的码类之一。一、BCH码的构建BCH 码使用有限域上的域论与多项式。为了检测错误可以构建一个检测多项式，这样接收端就可以检测是否有错误发生。要构建一个能够检测、校正两个错误的 BCH 码，我们要使用有限域 GF(16) 或者 Z2x。如果是m1(x) = x4 + x + 1的一个根，那么m1就是的极小多项式，这是因为m1(x) = (x -)(x -2)(x -4)(x -8)=x4 + x + 1。 如果要构建一个能够纠正一个错误的BCH码，那么就使用 m1(x)，这个代码就是所有满足：C(x)0（mod m1(x)）且根为,2,4,8 的多项式 C(x)。 二、BCH码的编码构建码字为(c14, c13, ., c8)，这样多项式为c14+c13+.+c8，我们将它称为CI。然后就要找出CR满足CR=CI (mod m1,3(x)=c7+c6+.+c0这样就得到待发的码字C(x) = CI+CR (mod m1,3(x) = 0例如，如果我们要对 (1,1,0,0,1,1,0) 进行编码CI=x14+x13+x10+x9 然后用m1,3(x) 除以（这里的除法是多项式除法）CI ，得到结果为 CR(x)，在Z2域中，我们可以算出 CR为x3+1 这样，待发的码字为(1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1) 三、BCH码的解码BCH 的解码过程可以分为以下四步：1、计算接收到的向量R的 2t 伴随矩阵； 2、计算错误定位多项式； 3、解多项式，得到错误位置； 4、如果不是二进制 BCH 码，就计算错误位置的误差值。 假设我们收到一个码字向量r，即多项式 R(x)。如果没有错误，那么 R()=R(3)=0如果有一个错误，例如 r=c+ei，其中 ei 表示 R14 的第i个基向量，于是：S1=R () =C () +i=i S3=R (3) =C (3) + (3) i = (i) 3=S13 这样就可以纠正错误。的指数显示的数据位变化可以帮助我们校正错误。如果有两个错误，例如r=c+ei+ej ，那么：S1=R () =C () +i+j S3=R (3) =C (3) + (3) i+ (3) j = (3) i + (3) j 这与 S13 不同，所以我们认为有两个错误。更进一步的代数方法可以帮助校正这两个错误。四、BCH 解码算法流行的BCH解码算法有Peterson Gorenstein Zierler算法和Berlekamp-Massey 算法。现介绍一下Peterson Gorenstein Zierler算法的原理和实现。1、假设Peterson 算法是普通 BCH 解码过程的第二步，这里使用 Peterson 算法计算多项式(x)=1+1X +2X2 + . +2tX2t 的错误定位多项式系数1,2.2t，这样给定 BCH 码(n,k,dmin)，可以校正个错误的Peterson Gorenstein Zierler 算法如下。2、 算法l 首先生成 2t 伴随矩阵l 然后生成元素为 的矩阵 Sttl 生成元素为 的矩阵Ct1l 让表示未知的多项式系数，用 来表示。l 这样就得到矩阵方程 l 如果矩阵 存在行列式，那么我们就可以找到这个矩阵的逆，然后就可以得到的值 l 如果 ，那么按照 if t = 0 then declare an empty error locator polynomial stop Peterson procedure. end set continue from the beginning of Petersons decodingl 在的值确定之后，自然就得到错误定位多项式 l 结束 Peterson procedure。 3、错误定位多项式的因式分解在得到(x)多项式之后，用钱（Chiens）搜索算法就可以得到它的解(x) = ( i X + 1)( j X + 1).( k X + 1)。根据素元的指数幂就能得到接收到的码字中错误的位置，这也就是误差定位多项式名称的由来。4、错误校正对于二进制的 BCH 码，可以直接根据错误定位多项式因数素元指数的位置校正接收到的向量。最后，对这些位置接收到的数值取反，就可以得到正确的 BCH 解码码字。另外也可以使用 Berlekamp-Massey 算法确定错误定位多项式，从而解决 BCH 解码的问题。参考文献 纠错编码的艺术，（美）Robert H.Morelos-Zaragoza著，张立军译，北京交通大学出版社 纠错编码原理与方法，王新梅、肖国镇编著，西安电子科技大学出版社 Federal Standard 1037c: / Galois Field Calculator: http:/www.ge