ECC BCH 编码 原理.ppt

* * 3.5 BCH码的译码 根据生成多项式，可以构造出快速的硬件编码器，而对于BCH码的译码，由于它是循环码的一个子类，任何对循环码的标准译码过程都适用于BCH码。下面我们主要讨论专门针对BCH码的更高效的算法: Gorenstein-zierler译码算法 设c(x)为发送码字多项式，e(x)为错误多项式，则接收到的多项式为r(x)=c(x)+e(x) 设y1,y2,…,yw为g(x)在GF(pm)上的根，即g(yi)=0,i=1,2,…,w。因为对某个信息多项式a(x),有c(x)=a(x)g(x),所以c(yi)=0 r(yi)=c(yi)+e(yi)=e(yi), i=1,2,…,w * * 假设BCH码是根据一个域元素a来构造的，考虑错误多项式 e(x)=en-1xn-1+en-2xn-2+…+e1x+e0 其中最多有t个系数为非零(可纠t个错误),假设实际发生了v个错误，其中0≤v≤t。设错误发生在位置i1,i2,…,iv,则错误多项式可写为 其中 为第k个错误的大小，对二元码， * * 对纠错问题，我们必须知道两件事： (1)错误在哪里发生了，即错误的位置 (2)错误程度 因此，未知量为i1,i2,…,iv和 , ,…, ,它们分别表明错误发生的位置和程度。 伴随式可通过对接收到的关于a的多项式计算得到： 定义错误程度 和错误位置 , k=1,2,…,v。其中ik为第k个错误的位置，Xk是与这个位置相关的域元素。 * * 现在伴随多项式可写为 S1=Y1X1+Y2X2+…+YvXv 对j=1,2,…,2t, 我们定义伴随式 Sj=r(aj)=c(aj)+e(aj)=e(aj) 于是我们可得到2t个联立方程组，它有v个错误位置未知量X1,X2,…,Xv和v个错误程度未知量Y1,Y2,…,Yv: * * 定义错误定位多项式 U(x)=Uvxv+Uv-1xv-1+…+U1x+1 这个多项式的根是错误位置的逆 ,k=1,2,…,v,即 U(x)=(1-xX1)(1-xX2)…(1-xXv) 所以，如果我们知道错误定位多项式U(x)的系数，便可以求得错误位置X1,X2,…,Xv。经过一系列代数变换，我们可得如下矩阵： 错误定位多项式的系数可通过对伴随式矩阵M求逆得到！ * * BCH码的译码步骤 作为测试值，令v=t，计算伴随矩阵M的行列式。如果行列式的值为零，令v=t-1,再一次计算M的行列式。重复这个过程直到找到一个v值，使伴随矩阵的行列式不为0，该v值就是实际产生错误的数目。 求M的逆，并计算错误定位多项式U(x)的系数； 求解U(x)=0的零点，从中可计算错误位置X1,X2,…,Xv。如果是二元码，就到此为止(因为错误程度为1); 如果不是二元码，回到方程组 解这些方程组就得到错误程度 * * 例3.7 考虑纠3个错误的BCH(15,5)码，它的生成多项式为g(x)=x10+x8+x5+x4+x2+x+1 设传输的是全0码字，接收到的多项式为r(x)=x5+x3,故有两个错误分别在第4个位置和第6个位置，错误多项式为e(x)=x5+x3。但译码器并不知道这些，它连实际发生了几个错误都不知道！ 解：利用Gorenstein-aierler译码算法，首先用GF(16)上的算术计算出伴随式 S1=a5+a3=a11, S2=a10+a6=a7 S3=a15+a9=a7, S4=a20+a12=a14 S5=a25+a15=a5, S6=a30+a18=a14 因为这是个纠3个错的码，首先令v=t=3 * * Det(M)=0, 这表明发生的错误数少于3个。 下面令v=2 Det(M) ≠ 0, 这表明实际发生了2个错误。 下面计算M-1 * * 求解U1和U2可得U2=a8及U1=a11, 从而 U(x)=a8x2+a11x+1=(1+xa5)(1+xa3) 因此恢复出来的错误位置为a5和a3。因为该码是二元码，错误程度为1，故e(x)=x5+x3。 # * * 3.6 戈雷(Golay)码 在第9页中，我们曾给出一些部分非本原BCH码的列表，Golay码就是(23,12)码。由表可查出，其生成多项式 (5343)8=101 011 100 011 即 g1(x)=x11+x9+x7+x6+x5+