第九章循环码

1、第九章第九章 循环码循环码第九章第九章 循环码循环码 内容提要内容提要循环码是线性分组码中一个重要的子类。本章首循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码介绍了已获得广泛应用的循环汉明码等。等。 9.1.1 循环码的定义循环码的定义 将任一码字中的将任一码字中的7个码元排在一个圆周上，则从圆周的个码元排在一个圆周上

2、，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图一个码字。这就是循环码的由来。（见图9.1） 9.1 9.1 循环码的一般概念循环码的一般概念定义定义9.1 一个线性分组码，若具有下列特性，称为一个线性分组码，若具有下列特性，称为循环循环码码。设码字。设码字c（cn-1，cn-2，c1，c0）若将码元左移一位，得若将码元左移一位，得c (1)（cn-2，c1，c0，cn-1）c (1)也是一个码字。也是一个码字。表表 8-2 (7,4)码的码字表码的码字表 图图9.1 9.1 （7，4）汉明码的

3、码字循环图）汉明码的码字循环图1000101:1100010:0110001:1011000:0101100:0010110:0001011:7654321c cc cc cc cc cc cc c0000000:15c c第一循环第一循环1001110:0100111:1010011:1101001:1110100:0111010:0011101:141312111098c cc cc cc cc cc cc c第二循环第二循环1111111:16c c9.1.2 循环码的多项式描述循环码的多项式描述设设c（cn-1 cn-2 c1 c0）是是（n，k）循环码的一个码字，则循环码的一个码字，

4、则与其对应的多项式与其对应的多项式 c (x)cn-1xn-1cn-2xn-2c1xc0 (9 (91)1) 称为码字称为码字c的的码字多项式码字多项式（或码多项式）。（或码多项式）。 如果如果c（cn-1 cn-2 c1 c0）是（是（n，k）循环码的一个码循环码的一个码字，则字，则c (1)（cn-2 c1 c0 cn-1）也是该循环码的一个码字。也是该循环码的一个码字。这就是说这就是说c (x)cn-1xn-1cn-2xn-2c1xc0 和和 c (1) (x)cn-2xn-1c1x2c0 xcn-1都是（都是（n，k）循环码的码字多项式。循环码的码字多项式。 比较比较c(x)和和c (

5、1) (x)后可得后可得 c (1) (x)x c (x), , mod xn1 (9(92)2)以及以及 c(i) (x)xic (x) （i1, ,2, , ,n1）, , mod xn1 (9 (93)3) 定理定理9.1 在以多项式在以多项式xn1为模的剩余类全体所构成的为模的剩余类全体所构成的n维线维线性空间性空间Vn中，其一个子空间中，其一个子空间Vn,k是一个循环子空间（循环码）是一个循环子空间（循环码）的充要条件是：的充要条件是：Vn,k是一个是一个理想理想。 一个（一个（n，k）循环码的码字多项式都是模循环码的码字多项式都是模xn1运算下多运算下多项式剩余类项式剩余类环环中的

6、一个理想，而且一定是一个中的一个理想，而且一定是一个主理想子环主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。循环码。 9.1.3 9.1.3 循环码的生成多项式循环码的生成多项式定理定理9.2 GF( (2) )上的（上的（n，k）循环码中，存在有唯一的循环码中，存在有唯一的nk次首一多项式次首一多项式 g( (x) )xn-k gn-k-1xn-k-1 g1xg0使得每一个码多项式使得每一个码多项式c (x)都是都是g( (x) )的倍式，且每一低于的倍式，且每一低于或等于或等于n1次的次的g( (x) )倍式，一定是

7、码多项式。倍式，一定是码多项式。 定理定理9.3 （n，k）循环码的生成多项式循环码的生成多项式g( (x) )一定是一定是xn1的因式：的因式：xn1g( (x) )h( (x) )。反之，若反之，若g( (x) )为为nk次，且除次，且除尽尽xn1，则此则此g( (x) )一定生成一个（一定生成一个（n，k）循环码。循环码。定义定义9.2 若一个循环码的所有码字多项式都是一个次数若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式最低的非零首一多项式g( (x) )的倍式，则称的倍式，则称g( (x) )生成该码，生成该码，并称并称g( (x) )为该码的生成元或生成多项式。为该码

8、的生成元或生成多项式。循环码的生成矩阵常用多项式的形式来表示循环码的生成矩阵常用多项式的形式来表示 1)(111xgxgxxgrrr)()()()()(21xgxxgxgxxgxxGkk其中其中 即即 例如例如(7,3)循环码，循环码，n=7, k=3, r=4, 其生成多项式其生成多项式及生成矩阵分别为及生成矩阵分别为 定理定理9.4 若若g( (x) )是（是（n，k）循环码的生成多项式，循环码的生成多项式，由由xn1g( (x) )h( (x) )，h( (x) )是是k次多项式，称为次多项式，称为校验校验多项式多项式。令。令h( (x) )hkxkhk-1xk-1h1xh0则则 (9(

9、95)5)为（为（nk） n阶矩阵，称为码的阶矩阵，称为码的校验矩阵校验矩阵。kkkhhhhhhhhh1010100000000H H监督矩阵监督矩阵 h(x)是常数项为是常数项为1的的k次多项式，称为次多项式，称为监督监督多项式多项式。同理，可得监督矩阵。同理，可得监督矩阵H )(*)(*)(*)(1xhxxhxhxxHkn（n，k）循环码的生成多项式循环码的生成多项式g( (x) )是一个次数最低的唯一是一个次数最低的唯一的首一多项式，其次数的首一多项式，其次数rnk正好是码字中校验元的数目；正好是码字中校验元的数目； 生成多项式生成多项式g( (x) )是是xn1的因式。要构造一个（的因

10、式。要构造一个（n，k）循环码，就是要在循环码，就是要在xn1的因式中找一个的因式中找一个nk次的首一多项次的首一多项式式g( (x) )，它的一切倍式就构成一个（它的一切倍式就构成一个（n，k）循环码。反之，循环码。反之，循环码的每一个码字多项式必是循环码的每一个码字多项式必是g( (x) )的倍式；的倍式； 综上所述，综上所述，有如下结论：有如下结论： 由由xn1g( (x) )h( (x) )，h( (x) )称为校验多项式。对于任意称为校验多项式。对于任意一个（一个（n，k）循环码，必有循环码，必有g( (x) )h( (x) )0 mod mod xn1及及 GH T 0 循环码是线

11、性分组码的一个循环码是线性分组码的一个子类子类。因此，所有线性分组。因此，所有线性分组码的性质均适用于循环码。码的性质均适用于循环码。 9.2 9.2 循环码的编码循环码的编码 9.2.1 9.2.1 利用生成多项式利用生成多项式g(x)g(x)实现编码实现编码 若已知若已知 g( (x) )gn-kxn-kgn-k-1xn-k-1g1xg0并设信息元多项式并设信息元多项式 m( (x) )mk-1xk-1mk-2xk-2m1xm0要编码成系统循环码形式，须用要编码成系统循环码形式，须用xn-k乘以乘以m( (x) )，再加上校验再加上校验元多项式元多项式r( (x) )，这样得到的码字多项式

12、这样得到的码字多项式c( (x) )为：为： c( (x) )xn-k m( (x) )r( (x) )mk-1xn-1mk-2xn-2m0 xn-krn-k-1xn-k-1r1xr0其中其中 r( (x) )rn-k-1xn-k-1r1xr0c( (x) )一定是一定是g( (x) )的倍式，即有的倍式，即有c( (x) )xn-km( (x) )r( (x) )q( (x) )g( (x) ) 或或 c( (x) )xn-km( (x) )r( (x) )0， mod g( (x) )注意到注意到g( (x) )为为nk次多项式，而次多项式，而r( (x) )至多为至多为nk1次多项式，次

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

14、n-km( (x) )r( (x) )。9.2.2 9.2.2 除法电路除法电路 设设GF( (2) )上的二个多项式上的二个多项式a( (x) )akxkak-1xk-1a1xa0b( (x) )brxrbr-1xr-1b1xb0a( (x) )是被除式，是被除式，b( (x) )是除式。用图是除式。用图9.2所示的电路完成所示的电路完成a( (x) )除以除以b( (x) )的运算的运算 。图图9.2 9.2 除法电路的一般形式除法电路的一般形式 【例【例9.2】设被除式】设被除式a( (x) )x4x1，除式除式b( (x) )x3x21，完成完成二个多项式相除的运算。二个多项式相除的运

15、算。11111223334423xxxxxxxxxxxx11001101110011011110011011长除法：长除法： 多项式的系数运算多项式的系数运算 实现以上除法运算的除法电路如图实现以上除法运算的除法电路如图9.3所示所示 图图9.3 9.3 以以b( (x) )x3x21为除式的除法电路为除式的除法电路 9.2.3 编码电路编码电路 然后将然后将xn-km(x)除以生成多除以生成多项式项式g(x)得到余式得到余式r(x)，该余该余式就是校验元多项式，从而式就是校验元多项式，从而可得码字多项式可得码字多项式 c(x)xn-km(x)r(x)。 系统循环码的编码方法是：系统循环码的编

16、码方法是： 首先将信息元多首先将信息元多项式项式m(x)乘以乘以xn-k成为成为xn-km(x)；用电路实现编码时可采用以用电路实现编码时可采用以g( (x) )为除式的除法电路。作为为除式的除法电路。作为实例，图实例，图9.49.4示出了生成多项式示出了生成多项式g( (x) )x3x21 1的（的（7，4）循环码的编码电路。循环码的编码电路。 图图9.4 9.4 以以g( (x) )x3x21的（的（7，4）循环码编码器）循环码编码器 码长码长n=7的循环码：的循环码：6）5）4）（）（7,3）循环码，生产多项式为）循环码，生产多项式为 g(x)（x3x21)(x+1)码多项式为码多项式为

17、) 1)()(2342210 xxxxaxaaxc9.3 9.3 循环码的译码循环码的译码 当码字当码字c通过噪声信道传送时，会受到干扰而产生错误。如信道通过噪声信道传送时，会受到干扰而产生错误。如信道产生的错误图样是产生的错误图样是e，译码器收到的译码器收到的n重接收矢量是重接收矢量是y，则表示为则表示为y c e上式也可写成多项式形式：上式也可写成多项式形式： y(x) )c( (x) )e( (x) (9) (97)7) 循环码的译码可按以下三个步骤进行：循环码的译码可按以下三个步骤进行：（）（）根据伴随式根据伴随式s( (x) )找出对应的估值错误图样找出对应的估值错误图样 ；)( x

18、e（）（）计算计算 ，得到估值码字，得到估值码字 。若。若，则译码正确，否则，若，则译码正确，否则，若 ，则译码错误。，则译码错误。)( )()( xexyxc)( xc)()( xcxc)()( xcxc（）（）由接收到的由接收到的y( (x) )计算伴随式多项式计算伴随式多项式s( (x) )；9.3.1 9.3.1 伴随式计算伴随式计算 对于（对于（n，k）循环码，可以定义码的生成多项式循环码，可以定义码的生成多项式g( (x) )除以除以接收码字多项式接收码字多项式y( (x) )的余式为伴随式多项式的余式为伴随式多项式s( (x) )，写写 s( (x) )y( (x) ) mod

19、g( (x) (9) (98)8)由于由于 y( (x) )c( (x) )e( (x) )而而 c( (x) ) mod g( (x) )0于是于是 s( (x) )e( (x) ) mod g( (x) (9) (99)9) s( (x) )伴随式计算电路的一个重要性质伴随式计算电路的一个重要性质：定理定理9.5 设设s( (x) )是接收码字多项式是接收码字多项式r( (x) )的伴随式。则的伴随式。则y( (x) )的一的一次循环移位次循环移位xy( (x) )（mod xn1）的伴随式的伴随式s(1)(1)( (x) )，是是s( (x) )在伴在伴随式计算电路中无输入时，右移一位的

20、结果（称为自发运算）：随式计算电路中无输入时，右移一位的结果（称为自发运算）： s(1)(1)( (x) )xs( (x) ) mod g( (x) ) (9 (911)11) 【例【例9.3】以】以g( (x) )x4x3x21为生成多项式的（为生成多项式的（7，3）循环码）循环码（示于表（示于表9.1），能纠正一个错误。），能纠正一个错误。 设传送出现一个错，错误图样设传送出现一个错，错误图样e（0 0 0 1 0 0 0），），即即e( (x) )x3，其伴随式其伴随式 s( (x) )e( (x) ) mod g( (x) ) x3 mod (x4x3x21)x3， 即即s （1 0

21、0 0）现设错误图样现设错误图样 e1（0 0 1 0 0 0 0）, ,即即e(1)(1)( (x) )xe( (x) )x4，相应的伴随式相应的伴随式 s(1)(1)( (x) )x4 mod (x4x3x21)x3x21, ,即即 s1（1 1 0 1）s1是是s在图在图9.59.5所示的所示的g( (x) )x4x3x21除法电路中无输入除法电路中无输入时，右移一位的结果，也即自发运算的结果。时，右移一位的结果，也即自发运算的结果。图图9.5 9.5 （7，3）循环码的伴随式计算电路）循环码的伴随式计算电路 9.3.2 循环码的译码循环码的译码 把某一可纠正的错误图样把某一可纠正的错误

22、图样e( (x) )及其所有的小于等于及其所有的小于等于n1次的循环移位归成一类，用一个错误图样来代表。译码时次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在伴随式都可由该伴随式在g( (x) )除法电路中循环移位来得到。除法电路中循环移位来得到。 若（若（7，3）循环码译码器按错误图样（循环码译码器按错误图样（1 0 0 0 0 0 0）设计，于是设计，于是 s( (x) )e( (x) ) mod g( (x) ) x6 mod (x4x3x21)x3x2x， 即即 s（1 1 1 0）其译码器电路示于图其译码器电路示于图9.6。图图9.6 9.6 （7，3）循环码译码器）循环码译码器 9.3.3 Meggit译码器译码器 循环码译码器的缺点无法对接收到的码字实现连续的译循环码译码器的缺点无法对接收到的码字实现连续的译码输出。改进的译码器称作码输出。改进的译码器称作Meggit通用译码器通用译码器，其结构如图，其结构如图9.7，可实现连续的译码输出。，可实现连续的