BCH.ppt

第六章　循环码与BCH码;第一节　基本定义;循环码：设C是码长为n，信息位为k,监督位 为r的(n,k)线性分组码的任意一个码字，如果 C的每一次循环移位也是码字，则把具有这种 循环移位特点的码称为循环码(Cyclic Codes)。;关于循环码强调两点：;码多项式　　与n重码相对应的n-1次多项式 C(x)=cn-1xn-1+ cn-2xn-2+…+ c1x+ c0 [6-1] 称为码多项式。 ;实际上，将(n,k)循环码的一个码字C=[cn-1, cn-2,…, c1, c0] 所对应的码多项式循环左移一位，即相当于对码多项式乘以x并除以xn+1后所得的余式，刚好是将码字C循环移位一次后所得码字(cn-2, cn-3,…, c0,cn-1)的码多项式，即下面关系式成立：;生成多项式　在(n,k)循环码的2k个码字中，取一个前k-1位皆为0的码字，此码字对应有一个次数最低，且为n-k=r的多项式g(x)，其它码字所对应的码多项式都是g(x)的倍式，则称g(x)生成该码，并且称g(x)为该码的生成多项式。; 如果g(x)为(n,k)循环码的最低次多项式，即 生成多项式时，xg(x), x2g(x),…, xk-1g(x)都是 码字，这k个码字是独立的，故可作为码的一 组生成基底，使每个码多项式都是这一组基 底的线性组合。例如P176例5-1 ;第二节　有限域中的运算规则;D：满足分配律a(b+c)=ab+ac,(a+b)c=ac+bc;当域中元素为有限数p时，称为有限域或p元域，有限域理论是由数学家伽罗华（Galols）所创立的，因此又称为伽罗华域，并记为GF(p)。 普通代数中全体有理数的集合叫有理域，全体实数的集合叫实数域。全体复数的集合叫复数域。它们都是无限域。 经常用到的有限域是二元域GF(2)，它有两个元素“0”和“1”，其加法和乘法分别为：;　　加法　　　　　　乘法 　　0+0＝0　　　　　0*0＝0 　　0+1＝1　　　　　0*1＝0 　　1+0＝1　　　　　1*0＝0 　　1+1＝0　　　　　1*1＝1 系数在GF(2)中的多项式叫做二元域上的多项式。二元域上多项式的加减乘除等运算在原理上和普通代数多项式的运算相同。例如：对码字多项式 C(x)=cn-1xn-1+ cn-2xn-2+…+ c1x+ c0有 xi+ xi＝0, ci+ ci＝0, ci2=ci . ci＝ci 并且减法就是加法。加法符号为“　　”或简记为“+”。 ;证：因 C2(x)＝ (cn-1xn-1+ cn-2xn-2+…+ c1x+ c0) 2 =(cn-1xn-1) 2+ 2cn-1xn-1( cn-2xn-2+…+ c1x+ c0) + (cn-2xn-2+…+ c1x+ c0) 2 考虑到cn-1 2 ＝ cn-1，上式包括2作系数的第二项 乘积为0，将第三项类似地逐步展开，就可以 得出 C2(x)＝ cn-1x2(n-1)+ cn-2x2(n-2) +…+ c1x 2 + c0=C(x2);定理：设d(x)和g(x)是二元域上的两个多项式。则有唯一的一对二元域上的多项式q(x)和r(x)。具有下面的性质： 　　d(x)=q(x)g(x)+r(x) 　其中r(x)的次数小于g(x)的次数，叫余式。 　这个定理也称欧几里德(Euclid)除法定理。利用这种余式的唯一性质，按某个次数为m的多项式g(x)的求余运算，可以把所有多项式分为2m个剩余类。;既约多项式 又称不可约多项式，它不能分解为次数更低的多项式的乘积，例如x2 +x + 1和x4 +x +1为不可约多项式，而x2+1不是既约多项式。因为(x+1)2= x2 +x+x + 1= x2 +1;第三节　循环码多项式的基本特性;(二)在一个(n,k)循环码中，有唯一的一个n-k次多项式g(x)= xn-k+ gn-k-1xn-k-1 +… + g2x2+ g1x+ 1，每个为g(x)倍式的小于等于n-1次的多项式一定是码多项式。反之，每一个码多项式C(x)是g(x)的倍式。 ;反之，任意一个码字的码多项式Ci(x)，必定是最低的 非零首－多项式g(x)的倍式。 因为不然的话，将Ci(x)用g(x)除之，将会出现余式b(x)， 即Ci(x)＝a(x)g(x)+b(x)，由此，b(x)= Ci(x)+ a(x)g(x)为 码多项式Ci(x)和g(x)的线性组合，必定也是一个码多项 式。且其次数因其为余式低于g(x)。 这和原来假设g(x)是码多项式集合中次数最低的相矛盾， 故b(x)=0,即Ci(x)是g(x)的倍式： Ci(x)＝a(x)g(x) ;设g(x)不是唯一的，即还有一个同次数的非零首－ 多项式g’(x)= xr+ g’r-1xr-1 +