第九章循环码

第九章循环码第九章循环码内容提要循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码等。9.1.1循环码的定义将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图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（7，4）汉明码的码字循环图1000101:1100010:0110001:1011000:0101100:0010110:0001011:7654321ccccccc0000000:15c第一循环1001110:0100111:1010011:1101001:1110100:0111010:0011101:141312111098ccccccc第二循环1111111:16c9.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）循环码的码字多项式。比较c(x)和c(1)(x)后可得c(1)(x)＝xc(x),modxn－1(9－2)以及c(i)(x)＝xic(x)（i＝1,2,…,n－1）,modxn－1(9－3)定理9.1在以多项式xn－1为模的剩余类全体所构成的n维线性空间Vn中，其一个子空间Vn,k是一个循环子空间（循环码）的充要条件是：Vn,k是一个理想。一个（n，k）循环码的码字多项式都是模xn－1运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。9.1.3循环码的生成多项式定理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.2若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式g(x)的倍式，则称g(x)生成该码，并称g(x)为该码的生成元或生成多项式。循环码的生成矩阵常用多项式的形式来表示1)(111xgxgxxgrrr)()()()()(21xgxxgxgxxgxxGkk其中即例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别为定理9.4若g(x)是（n，k）循环码的生成多项式，由xn－1＝g(x)h(x)，h(x)是k次多项式，称为校验多项式。令h(x)＝hkxk＋hk-1xk-1＋…＋h1x＋h0则(9－5)为（n－k）n阶矩阵，称为码的校验矩阵。kkkhhhhhhhhh1010100000000H监督矩阵h(x)是常数项为1的k次多项式，称为监督多项式。同理，可得监督矩阵H)(*)(*)(*)(1xhxxhxhxxHkn①（n，k）循环码的生成多项式g(x)是一个次数最低的唯一的首一多项式，其次数r＝n－k正好是码字中校验元的数目；②生成多项式g(x)是xn－1的因式。要构造一个（n，k）循环码，就是要在xn－1的因式中找一个n－k次的首一多项式g(x)，它的一切倍式就构成一个（n，k）循环码。反之，循环码的每一个码字多项式必是g(x)的倍式；综上所述，有如下结论：③由xn－1＝g(x)h(x)，h(x)称为校验多项式。对于任意一个（n，k）循环码，必有g(x)h(x)＝0modxn－1及G·HT＝0循环码是线性分组码的一个子类。因此，所有线性分组码的性质均适用于循环码。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＋r0c(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)(9－6)即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)。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除法电路的一般形式【例9.2】设被除式a(x)＝x4＋x＋1，除式b(x)＝x3＋x2＋1，完成二个多项式相除的运算。11111223334423xxxxxxxxxxxx11001101110011011110011011长除法：多项式的系数运算实现以上除法运算的除法电路如图9.3所示图9.3以b(x)＝x3＋x2＋1为除式的除法电路9.2.3编码电路然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而可得码字多项式c(x)＝xn-km(x)＋r(x)。系统循环码的编码方法是：首先将信息元多项式m(x)乘以xn-k成为xn-km(x)；用电路实现编码时可采用以g(x)为除式的除法电路。作为实例，图9.4示出了生成多项式g(x)＝x3＋x2＋1的（7，4）循环码的编码电路。图9.4以g(x)＝x3＋x2＋1的（7，4）循环码编码器码长n=7的循环码：6）5）4）（7,3）循环码，生产多项式为g(x)＝（x3＋x2＋1)(x+1)码多项式为)1)(()(2342210xxxxaxaaxc9.3循环码的译码当码字c通过噪声信道传送时，会受到干扰而产生错误。如信道产生的错误图样是e，译码器收到的n重接收矢量是y，则表示为y＝c＋e上式也可写成多项式形式：y(x)＝c(x)＋e(x)(9－7)循环码的译码可按以下三个步骤进行：（２）根据伴随式s(x)找出对应的估值错误图样；)(ˆxe（３）计算，得到估值码字。若，则译码正确，否则，若，则译码错误。)(ˆ)()(ˆxexyxc)(ˆxc)()(ˆxcxc)()(ˆxcxc（１）由接收到的y(x)计算伴随式多项式s(x)；9.3.1伴随式计算对于（n，k）循环码，可以定义码的生成多项式g(x)除以接收码字多项式y(x)的余式为伴随式多项式s(x)，写s(x)＝y(x)modg(x)(9－8)由于y(x)＝c(x)＋e(x)而c(x)modg(x)＝0于是s(x)＝e(x)modg(x)(9－9)s(x)伴随式计算电路的一个重要性质：定理9.5设s(x)是接收码字多项式r(x)的伴随式。则y(x)的一次循环移位xy(x)（modxn－1）的伴随式s(1)(x)，是s(x)在伴随式计算电路中无输入时，右移一位的结果（称为自发运算）：s(1)(x)＝xs(x)modg(x)(9－11)【例9.3】以g(x)＝x4＋x3＋x2＋1为生成多项式的（7，3）循环码（示于表9.1），能纠正一个错误。设传送出现一个错，错误图样e＝（0001000），即e(x)＝x3，其伴随式s(x)＝e(x)modg(x)＝x3mod(x4＋x3＋x2＋1)＝x3，即s＝（1000）现设错误图样e1＝（0010000）,即e(1)(x)＝xe(x)＝x4，相应的伴随式s(1)(x)＝x4mod(x4＋x3＋x2＋1)＝x3＋x2＋1,即s1＝（1101）s1是s在图9.5所示的g(x)＝x4＋x3＋x2＋1除法电路中无输入时，右移一位的结果，也即自发运算的结果。图9.5（7，3）循环码的伴随式计算电路9.3.2循环码的译码把某一可纠正的错误图样e(x)及其所有的小于等于n－1次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到。若（7，3）循环码译码器按错误图样（1000000）设计，于是s(x)＝e(x)modg(x)＝x6mod(x4＋x3＋x2＋1)＝x3＋x2＋x，即s＝（1110）其译码器电路示于图9.6。图9.6（7，3）循环码译码器9.3.3Meggit译码器循环码译码器的缺点无法对接收到的码字实现连续的译码输出。改进的译码器称作Meggit通用译码器，其结构如图9.7，可实现连续的译码输出。图9.7Meggit通用译码器9.4.1循环Hamming码定义9.3设是GF(2m)上的一个本原元，则以的本原多项式为生成多项式的（2m－1，2m－1－m）Hamming码是循环码。码的校验矩阵为(9－13）121nnH因码长n＝2m－1，H也可以表为(9－14)13222mmH9.4一些重要的循环码例如，以GF(23)上的三次本原多项式为生成多项式，可生成一个（7，4）循环Hamming码，其生成多项式g(x)＝x3＋x＋1。1001011010111000101110123456H设是GF(23)上的本原元，则码的校验矩阵循环码是线性分组码中一个重要的子类，由于这种码的代数结构完全建立在有限域基础上，它是目前理论上最为成熟的一类码。本章的主要内容有：本章小结（2）循环码的性质：循环码的生成多项式，生成多项式的重要性质，由生成多项式构造生成矩阵。（1）循环码的定义及多项式描述：循环码的循环特性，循环码的码字多项式，循环码是多项式剩余类环的一个主理想子环。（5）循环Hamming码和BCH码：用g(x)的根定义循环码，建立在有限域扩域上的BCH码。（4）循环码的译码：伴随式的计算电路，自发运算电路，Meggit译码器。（3）循环码的编码：用生成多项式编码的理论，除法电路，循环码的编码电路。