信息与编码理论 第2版 课件 6.2 BCH码

§6.2BCH码6.2.1BCH码的结构BCH码是一种循环码，因此也可以用生成多项式来描述。接下来介绍一种被称作本原二进制BCH码（PrimitiveBinaryBCHCode）的编码和译码方法。码长为，其中整数。对于任意的，这种码可以纠正不少于个错误。实际上，对于任意两个正整数和，均可以设计一个参数满足下列关系的BCH码：

(6-7)6.2.2BCH码的生成多项式为了生成一个能纠正个错误的BCH码，可以从有限域中选取一个本原元素，那么以为根的上的最低阶多项式便是该码的生成多项式。因为上任何以为根的多项式均可以被的最小多项式整除。因此，生成多项式一定可以被的最小多项式整除，其中，又因为应为满足该条件的最低阶多项式，于是可得

(6-8)另外，考虑到共轭类中元素的最小多项式相同，故在确定生成多项式时仅考虑奇数值的就够了，于是

(6-9)因为最小多项式的阶不会超过，于是的阶最多为，所以假设是BCH码的任一码字多项式，那么根据循环码的性质可知该码的生成多项式将是一个因式，故对应于的所有都将是的根，

(6-10)这是判断一个阶小于的多项式是否为一个合法BCH码字多项式的充要条件。【例6-6】设计一个能够纠正单个错误的BCH码，要求码长。【解】由题意可知，。选取上的一个本原元素，则由例6-5的结果可知的最小多项式为，显然该式是一个阶为4的本原多项式。于是，该BCH码的生成多项式为

由上式可知，。因为对于BCH码有，而观察上式后可知对应码字向量的重量为3，所以可确定。综上，该BCH码是一个可以纠正1个错误的码，其最小码距为3，实际上该码是一个循环汉明码（CyclicHammingCode）。一般而言，循环汉明码是可以纠正单个错误的BCH码。【例6-7】设计一个能够纠正四个错误的BCH码，要求码长。【解】由题意可知，。仍然假设是上的一个本原元素，那么由例6-5的结果可知，，，的最小多项式分别为因此生成多项式为

由上式可知，，该码的最小码距。因此该BCH码是一个重复码（RepetitionCode）。该BCH码是按照纠正4个错误来设计的，但实际上该码可以纠正最多7个错误。【例6-8】设计一个能够纠正两个错误的BCH码，要求码长。【解】由题意可知，。仍设表示上的一个本原元素，且由例6-5的结果可知和的最小多项式分别为因此，该BCH码的生成多项式为

由上式可知，。因为对于BCH码有，而观察上式可知对应的码字向量的重量为5，所以可确定。6.2.3BCH码的译码设码字向量对应的码字多项式为，则对于均有。如果传输过程中的错误多项式为，那么接收多项式为

(6-11)于是，可以将与上式对应的伴随式定义为

(6-12)该伴随式可以通过对接收向量使用域运算来计算得到。如果传输过程中没有发生错误，那么，则伴随式为零。假设在码字向量的传输过程中共有个错误发生，且，其中是该码的纠错能力，将这些错误的具体位置分别记作。不失一般性，假设，于是

(6-13)将式(6-13)带入式(6-12)，可得

(6-14)

(6-14)式(6-14)给出的方程组中共有个方程，以及个未知数：或者是等效的通过解该方程组便可以求得个未知数，进而可得错误位置。一旦得到错误位置，便可以对应修改这些位置的接收比特从而得到发射码字的估计值。定义为错误位置数（ErrorLocationNumber），其中，则式(6-14)可以改写为

(6-15)通过解该方程组可以求得个未知数，于是可以进一步确定个错误位置。由于是中的元素，故在解上面方程组时应使用内的运算规则。为了解方程组，定义错误定位多项式（ErrorLocatorPolynomial）为

(6-16)显然，上式的根为，，求解该多项式的根即可确定错误的位置。将式(6-16)展开之后可得

(6-17)利用式(6-15)和式(6-17)，可得的系数与伴随式之间的关系如下

(6-18)接下来，需要求得系数满足上面这些方程的最低阶多项式。在确定之后，便可以求得其根，再由这些根的逆即可得到错误的位置。求根时，可以将中所有个元素分别代入进行验证。6.2.4BCH码的Berlekamp-Massey译码算法BM迭代译码算法首先找到满足式(6-18)中第一个等式的最低阶多项式，然后验证其是否也满足第二个等式，并根据验证结果分别做如下处理：如果满足第二个等式，则记；如果不满足第二个等式，则引入一个修正项从而得到，使其为满足前两个等式的最低阶多项式；重复该过程，直到获得一个同时满足式(6-18)中所有等式的最低阶多项式。假设下式表示满足式(6-18)中前个等式的最低阶多项式

(6-19)为了确定，可以计算求得第个偏差（Discrepancy），如下式

(6-20)如果，表明满足前个等式，于是有

(6-21)如果，则需要对进行修正来获得，如下式

(6-22)式中，且其选择原则为满足的所有中使得值最大的那个，其中表示的阶。这样得到的是满足式(6-18)中前个等式的最低阶多项式。重复该过程直到获得，该多项式的阶就是错误比特的个数，其根可以用来确定错误的位置。如果的阶大于，则表明接收向量中错误个数多于，此时不能进行纠正。综上，Berlekamp-Massey译码算法的初始条件如表6-7所示，然后可以按照上述方法来迭代进行。表6-7Berlekamp-Massey算法【例6-9】考虑例6-8中可以纠正2个错误的BCH码，并利用Berlekamp-Massey算法对下列接收向量进行译码【解】该接收向量对应的接收多项式为，于是可得伴随式为

在上面4个伴随式的计算过程中用到了表6-6中的结论。接下来，便可以按照表6-7中给出的Berlekamp-Massey算法来进行译码。当的时候，由表6-7可得当的时候，有当

的时候，有

当的时候，有综上，可知

观察上式，可知错误定位多项式的阶为2，表示接收向量中有2位错误，所以对应了一个可以纠正的错误图样，因此只需要求得该多项式的根便可以得到