第九章 循环码

本文格式为Word版，下载可任意编辑——第九章循环码

信息论

第九章循环码1

信息论

第九章循环码

内容提要：内容提要：循环码是线性分组码中一个重要的子类。循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述方法，项式描述方法，论述了循环码构成的有关重要定理；定理；接着探讨了循环码的编译码方法及其实现电路，现电路，最终介绍了已获得广泛应用的循环汉明码、码等。明码、BCH码等。码等

信息论

本章重点：本章重点：1.循环码的基本概念；循环码的基本概念；循环码的基本概念2.循环码的编码和译码方法；循环码的编码和译码方法；3.BCH码。码

信息论

9.1循环码的一般概念9.1.1循环码的定义将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。(见图9.1)

信息论

c1:c2:c3:c4:c5:c6:c7:c15:

0001011001011001011001011000第一循环011000111000101000101

0000000

c8:c9:c10:c11:c12:c13:c14:c16:

0011101011101011101001101001其次循环10100110100111100111011111115

图9.1(7,4)汉明码的码字循环图

信息论

定义9.1一个线性分组码，若具有以下特性，则称其为定义循环码。设码字循环码c=(cn-1,cn-2,…,c1,c0)若将码元循环左移一位，得c(1)=(cn-2,…,c1,c0,cn-1)c(1)也是一个码字。

信息论

9.1.2循环码的多项式描述设c=(cn-1cn-2…c1c0)是(n,k)循环码的一个码字，则与其对应的多项式c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0(9-1)称为码字c的码字多项式码字多项式(或码多项式)。码字多项式假使c=(cn-1cn-2…c1c0)是(n,k)循环码的一个码字，则c(1)=(cn-2…c1c0cn-1)也是该循环码的一个码字。这就是说c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0和c(1)(x)=cn-2xn-1+…+c1x2+c0x+cn-1都是(n,k)循环码的码字多项式。7

信息论

比较c(x)和c(1)(x)后可得c(1)(x)=xc(x),modxn-1modxn-1(9-3)定理9.1在以多项式xn-1为模的剩余类全体所构成的n维线定理VV性空间Vn中，其一个子空间Vn,k是一个循环子空间(循环码)的充要条件是：Vn,k是一个理想。一个(n,k)循环码的码字多项式都是模xn-1运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。8

(9-2)

以及c(i)(x)=xic(x)(i=1,2,…,n-1),

信息论

9.1.3循环码的生成多项式定义9.2若一个循环码定义的所有码字多项式都是一个次数最低的非零首一多项式g(x)的倍式，则称g(

x)生成该循环码，并称g(x)为该码的生成元或生成多项式。定理9.2GF(2)上的(n,定理k)循环码中，存在有唯一的n-k次首一多项式g(x)=xn-k+gn-k-1xn-k-1+…+g1x+g0使得每一个码多项式c(x)都是g(x)的倍式，且每一低于或等于n-1次的g(x)倍式，一定是码多项式。

定理9.3(n,k)循环码的生成多项式g(x)一定是xn-1定理的因式：xn-1=g(x)h(x)。反之，若g(x)为n-k次，且除尽xn-1,则此g(x)一定生成一个(n,k)循环码。9

信息论

定理9.4若g(x)是(n,k)循环码的生成多项式，由xn-1=定理g(x)h(x),h(x)是k次多项式，称为校验多项式校验多项式。令校验多项式h(x)=hkxk+hk-1xk-1+…+h1x+h0则0h0h1Lhk0L0hhLh0L001kH=M(9-5)0h0h1Lhk0L为(n-k)n阶矩阵，称为码的校验矩阵校验矩阵。校验矩阵

信息论

综上所述，有如下结论：①(n,k)循环码的生成多项式g(x)是一个次数最低的唯一的首一多项式，其次数r=n-k正好是码字中校验元的数目；②生成多项式g(x)是xn-1的因式。要构造一个(n,k)循环码，就是要在xn-1的因式中找一个n-k次的首一多项式g(x),它的所有次数低于或等于n-1的倍式就构成一个(n,k)循环码。反之，循环码的每一个码字多项式必是g(x)的倍式；③由xn-1=g(x)h(x),h(x)称为校验多项式。对于任意一个(n,k)循环码，必有g(x)h(x)=0modxn-1及GHT=0循环码是线性分组码的一个子类。因此，所有线性分组码的性质均适用于循环码。11

信息论

9.2循环码的编码9.2.1利用生成多项式利用生成多项式g(x)实现编码实现编码若已知g(x)=gn-kxn-k+gn-k-1xn-k-1+…+g1x+g0

并设信息元多项式m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0要编码成系统循环码形式，须用xn-k乘以m(x),再加上校验元多项式r(x),这样得到的码字多项式c(x)为：c(x)=xn-km(x)+r(x)=mk-1xn-1+mk-2xn-2+…+m0xn-k+rn-k-1xn-k-1+…+r1x+r0其中r(x)=rn-k-1xn-k-1+…+r1x+r012

信息论

c(x)一定是g(x)的倍式，即有c(x)=xn-km(x)+r(x)=q(x)g(x)或c(x)=xn-km(x)+r(x)=0,modg(x)

注意到g(x)为n-k次多项式，而r(x)至多为n-k-1次多项式，必有r(x)=xn-km(x),modg(x)即r(x)必是xn-km(x)除以g(x)的余式。(9-6)式指出了系统循环码的编码方法：首先将信息元多项式m(x)乘以xn-k成为xn-km(x);然后将xn-km(x)除以生成多项式g(x)得到余式r(x),该余式就是校验元多项式，从而得到码字多项式c(x)=xn-km(x)+r(x)。13

(9-6)

信息论

9.2.2除法电路设GF(2)上的两个多项式a(x)=akxk+ak-1xk-1+…+a1x+a0b(x)=brxr+br-1xr-1+…+b1x+b0a(x)是被除式，b(x)是除式。用图9.2所示

的电路完成a(x)除以b(x)的运算。

图9.2除法电路的一般形式14

信息论

设被除式a(x)=x4+x+1,除式b(x)=x3+x2+1,完成二例个多项式相除的运算。长除法：

x3+x2+1x4x4+x3x3x3+x2x2

x+1+x+1+1+1

+x

多项式的系数运算

1111011001111011001110110015

信息论

实现以上除法运算的除法电路如图9.3所示

图9.3以b(x)=x3+x2+1为除式的除法电路

信息论

9.2.3编码电路系统循环码的编码方法是：首先将信息元多项式m(x)乘以xn-k成为xn-km(x);然后将xn-km(x)除以生成多项式g(x)得到余式r(x),该余式就是校验元多项式，从而可得码字多项式c(x)=xnkm(x)+r(x)。

信息论

用电路实现编码时可采用以g(x)为除式的除法电路。作为实例，图9.4示出了生成多项式g(x)=x3+x2+1的(7,4)循环码的编码电路。

图9.4以g(x)=x3+x2+1的(7,4)循环码编码器18

信息论

9.3循环码的译码当码字c通过噪声信道传送时