又称不可约多项式,它不能分解为次数更低的多项式的乘`隥.ppt

第六章 循环码与BCH码,第一节 基本定义,循环码是线性分组码中应用最广泛的一类码它有两个重要的特点：,1、码的结构可以用代数方法来表示、 分析和构造2、利用循环特性，可以用循环反馈移位寄存器来构造较为简单方便的编码器和译码器循环码：设C是码长为n，信息位为k,监督位 为r的(n,k)线性分组码的任意一个码字，如果 C的每一次循环移位也是码字，则把具有这种 循环移位特点的码称为循环码(Cyclic Codes)即如果 C=[cn-1, cn-2,…, c1, c0]是一个码字,则 C1=[cn-2, cn-3,…, c0, cn-1] C2=[cn-3, cn-4,…, cn-1, cn-2] …… Cn-1=[c0, cn-1,…, c2, c1]都是码字,例如，第五章中表5-2中所列的(7,3)码，就是具有这 种循环特性的循环码P176）,关于循环码强调两点：,1、本书讨论的循环码首先是一个线性分组码2、循环码具有循环移位特性例6-1：判断下面三组码字的特点C1是线性循环码，C2是非循环的线性分组码， C3是非线性的循环码码多项式 与n重码相对应的n-1次多项式 C(x)=cn-1xn-1+ cn-2xn-2+…+ c1x+ c0 [6-1] 称为码多项式。

例如：码字C=[0010111]所对应的码多项式为 C(x)=x4+ x2+ x+1,,假如已知码多项式C(x)=x7+ x3+ x+1，则可求 出对应的码字C=10001011,实际上，将(n,k)循环码的一个码字C=[cn-1, cn-2,…, c1, c0] 所对应的码多项式循环左移一位，即相当于对码多项式乘以x并除以xn+1后所得的余式，刚好是将码字C循环移位一次后所得码字(cn-2, cn-3,…, c0,cn-1)的码多项式，即下面关系式成立：,,x(cn-1xn-1+ cn-2xn-2+…+ c1x+ c0) = cn-1xn+ cn-2xn-1+…+ c1x2+ cnx ≡ cn-2xn-1+ cn-3xn-2+…+ c1x2+ cnx+ cn-1 mod(xn+1),(n,k)循环码的每个码字必处在以xn+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,由此看来，找到合适的g(x)是构造循环码的 关键在这方面需要用到有限域的知识第二节 有限域中的运算规则,运算自封：一个集合中的元素经过某种运算（例如加减乘除）后仍为集合中的元素时，称为运算自封域：运算自封元素的集合叫做域F（Field）域中 的元素相加a+b和相乘ab满足下列关系：,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),例6-2 试证明对上述二元域上码多项式C(x), 有C2(x)＝ 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个剩余类例如，m=3的三次多项式g(x)=1+x+x3有2m=23=8个 剩余类 0 x2 1 1+ x2 x x+x2 1+x 1+x+x2,既约多项式 又称不可约多项式，它不能分解为次数更低的多项式的乘积，例如x2 +x + 1和x4 +x +1为不可约多项式，而x2+1不是既约多项式。

因为(x+1)2= x2 +x+x + 1= x2 +1,和普通代数一样，对于多项式f(x),如果f(a)=0,则称a为多项式的根，例如(x+1)2的根为1显然，既约多项式的根不能在二元域内，但是可以像实数根扩展到复数根那样，将既约多项式的根在二元域的扩充域中表示出来以二次既约多项式1+x+x2为例，可以把二元域中的元“0”和“1”扩充一位，表示成0＝(00),1=(01)如果a是1+x+x2的根，则可令a=(10).再由1+a+a2＝0，可得a2＝ 1+a=(01)+(10)=11 这样就得到一个具有两位数字的扩域GF(4)，它包含0、1、a、 a2四个元第三节 循环码多项式的基本特性,(二)在一个(n,k)循环码中，有唯一的一个n-k次多项式g(x)= xn-k+ gn-k-1xn-k-1 +… + g2x2+ g1x+ 1，每个为g(x)倍式的小于等于n-1次的多项式一定是码多项式反之，每一个码多项式C(x)是g(x)的倍式证：令r=n-k，由于g(x)= xr+ gr-1xr-1 +… + g2x2+ g1x+ 1是(n,k)循环码中次数最低的一个非零首－多项式由于码的循环特性，xg(x), x2g(x),…, xn-1-rg(x)也必为码多项式，从而它们的线性组合 (mn-1-rxn-1-r +… + m2x2+ m1x+ m0 )g(x)=M(x) g(x)也必在循环码中，故每一个次数等于或小于n-1次的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 +… + g’2x2+ g’1x+ 1 则g’(x)和g(x)的线性组合g(x)－ g’(x)必定也是码多 项式，且由于首项相消，其次数小于g(x)的次数, 与g(x)是码多项式中次数最低的矛盾 所以g(x)＝ g’(x)， g(x)是唯一的三)(n,k)循环码的生成多项式g(x)是xn+1的因式，反之， 若g(x)是xn+1的一个n-k次因式，则g(x)生成(n,k)循环码证：因g(x)为n-k次，则xk g(x)为n次多项式，用xn+1除之， 由6-5式可得： xkg(x)＝xn+1+Ck(x) 其中Ck(x)为码多项式，总可以写为g(x)的倍式形式， 即Ck(x)＝m(x)g(x) 由此可以得出xn+1＝ (xk+m(x))g(x) 即g(x)是xn+1的一个因式。

反之，当g(x)为n-k次，则它的倍式的线性组合 (m0 + m1x + m2x2 +… mk-1xk-1) g(x)也是码多项式， 系数m0 、 m1、 m2、 mk-1 共有2k种不同组合，正好 构成(n,k)码中k个信息元所形成的2k个码多项式概括地说，要生成一个(n,k)循环码，就是要找到一个能除尽xn+1的r=n-k次首－生成多项式g(x),由g(x)来生成各个码多项式后，找出与码多项式相对应的循环码字第四节 循环码的编码方法,xk-1g(x) … C(x)=[mk-1,…, m1,m0] · xg(x) = MG(x) g(x) 式中G(x)为循环码的生成矩阵，其k行分别由g(x)循环移位而成但是这样编成的循环码不是系统码 如要编成前k位是信息元，后r=n-k位是监督元的n位系 统码，可以先用xn-k乘消息多项式M(x)，再用g(x)去除， 即,,,其中q(x)是商式，r(x)是次数小于n-k的余式于是 C(x)=xn-kM(x)+r(x)=g(x)q(x) 是g(x)的倍式，因而是由g(x)生成(n,k)循环码的码 多项式可以容易看到码多项式Ci(x)对应的码字（或向量）， i=0,1,2…k-1是线性无关的，所以这K个码多项式组成 了循环码的系统生成矩阵。

系统循环码的生成矩阵为： xn-1 + rn-1(x) xn-2 + rn-2(x) C(x)= … … … xn-k+1 + rn-k+1(x) xn-k + rn-k(x) 式中rn-i(x)为xn-i 除以g(x)后所得的余式 是g(x)的倍式，因而是由g(x)生成(n,k)循环码的码多项式解：由于n=7时 x7+1=(x+1)(x3+x+1)(x3+x2+1) 6-14 如选用g(x)= x3+x+1，并考虑到 M=[1101]-M(x)= x3+x2+1 即此处余式r(x)=1，由6-13得出 C(x)=x3(x3+x2+1)+1= x6+x5+x3+1 由此得出对应于消息1101的码字为1101001例6-2 将消息M=[1101]编成(7,4)循环汉明码,解：从6-14中取次数为n-k=4的g(x)，即取 g(x)=(x+1)(x3+x+1)=x4+x3+x2+1 因M=[101]-M(x)= x2+1 故此多项式为 C(x)=x4(x2+1)+x+1= x6+x4+x+1 由此得出对应的编成码字为1010011。

例6-3 将消息M=[101]编成(n,k)=(7,3)循环码,由上面例子可以看出，从xn+1中取不同的n-k次因式作g(x),就得出不同(n,k)循环码一般可写为xn+1 =h(x)g(x) 或,其中h(x)称为监督多项式，次数为k 例如，由x7+1就可以构成如表6-3所示不同k值的循环码 由x7+1的因式构成(7,3)循环码 表6-3 (n,k)码 码距d 生成多项式g(x) 监督多项式h(x) (7,6) 2 。