1、信息论与编码-循环码上次课小结：o线性分组码的一些概念：域、矢量空间、线性 分组码；o生成矩阵和校验矩阵o伴随式与译码：伴随式的定义、标准阵列译码 表。信息论与编码-循环码循环码是线性分组码中最重要的一类码。循环码的特点是：码集C中任意一个码字经循环移位后仍然是码字。由于构成码集C的k维n重矢量空间的基底也一定是码字，因此，k个基底可以是同一个基底经循环移位得到。所以，只用一个基底就可以表示一个码的特征，也就不需要用矩阵来描述。信息论与编码-循环码描述循环码的重要的数学工具是多项式。设一个码字为 ，可以用一个称为码多项式的多项式来表示，多项式的系数就是码字的各个码元的值，指数项表示码元在码字中
2、所处的位置，即对于二进制码，。,021cccCnn012211)(cxcxcxcxCnnnn1,0ic信息论与编码-循环码当C所对应的码字循环移位1位后，得到对应的多项式为所以，可以用多项式乘以x来表示一次循环移位，因此有：0122110)(cxcxcxcxCnnnn1023121)(nnnnncxcxcxcxC)()(01xxCxC)1mod(nx021,cccnn循环移1位1032,nnncccc信息论与编码-循环码以此类推。)1mod()1mod()1mod()()()()()()()()(1-n210121021201nnnnnnxxxxCxxxCxCxCxxxCxCxxCxC位：移位
3、：移位：移因为一个码字经过n次循环移位后又变回自身，所以一个码字经循环移位最多产生n个码字。而对于码长为n的码字，共有 个不同的码字，因此，不可能由一个码字经循环移位得到所有可能的码字。但是，可以由一个基底矢量经循环移位得到所有k个基底矢量，所有的码字都可以由这k个基底的线性组合构成。k2信息论与编码-循环码信息论与编码-循环码因此，设 对应一个码字，则其线性组合：其中，A(x)是任意多项式，是一个码多项式。也就是说，任意一个码多项式与一个多项式之积，仍然是一个码多项式。上述运算是在模运算的前提下，即)(0 xC)()()()()()()()()(00112210011j0220100 xCx
4、AxCxaxaxaaxCxaxCxaxxCaxCaxCjjj)(0 xC)1mod(nx信息论与编码-循环码从多项式的性质出发，根据近世代数理论，可以得到以下结论：(1)一个(n,k)循环码的码多项式是模(xn+1)乘运算下多项式交换环的一个主理想子环，反之，多项式交换环的一个主理想子环一定可以产生一个循环码。而主理想子环中的所有码多项式都可以由其中一个元素(码多项式)的倍式组成，这个元素称为该主理想子环的生成元，或称它为对应循环码的生成多项式。生成多项式不是唯一的，但总有一个是最低的。信息论与编码-循环码（2）GF(2)上的（n，k）循环码中，存在着唯一的一个次数最低（n-k次）的首一（即第
5、一项的系数为1）码多项式g(x)：使得所有的码多项式都是g(x)的倍式，即且所有小于n次的g(x)的倍式都是码多项式。g(x)称为生成多项式。1)(12211xgxgxgxxgknknkn)()()(xgxmxC信息论与编码-循环码（3）（n，k）循环码的生成多项式g(x)一定是 的因子，写为 ，或 。反之，如果g(x)是 的（n-k）次因子，则g(x)一定是（n，k）循环码的生成多项式。1nx1|)(nxxg)()(1xhxgxn1nx信息论与编码-循环码（n，k）循环码的构造方法为：（1）对 做因式分解，找出其（n-k）次因子；（2）以该（n-k）次因子为生成多项式g(x)，与信息多项式m
6、(x)相乘，得到的多项式C(x)=m(x)g(x)即为码多项式。1nx信息论与编码-循环码例题：研究一个长度为7的循环码的构成方法。解：根据上面的循环码编码方法，首先对 做因式分解，得到17x)1)(1)(1(13237xxxxxx信息论与编码-循环码所以，的因子共有以下几种：次数为1（1个）；，：次数为3（2个）；，：次数为4（2个）；：次数为6（1个）；如果给定了n和k，那么只能选用满足要求的（n-k）次多项式作为生成多项式，本题中没有要求k，可以选用不同的多项式做生成多项式，当然会得到不同的码集。17x)1(x)1(23 xx)1(3 xx)1)(1(23xxx)1)(1(3xxx)1)
7、(1(233xxxx信息论与编码-循环码设选取 为生成多项式，则n-k=3，k=4，所以信息多项式为信息码组共有16种不同的组合，因此，共有16个码字。例如则循环编码后的码多项式为对应的码字为（0101110）。)1()(23xxxg1)(32231xmxmxmxm)0110()(0123mmmmmxxxxxxxxxC235232)1)()(信息论与编码-循环码o相同地，可以得到不同信息组的时候的码字。可以看出，码集中有四组码字循环信息比特码字（循环1）信息比特 码字（循环2）信息比特 码字 （循环3和4）00010010010010001101011111100001101001101001
8、101001101000101000101000111000110001101101100010110101001111100101110101110101110001110011110010110010110010110000101100000001111111信息论与编码-循环码一致校验多项式如果 分解为 ，选g(x)为生成多项式，则h(x)称为码的一致校验多项式，阶次为k，和校验矩阵类似，校验多项式满足：当然，也可以选择h(x)为码生成多项式，则g(x)就是一致校验多项式。因此，由g(x)生成的（n，k）码和由h(x)生成的（n，k）码互为对偶码。1nx)()(1xhxgxn)1mod(
9、0)1)()()()()()(nnxxxmxhxgxmxhxC信息论与编码-循环码循环码是线性分组码的一种。对于线性分组码，可以用生成矩阵来描述。具体到循环码，则简化为生成多项式。因此也一定可以用生成矩阵来描述循环码。所谓生成矩阵，就是码空间的一组基底。而生成多项式及其移位后的一组多项式，就可以作为一组基底，因此，如果循环码的生成多项式为1)(111xgxgxxgknknkn信息论与编码-循环码则生成矩阵为这种形式的生成矩阵不是系统形式的。如果要生成系统形式的生成矩阵，则第l行应是多项式1000000100101100010010001)()()()(12112121121121ggggggg
10、gggggGxgxxgxgxxgxknknknknkk信息论与编码-循环码这里，是 除以g(x)的余式，因为所以由于g(x)是码字，所以 也是码字，因此 也一定是码字，可以作为基底。klxRxlln,2,1),()(xRllnx)()()(xRxgxQxllln)()()(xgxQxRxllln)()(xgxQl)(xRxlln信息论与编码-循环码实际上，可以由生成多项式直接得到系统码。因为系统码中，信息位占据了码字的前k个位置，而信息多项式为如果用 乘以m(x)，得到如果在其后加上n-k比特的校验位，就构成了码字.012211)(mxmxmxmxmkkkkknxknknnknkknxmxmx
11、mxmxmx0112211)(信息论与编码-循环码也就是说，要在上面的多项式后面加上次数底于n-k的多项式。这个多项式应该是用g(x)除 ，得到的余式r(x)（商为Q(x)），即也就是说，得到的码多项式为由于g(x)是码多项式，因此Q(x)g(x)也是码字，这样由信息多项式得到的码字一定是系统码。)(xmxkn)()()()(xrxgxQxmxkn)()()()(xgxQxrxmxkn信息论与编码-循环码归纳起来，我们可以得到由信息组得到对应系统码字的方法是：（1）由信息组得到信息多项式，将信息多项式 乘以 ；（2）用g(x)除 ，得到余式r(x)；（3）将r(x)加在 后面，得到码多项式，从
12、而得到其对应的码字（码多项式的系数）。)(xmknx)(xmxkn)(xmxkn信息论与编码-循环码例题：（7，4）循环码的生成多项式为求（1）该循环码系统形式的生成矩阵；（2）对于给定的信息组（1001），求其对应的系统形式的码字。1)(3xxxg信息论与编码-循环码解：（1）生成矩阵 将生成多项式及其对应的循环移位多项式作为基底，得到一般形式的生成矩阵为1101000011010000110100001101G信息论与编码-循环码o系统形式的生成矩阵：一种办法是将一般形式的生成矩阵通过行变换和列置换，得到系统形式；通过矩阵运算:将矩阵第3,4行加到第1行:将矩阵第4行加到第2行110100
13、0011010011100101010001G信息论与编码-循环码另一种方法：第一行，前四列为1000，对应的多项式为 ，除以生成多项式 ，得余式为 ，所以对应的后三列为101；同样的办法，可以得到第二行为0100111；第三行为0010110；第四行为0001011；因此，得到系统形式的生成矩阵。6x1)(3xxxg1)(2 xxr信息论与编码-循环码（2）对应信息组（1001）的码字，可以由生成矩阵得到，也可以直接得到，即用信息组多项式 乘以得到 ，除以码多项式 ，得余式为 ，因此，码多项式为对应的码字为：10011101)(3012233xmxmxmxmxm3xxkn36)(xxxmxk
14、n1)(3xxxgxxxr2)(xxxxxrxmxxCkn236)()()(信息论与编码-循环码DDD1xX32循环码编码电路实现的硬件结构图 用除法器实现(7,4)循环码编码器11k2k1(m0,m1,m2,m3)信息论与编码-循环码o带反馈移存器构成除以g(x)=x3+x+1的除法电路，反馈线的位置与g(x)的项对应，左到右分别对应1，x,x2 和x3。正常做除法时，m(x)应从除法器最左端(对应g(x)常数项1)进入。如m(x)右移一位，则应从g(x)一次项x的位置进入，相当于作xm(x)运算再去做除法。信息论与编码-循环码om(x)从xn-k=x3 的位置进入，相当于作xn-k m(x
15、)运算再去除以g(x)。每编一个码需化n=7拍时间。前4拍时开关k1，k2 在位置1，消息位先m3 再m2,m1,m0 依次输入除法器做xn-k m(x)/g(x)运算，同时依次该4个码元输出。信息论与编码-循环码 到第4拍完成时，除法器移存里的数据就是余式系数。后3拍消息停止输入(空3拍)，k1，k2 倒向位置2，移存器断开反馈后不再起除法器而仅起一般移存器作用，其中的数据分3拍依次移出，作为第5到第7循环码校验位的输出。信息论与编码-循环码信息论与编码-循环码乘法电路已知两多项式相乘为 C(x)=A(x)B(x)=akbrxk+r+(akb r-1+ak-1br)xk+r-1 +(akb
16、r-2+ak-1b r-1+ak-2br)xk+r-2+(akb r-i+ak-1b r-(i-1)+ak-ibr)xk+r-i+(a1b0+a0b1)x+a0b0 可用下图所示的电路完成上述运算过程。该电路由r个存贮单元组成的r 级移位寄存器，至多r个模q相加器和至多(r+1)个模q常乘器所组成。信息论与编码-循环码乘B(x)运算电路 信息论与编码-循环码o工作开始时，r级移位存贮器中的存数全清洗为 0，且规定被乘多项式A(x)的高次项系数ak首先送入电路，电路的工作过程如下：(1)当A(x)的最高次系数ak首先送入时，乘积C(x)的最高次项xk+r的系数akbr就出现在输出端，同时ak存入
17、移存器的第一级(最左一级)。信息论与编码-循环码 (2)A(x)的第二个系数ak-1送入电路时,ak由第一级输出送入第二级,同时与b r-1相乘和ak-1 br相加后送到输出端,这就是C(x)的x k+r-1项系数akb r-1+ak-1 br。此时，移存器内的存贮数据为ak-1，ak，0，0，0(自左至右)。信息论与编码-循环码(3)上述过程重复进行，直至k次移位后，A(x)的系数全部送入移存器。k+r+1次移位后，移存器输出C(x)的常数项a0+b0，移存器中的内容全部恢复到全为 0 初态，乘法 完成。由上面乘法过程可以看出,这种乘法电路完成一次乘法运算,共需移位k+r+1次。信息论与编码
18、-循环码图 5-4 另一种乘B(x)电路 多项式除法电路 GF(q)上的两多项式 A(x)=akxk+ak-1xk-1+a1x+a0 B(x)=brxr+br-1x r-1+b1x+b0 由欧几里德除法可知：A(x)=q(x)B(x)+r(x)0r(x)B(x)或 r(x)=0假设kr，否则q(x)=0，r(x)=A(x)。多项式A(x)被B(x)除的电路如下图所示，它由r级移存器、至多r个GF(q)加法器和至多r+1个常乘器组成。kr信息论与编码-循环码 除B(x)=brxr+b1x+b0电路 信息论与编码-循环码 为了理解除法电路的工作过程，下面我们列出B(x)除A(x)的竖式运算式子：b
19、rxr+b r-1 x r-1+b1x+b0(除式)b-1rakxk-r+b-1r(ak-1-b-1rbr-1ak)xk-r-1+(商式)akxk+ak-1xk-1+a1x+a0(被除式)-(akxk+b-1rbr-1akxk-1+b0b-1rakxk-r)(ak-1-b-1rbr-1ak)xk-1+(ak-r-b0b-1rak)xk-r+(A)-(ak-1-b-1rbr-1ak)xk-1+)(余式)由上面式子，我们讨论除法电路的工作过程。信息论与编码-循环码 (1)开始运算时r级移存器中的存数全部清为0。第一个移位节拍后，被除多项式 A(x)的最高次项xk的系数ak首先进入电路的最左一级。r
20、次移位后ak进入到移存器的最右一级中，此时自左至右移存器中的内容为ak-r+1，ak-r+2，ak-1，ak。信息论与编码-循环码 (2)第r+1次移位后，ak输出与b-1r 相乘得到ak b-1r，这就是商式q(x)的第一项xk-r的系数。akb-1r同时反馈到后面各级寄存器中(所以称这种除法电路为线性反馈移存器)减去akb-1rB(x)，所以，此时移存器中自左至右的内容为(ak-r-b0b-1rak),(ak-r+1-b1b-1rak)，(ak-1-br-1 b-1rak)，这相应于竖式运算中的第A项所示的结果。信息论与编码-循环码o(3)依次类推，经k+1 次移位后，完成了整个除法运算过
21、程。它的输出为商式q(x)，而移存器中的内容就是余式r(x)的系数信息论与编码-循环码o例 设除式B(x)=x3+x+1，被除式A(x)=x4+x3+1都是GF(2)上的多项式，求B(x)除A(x)的电路。除B(x)的除法电路如下图 所示，它由 3 级移存器和 2 个模 2 相加器组成。因为在GF(2)中，1 的逆元仍为 1，相加和相减相同，所以b-1r与-bi常乘器均为一条闭合线。信息论与编码-循环码图 5-7 除B(x)=x3+x+1电路 信息论与编码-循环码o完成上述两个多项式相除的长除法运算式如下：x+1 (商式)x3+x+1 x4+x3 +1 (被除式)(除式)x4 +x2+x x3
22、+x2+x+1 x3 +x+1 x2 (余式)信息论与编码-循环码 这里 x4+x3+1=(x+1)(x3+x+1)+x2 商为x+1，余式为x2。下表 5-4 中列出了电路的工作过程。显然，r+1=4 次移位后得到商的第一个系数，k+1=5 次移位后，就完成了整个除法运算，并在D0、D1、D2组成的移存器中保留了余式001，即x2。信息论与编码-循环码B(x)除x4+x3+1 的运算过程表信息论与编码-循环码 多项式相乘相除电路 GF(q)上的多项式A(x)、H(x)、G(x)分别为：A(x)=akxk+ak-1xk-1+a1x+a0 H(x)=hrxr+h r-1 x r-1+h1x+h0
23、 G(x)=grxr+g r-1 x r-1+g1x+g0 若A(x)与H(x)相乘后再用G(x)除，则 A(x)H(x)=q(x)G(x)+r(x)0r(x)G(x)，或 r(x)=0 信息论与编码-循环码 该运算可用图 所示的电路实现，它由r级移存器、至多有2(r+1)个GF(q)的常乘器和r+1个GF(q)的相加器组成。显然，该电路就是乘法电路与除法电路的两种电路的结合。如果H(x)与G(x)次数不等，则只要按G(x)与H(x)中最高次数设计移存器级数 即可。信息论与编码-循环码图 5-8 乘H(x)除G(x)电路 信息论与编码-循环码例 设GF(2)上的 3 个多项式为：A(x)=x4
24、+x+1，H(x)=x2+1，G(x)=x3+x+1 则 A(x)H(x)=(x4+x+1)(x2+1)=x6+x4+x3+x2+x+1 =x3(x3+x+1)+(x2+x+1)=q(x)G(x)+r(x)可用下图的电路实现，该电路的工作过程如下表所示，移位A(x)+1=5 次后，即得到了商式x3 和余式x2+x+1。信息论与编码-循环码 图 5-9 乘(x2+1)除(x3+x+1)电路 信息论与编码-循环码 若GF(2)上的多项式 A(x)=x4+x+1，H(x)=x3+x+1，G(x)=x2+1 则 A(x)H(x)=(x4+x+1)(x3+x+1)=x7+x5+x3+x2+1 =(x5+
25、x+1)(x2+1)+x=q(x)G(x)+r(x)该运算可用下图所示的电路实现，它的工作 过 程 如 下 表 所 示。显 然，移 位 A(x)+H(x)+1-G(x)=6 次后，电路即可完成运算，它的输出是商 q(x)=(x5+x+1)，在移存器中保留了余式x。信息论与编码-循环码图 5-10 乘(x3+x+1)除(x2+1)电路信息论与编码-循环码电路运算过程表 o循环码将生成矩阵简化为生成多项式，从而将与编码矩阵对应的硬件阵列（平面型）简化为带反馈的移存器（直线型）。o针对循环码的特点，在译码上也出了许多高效的算法，如捕错译码、大数逻辑译码等，限于篇幅，这里不再讨论译码的问题。信息论与编
26、码-循环码信息论与编码-循环码 一个码可以兼有很多的特点，循环特征仅是其中之一。前面讲过的汉明码也可以兼有循环特征，这类码叫循环汉明码，其分组长度是n=2m1,校验位nk=m，而任何码字的循环依然是码字。同样，兼有循环特征的高莱码叫作循环高莱码，比如用生成多项式g(x)=x11+x9+x7+x6+x5+x+1 产生的线性（23，12）高莱码就是循环高莱码。在无线信道上应用最广泛的BCH码、RS码也是循环码，它们在具有循环特性的基础上又兼有另一些特点。信息论与编码-BCH码和RS码BCH码oBCH（Bose：Chaudhuri-Hocquenghem）码是循环码中一大子类，它可以是二进制码，也可
27、以是非二进制码。二进制本原BCH码具有下列参数：式中m（m=3）和纠错能力t()是任意正整数。12mnmtkn12min td12m信息论与编码-BCH码和RS码oBCH码的基本特点是其生成多项式g(x)包含2t个连续幂次的根。由上面关于循环码的论述可知，若在二元域GF(2)上把 分解为l个最小多项式m(x)，i1,2,l 之积，其中l1个组成g(x)而剩余的组成h(x)，则包含于g(x)中的最小多项式一定满足式中“|”表示整除，C（x）表示码多项式。1nx)1(|)(|)(|)(nixxCxgxm信息论与编码-BCH码和RS码o由近世代数可进一步得知，在二元扩域GF(2m)上可把xn+1分解
28、为如下n个根的乘积式中，a是GF(2m)上本原元，n（2m1）。若对于每个j，j1，2，2t，均有即g(x)包含2t个连续幂次的根,则由该g(x)生成的循环码就是纠错能力不小于t的BCH码)()()()1(1210nnaxxxxx11)()(|)liijxmxgax（信息论与编码-BCH码和RS码 BCH的出现为通讯系统设计者们在纠错能力，码长和码率的灵活设计上提供了很大的选择余地，一旦要求的纠错能力t给定，只要算出2t个连续幂次的根所对应的多项式作为生成多项式，即可得出纠错能力符合要求的码。又因其构码方法带来的译码特点，使之可以用伯利坎普（Berlekamp）迭代译码等通用，高效的译码算法，
29、以致BCH码从70年代起已成为线性分组码的主流。信息论与编码-BCH码和RS码o已知码长n及纠错能力t，二元本原BCH码的具体设计步骤如下：1。由关系式n=2m-1算出m，查表找到m次本原多项式P(x)，用它产生一个GF(2m)扩域2。以本原多项式P(x)的根为本原元a，分别计算2t个连续幂次根a，a2，a2t所对应的二元域上的最小多项式m1(x),m2(x),m2t(x).3。计算这些最小多项式的最小公倍式，得到生成多项式为 g(x)=LCM(m1(x),m2(x),mt2(x)4.得到BCH码字 c(x)=m(x)g(x)信息论与编码-BCH码和RS码o例 设计一个n=7的二元本原BCH码
30、，求出不同纠错能力下的生成多项式。解：因7=23-1,因此m=3.1.查表找出一个三次本原多项式，本题为P(x)=x3+x+1然后令a为P(x)的根，生成扩域GF(23)的所有元素，见表6-7最大纠错能力为t=3。信息论与编码-BCH码和RS码2。每个根所对应的最小多项式，由表6-7给出3。对于给定的t，求连续幂次所对应的最小多项式的最小公倍式如t=1,连续幂次为a,a2,生成多项式为 g(x)=LCM(m1(x),m2(x)=x3+x+1生成一个(7,3)BCH码，即汉明码t=2,g(x)=x6+x5+x4+x3+x2+x+1生成一个(7,1)BCH码。t=3,g(x)=x6+x5+x4+x
31、3+x2+x+1纠错能力至少是t.元素 多项式 矢量表示 极小多项式 0 0 000 x a0 1 001 x+1 a1 a 010 x3+x+1 a2 a2 100 x3+x+1 a3 a+1 011 x3+x2+1 a4 a2+a 110 x3+x+1 a5 a2+a+1 111 x3+x2+1 a6 a2+1 101 x3+x2+1 x3+x+1生成的GF（23）扩域信息论与编码-BCH码和RS码oRS译码译码RS译码（ReedSolomon里德-索罗门码）属于BCH码的一个子类，是一种q进制（q2）的BCH码，其码的每个码元取值于符号集0,a0,a1,aq-2 实用时通常选取q为2的幂
32、次（q2m），以便一组m个信息比特可以一一映射到q个符号之一，也便于与4，8，16，32，信号点集的PSK或QAM调制相适应。若m8即256进制，可以将整个8比特字节变为RS码的一个码元。信息论与编码-BCH码和RS码o如果用N表示RS码的码长，K表示信息符号的长度，NK表示校验符号码的长度，则RS码的参数可以用以下式子来表达 码长n=q-1 校验位n-k=2t 最小距离dmin=n-k+1(MDC码)生成多项式g(x)=(x-a)(x-a2)(x-a2t)=an-kxn-k+an-k-1xn-k-1+a1x+a0信息论与编码-BCH码和RS码oRS码的重量分布是已知的。码重多项式第i次项的系
33、数（重量为i的码字个数）是 oRS码之所以重要，原因之一是该码的距离特性好，是（MDC）码。第二是因为存在一种有效的硬判决法，使得在许多需要长码得应用场合，该码能够被实现。第三是q进制RS码得二进衍生码具有良好的抗突发差错能力。qADjiDqinjiijjiminmin1)1(0)1(信息论与编码-BCH码和RS码o二进制衍生码 对于一个q=2m进制（n，k）RS码，如果不用q进制调制发送，而是将每码元对应为m比特后以二进制发送,实际上就是把q进制RS码化作了（mn，mk）二进制衍生码，这样的二进制衍生码特别适用于纠突发差错，下面举例说明。信息论与编码-BCH码和RS码o例，一个8进制（7，3
34、）RS码的a幂次，多项式及三比特组这三种形式的符号集如表6-7，写出相应的RS码的生成多项式。如输入的8进制信息元为a5a3a1，问编出的8进制RS码字是什么，纠错能力如何？解：n=7,k=3,dmin=n-k+1=5,纠错能力t=2，生成多项式为 g(x)=(x-a)(x-a2)(x-a3)(x-a4)=x4+a3x3+x2+ax+a3信息论与编码-BCH码和RS码信息多项式为m(x)=a5x2+a3x+a，对应码字为c(x)=m(x)g(x)系统码字为c(x)=xn-km(x)+r(x)=a5x6+a3x5+ax4+a6x3+a4x2+a2x+1 r(x)=xn-km(x)mod g(x)
35、二进制衍生码：信息码元：a5a3a1(111,011,010)码字：a5a3aa6a4a21 (111,011,010,101,110,100,001)信息论与编码-BCH码和RS码o衍生码就突发错误的能力：o八进制RS码能纠每码字两个字符的差错。对于其二进制衍生码，若以二进制信号在信道上传送，突发差错长度比特时最多影响到两个八进制符号时，可纠正；若突发差错长度等于5时，可能只影响两个八进制符号，也可能跨三各八进制符号，就不一定能纠正了。o一般的结论：若q进制（q=2m）RS码的纠错能力是t个q进制符号，那么它的二进衍生码能纠正的二进制突发差错长度b为1)1(mtb信息论与编码-码的扩展和缩短
36、o码的扩展和缩短：可以通过增加或删除信息位或校验位的方法改变码率，改变纠检错能力，以满足不同的需要。常用的方法有：增信，删余，增余，删信，及组合信息论与编码-码的扩展和缩短o扩展码 设C是一个最小距离为d的二进制n,k,d线性分组码，它的码字有奇数重量也有偶数重量。若对每一个码字(cn-1,cn-2,c1.c0)增加一个校验元c0，满足以下校验关系：cn-1+cn-2+c1+c0+c0=0 称c0为全校验位。若原码的校验矩阵为H，则扩展码 的校验矩阵为C1.1100HH2m-1，2m-1-m，3汉明码的扩张码是2m，2m-1-m，4码，它的 中的H是汉明码的校验 矩阵。最小码距由3增加为4H信
37、息论与编码-码的扩展和缩短信息论与编码-码的扩展和缩短码的缩短：缩短循环码就是在(n，k)循环码的 个码字中挑选出前i位均为0的所有码字，组成一个新的(n-i,k-i)缩短循环码码集。该码集是原循环码码集的一个子集，子集里所有码多项式的阶数均小于n-i且能够被生成多项式g(x)整除。反之，次数小于n-i的所有g(x)倍式一定包含于该子集中，是(n-i,k-i),缩短循环码的一个码多项式。一般来讲，每缩短一位，码字数目减少一半。k2信息论与编码-码的扩展和缩短knx特点：1.码的重量没有变，2.校验位的数量也没有变（n-i-(k-i)=n-k）,3.因此(n-i,k-i)缩短循环码的纠错能力于原
38、来的（n,k）循环码码完全一样，4.3.码率R下降了，由k/n变为(k-i)/(n-i).5.4.循环码的外部特征在缩短循环码中已不复存在，缩短码码字的循环未必仍是码字；5.循环码的内部特征仍然存在，即所有的码多项式一定能够被g(x)整除。信息论与编码-码的扩展和缩短o这样，缩短循环码的编、译码可以借用循环码的方法，将消息多项式m(x)乘以 后 除以g(x)即可，所不同的是这里的消息多项式m(x)由(k-i)项组成而不是k项组成。o缩短循环码用于检错时也和循环码一样，只要将接收序列除以g(x)后检查其余式即可，余式全0(除尽)则表示接收的时码字(g(x)的倍式)，否则就不是码字。knx信息论与
39、编码-码的扩展和缩短CRC：缩短循环码的最大应用在于帧校验，这就是在数据通信中大家所熟悉的循环冗余校验码(CRC：Cyclic Redundancy Check)。在数据通信中，信息都是先划分成小块再组装成帧后(或叫分组、包、信元，仅名称不同而已)在线路上统计复用传送或存入共同物理介质的，帧尾一般都留有8，12，16或32位用作差错校验。如把一帧视为一个码字，则其校验位长度nk不变而信息位k和码长n是可变的，正符合(ni，ki)缩短循环码的特点。只要以一个选定的(n，k)循环码位基础，改变i值，就能适用于任何信息长度的编码。信息论与编码-码的扩展和缩短例546 用于HDLC，X.25，ISDN
40、和7号信令的CRCITUT循环冗余校验码的生成多项式为 1)(51216xxxxgCRC nk16位 r(x)信息ki位 015次 16n-i-1次低次 高次(先发)带CRC的帧结构信息论与编码-码的扩展和缩短根据循环码定义，g（x）必定是 的因式，而g（x）是本原多项式，它所能整除的 中n的最小值是216-1，所以，g(x)生成的循环码是一个（65535，65519）循环码将该码所有前i位为零的码字去除前i位后集合在一起就构成（ni，ki）缩短循环码，表现为ki信息位加上16位CRC组成长度（ni）的一个帧。由于i可变，因此帧长可变。151216xxx1nx1nx信息论与编码-码的扩展和缩短
41、g（x）本身也是码字，而且是最轻的码字，所以本码的 能纠一个错误（t1）或检3个差错。另外，由此g(x)生成的码字的重量一定是偶数，所以它就能检出所有奇数个差错。4mind信息论与编码-码的扩展和缩短将该码所有前i位为零的码字去除前i位后集合在一起就构成（ni，ki）缩短循环码，表现为ki信息位加上16位CRC组成长度（ni）的一个帧。由于i可变，因此帧长可变。实施CRC编码时，信息在输出的同时由位置输入移存器，相当于信息移16位后即)(16xmx再除以g（x）。输完ki信息位后断开移存器的反馈线，将此时移存器内的数据（余式，即CRC校验码）移位输出即可。信息论与编码-码的扩展和缩短接收端校验时，只要将整个帧除以g（x）检查余式是否为零即可。如为零，说明传输无误；如余式非零，说明该帧有差错，须反馈重发和丢弃。除法器的结构与图544（b）所示相同，只是接收序列由最左端而不是从 处输入而已。16x信息论与编码-码的扩展和缩短5x 12x 16x 10D接收端校验时，只要将整个帧除以g（x）检查余式是否为零即可。如为零，说明传输无误；如余式非零，说明该帧有差错，须反馈重发和丢弃。o作业o6-11，6-12，6-13
