《循环码与bch码》由会员分享，可在线阅读，更多相关《循环码与bch码（70页珍藏版）》请在金锄头文库上搜索。
1、第六章 循环码与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-1C2=cn-3, cn-4, cn-1, cn-2Cn-1=c0,
2、cn-1, c2, c1都是码字例如，第五章中表5-2中所列的(7,3)码，就是具有这 种循环特性的循环码。（P176）关于循环码强调两点：1、本书讨论的循环码首先是一个线性分组码。2、循环码具有循环移位特性。例6-1：判断下面三组码字的特点。000 110 011 101000 100 011 111000 100 010 001C1=C2=C3=C1是线性循环码，C2是非循环的线性分组码， C3是非线性的循环码。码多项式 与n重码相对应的n-1次多项式 C(x)=cn-1xn-1+ cn-2xn-2+ c1x+ c0 6-1称为码多项式。例如：码字C=0010111所对应的码多项式为 C(
3、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+
4、1) (n,k)循环码的每个码字必处在以xn+1为模运算 的剩余类的某一类中。 生成多项式 在(n,k)循环码的2k个码字 中，取一个前k-1位皆为0的码字，此码字 对应有一个次数最低，且为n-k=r的多项式 g(x)，其它码字所对应的码多项式都是g(x) 的倍式，则称g(x)生成该码，并且称g(x)为 该码的生成多项式。可见生成多项式具有以下特征：g(x)= xr+ gr-1xr-1 + + g2x2+ g1x+ g0 g0 0 r=n-k 如果g(x)为(n,k)循环码的最低次多项式，即生成多项式时，xg(x), x2g(x), xk-1g(x)都是码字，这k个码字是独立的，故可作为码的一
5、组生成基底，使每个码多项式都是这一组基底的线性组合。例如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)。 普通代数中全体有理数的集
6、合叫有理域 ，全体实数的集合叫实数域。全体复数 的集合叫复数域。它们都是无限域。 经常用到的有限域是二元域GF(2)，它有 两个元素“0”和“1”，其加法和乘法分别为 ：加法 乘法0+00 0*000+11 0*101+01 1*001+10 1*11 系数在GF(2)中的多项式叫做二元域上的多项式 。二元域上多项式的加减乘除等运算在原理上 和普通代数多项式的运算相同。例如：对码字 多项式 C(x)=cn-1xn-1+ cn-2xn-2+ c1x+ c0有 xi+ xi0, ci+ ci0, ci2=ci . cici 并且减法就是加法。加法符号为“ ”或简记为 “+”。证：因 C2(x) (
7、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
8、)=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 x21 1+ x2x x+x21+x 1+x+x2 既约多项式 又称不可约多项式，它不能分解为次 数更低的多项式的乘积，例如x2 +x + 1和x4 +x +1为不可约多项式，而x2+1不是既约多项式。 因为(x+1)2= x2 +x+x + 1= x2 +1和普通代数一样，对于多项式f(x),
9、如果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+a20，可得a2 1+a=(01)+(10)=11 这样就得到一个具有两位数字的扩域GF(4)，它包 含0、1、a、 a2四个元。第三节 循环码多项式的基本特性(二)在一个(n,k)循环码中，有唯一的一个n-k次多 项式g(x)= xn-k
10、+ 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) 的倍式是码多项式。反
11、之，任意一个码字的码多项式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+ gr-1xr-1 + + g2x2+ g1x+ 1 则g(
12、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
13、的一个因式。反之，当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)
14、循 环移位而成。但是这样编成的循环码不是系统码 。 如要编成前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)循环码的码 多项式。如果令M(X)为单项式xk-ii=0,1,2k-1则Ci(x)=x + r (x)n-ii可以容易看到码多项式Ci(x)对应的码字（或向量）， i=0,1,2k-1是线性无关的，所以这K个码多项式组成 了循环码的系统生成矩阵。系统循环码的生
15、成矩阵为：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
