第九章-循环码

1第九章循环码2第九章循环码内容提要：循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码、BCH码等。3本章重点：1.循环码的基本概念；2.循环码的编码和译码方法；3.BCH码。49.1.1循环码的定义将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图9.1）9.1循环码的一般概念5图9.1（7，4）汉明码的码字循环图1001110:0100111:1010011:1101001:1110100:0111010:0011101:141312111098ccccccc第二循环1000101:1100010:0110001:1011000:0101100:0010110:0001011:7654321ccccccc0000000:15c第一循环1111111:16c6定义9.1一个线性分组码，若具有下列特性，则称其为循环码。设码字c＝（cn-1，cn-2，…，c1，c0）若将码元循环左移一位，得c(1)＝（cn-2，…，c1，c0，cn-1）c(1)也是一个码字。79.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）循环码的码字多项式。8比较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运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。99.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)为该码的生成元或生成多项式。10定理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1010100000000H11①（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及G·HT＝0循环码是线性分组码的一个子类。因此，所有线性分组码的性质均适用于循环码。129.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＋r013c(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)。149.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除法电路的一般形式15【例9.2】设被除式a(x)＝x4＋x＋1，除式b(x)＝x3＋x2＋1，完成二个多项式相除的运算。11111223334423xxxxxxxxxxxx11001101110011011110011011长除法：多项式的系数运算16实现以上除法运算的除法电路如图9.3所示图9.3以b(x)＝x3＋x2＋1为除式的除法电路179.2.3编码电路然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而可得码字多项式c(x)＝xn-km(x)＋r(x)。系统循环码的编码方法是：首先将信息元多项式m(x)乘以xn-k成为xn-km(x)；18用电路实现编码时可采用以g(x)为除式的除法电路。作为实例，图9.4示出了生成多项式g(x)＝x3＋x2＋1的（7，4）循环码的编码电路。图9.4以g(x)＝x3＋x2＋1的（7，4）循环码编码器199.3循环码的译码当码字c通过噪声信道传送时，会受到干扰而产生错误。如信道产生的错误图样是e，译码器收到的n重接收矢量是y，则表示为y＝c＋e上式也可写成多项式形式：y(x)＝c(x)＋e(x)(9－7)译码器的任务就是如何从y(x)中找到错误图样多项式，然后得到估计码字多项式，进而得到信息组。xeˆxexyxcˆˆxmˆ20循环码的译码可按以下三个步骤进行：（２）根据伴随式s(x)找出对应的估值错误图样；)(ˆxe（３）计算，得到估值码字。若，则译码正确，否则，若，则译码错误。)(ˆ)()(ˆxexyxc)(ˆxc)()(ˆxcxc)()(ˆxcxc（１）由接收到的y(x)计算伴随式多项式s(x)；219.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）循环码的伴随式计算电路239.3.2循环码的译码把某一可纠正的错误图样e(x)及其所有的小于等于n－1次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到。以（7，3）循环码为例：当码字传送出现一个错误时，若用一般译码器需要识别如（0000001），（0000010），（0000100），（0001000），（0010000），（0100000），（1000000）等7个不同的错误图样，但对于按上述定理设计的循环码译码器来说，可以把这些错误图样归成一类，译码器只要识别其中的一个错误图样就可以了。24若（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）循环码译码器259.3.3Meggit译码器循环码译码器的缺点无法对接收到的码字实现连续的译码输出。改进的译码器称作Meggit通用译码器，其结构如图9.7，可实现连续的译码输出。图9.7Meggit通用译码器269.4.1循环汉明码定义9.3设是GF(2m)上的一个本原元，则以的本原多项式为生成多项式的（2m－1，2m－1－m）汉明码是循环汉明码。码的校验矩阵为(9－13）121nnH因码长n＝2m－1，H也可以表为(9－14)13222mmH9.4一些重要的循环码27例如，以GF(23)上的三次本原多项式为生成多项式，可生成一个（7，4）循环汉明码，其生成多项式g(x)＝x3＋x＋1。1001011010111000101110123456H设是GF(23)上的本原元，则码的校验矩阵289.4.2BCH码定义9.4设是GF(2m)上的一个本原元，t为整数，则以含有、2、……2t等共2t个根，其系数在GF(2)上的最低次多项式g(x)为生成多项式的循环码，叫做二元本原BCH码。码长n＝2m－1校验位数r＝n－kmt最小距离d2t＋1纠错能力为t二元本原BCH码的参数为：29(9－17)1)()(1)()(1122121123231321tntntnnnnH【例9.4】设m＝4，是GF(24)上的本原元，求码长n＝24－1＝15的二元本原BCH码。若t＝1，则码以为根，即以，2，4，8共轭根系为根，最小多项式m1(x)＝x4＋x＋1生成多项式g(x)＝m1(x)＝x4＋x＋1校验位数目n－k＝4码的校验矩阵为30