信息论与编码-第六章.ppt

《信息论与编码-第六章.ppt》由会员分享，可在线阅读，更多相关《信息论与编码-第六章.ppt（88页珍藏版）》请在三一办公上搜索。

1、信息论与编码-循环码,上次课小结：线性分组码的一些概念：域、矢量空间、线性 分组码；生成矩阵和校验矩阵伴随式与译码：伴随式的定义、标准阵列译码 表。,信息论与编码-循环码,循环码是线性分组码中最重要的一类码。循环码的特点是：码集C中任意一个码字经循环移位后仍然是码字。由于构成码集C的k维n重矢量空间的基底也一定是码字，因此，k个基底可以是同一个基底经循环移位得到。所以，只用一个基底就可以表示一个码的特征，也就不需要用矩阵来描述。,信息论与编码-循环码,描述循环码的重要的数学工具是多项式。设一个码字为，可以用一个称为码多项式的多项式来表示，多项式的系数就是码字的各个码元的值，指数项表示码元在码字

2、中所处的位置，即对于二进制码，。,信息论与编码-循环码,当C所对应的码字循环移位1位后，得到对应的多项式为所以，可以用多项式乘以x来表示一次循环移位，因此有：,循环移1位,信息论与编码-循环码,以此类推。,因为一个码字经过n次循环移位后又变回自身，所以一个码字经循环移位最多产生n个码字。而对于码长为n的码字，共有 个不同的码字，因此，不可能由一个码字经循环移位得到所有可能的码字。但是，可以由一个基底矢量经循环移位得到所有k个基底矢量，所有的码字都可以由这k个基底的线性组合构成。,信息论与编码-循环码,信息论与编码-循环码,因此，设 对应一个码字，则其线性组合：其中，A(x)是任意多项式，是一个

3、码多项式。也就是说，任意一个码多项式与一个多项式之积，仍然是一个码多项式。上述运算是在模运算的前提下，即,信息论与编码-循环码,从多项式的性质出发，根据近世代数理论，可以得到以下结论：(1)一个(n,k)循环码的码多项式是模(xn+1)乘运算下多项式交换环的一个主理想子环，反之，多项式交换环的一个主理想子环一定可以产生一个循环码。而主理想子环中的所有码多项式都可以由其中一个元素(码多项式)的倍式组成，这个元素称为该主理想子环的生成元，或称它为对应循环码的生成多项式。生成多项式不是唯一的，但总有一个是最低的。,信息论与编码-循环码,（2）GF(2)上的（n，k）循环码中，存在着唯一的一个次数最低

4、（n-k次）的首一（即第一项的系数为1）码多项式g(x)：使得所有的码多项式都是g(x)的倍式，即且所有小于n次的g(x)的倍式都是码多项式。g(x)称为生成多项式。,信息论与编码-循环码,（3）（n，k）循环码的生成多项式g(x)一定是 的因子，写为，或。反之，如果g(x)是 的（n-k）次因子，则g(x)一定是（n，k）循环码的生成多项式。,信息论与编码-循环码,（n，k）循环码的构造方法为：（1）对 做因式分解，找出其（n-k）次因子；（2）以该（n-k）次因子为生成多项式g(x)，与信息多项式m(x)相乘，得到的多项式C(x)=m(x)g(x)即为码多项式。,信息论与编码-循环码,例题

5、：研究一个长度为7的循环码的构成方法。解：根据上面的循环码编码方法，首先对 做因式分解，得到,信息论与编码-循环码,所以，的因子共有以下几种：次数为1（1个）；，：次数为3（2个）；，：次数为4（2个）；：次数为6（1个）；如果给定了n和k，那么只能选用满足要求的（n-k）次多项式作为生成多项式，本题中没有要求k，可以选用不同的多项式做生成多项式，当然会得到不同的码集。,信息论与编码-循环码,设选取 为生成多项式，则n-k=3，k=4，所以信息多项式为信息码组共有16种不同的组合，因此，共有16个码字。例如则循环编码后的码多项式为对应的码字为（0101110）。,信息论与编码-循环码,相同地，

6、可以得到不同信息组的时候的码字。可以看出，码集中有四组码字循环,信息论与编码-循环码,一致校验多项式如果 分解为，选g(x)为生成多项式，则h(x)称为码的一致校验多项式，阶次为k，和校验矩阵类似，校验多项式满足：当然，也可以选择h(x)为码生成多项式，则g(x)就是一致校验多项式。因此，由g(x)生成的（n，k）码和由h(x)生成的（n，k）码互为对偶码。,信息论与编码-循环码,循环码是线性分组码的一种。对于线性分组码，可以用生成矩阵来描述。具体到循环码，则简化为生成多项式。因此也一定可以用生成矩阵来描述循环码。所谓生成矩阵，就是码空间的一组基底。而生成多项式及其移位后的一组多项式，就可以作

7、为一组基底，因此，如果循环码的生成多项式为,信息论与编码-循环码,则生成矩阵为这种形式的生成矩阵不是系统形式的。如果要生成系统形式的生成矩阵，则第l行应是多项式,信息论与编码-循环码,这里，是 除以g(x)的余式，因为所以由于g(x)是码字，所以 也是码字，因此 也一定是码字，可以作为基底。,信息论与编码-循环码,实际上，可以由生成多项式直接得到系统码。因为系统码中，信息位占据了码字的前k个位置，而信息多项式为如果用 乘以m(x)，得到如果在其后加上n-k比特的校验位，就构成了码字.,信息论与编码-循环码,也就是说，要在上面的多项式后面加上次数底于n-k的多项式。这个多项式应该是用g(x)除，

8、得到的余式r(x)（商为Q(x)），即也就是说，得到的码多项式为由于g(x)是码多项式，因此Q(x)g(x)也是码字，这样由信息多项式得到的码字一定是系统码。,信息论与编码-循环码,归纳起来，我们可以得到由信息组得到对应系统码字的方法是：（1）由信息组得到信息多项式，将信息多项式 乘以；（2）用g(x)除，得到余式r(x)；（3）将r(x)加在 后面，得到码多项式，从而得到其对应的码字（码多项式的系数）。,信息论与编码-循环码,例题：（7，4）循环码的生成多项式为求（1）该循环码系统形式的生成矩阵；（2）对于给定的信息组（1001），求其对应的系统形式的码字。,信息论与编码-循环码,解：（1）

9、生成矩阵 将生成多项式及其对应的循环移位多项式作为基底，得到一般形式的生成矩阵为,信息论与编码-循环码,系统形式的生成矩阵：一种办法是将一般形式的生成矩阵通过行变换和列置换，得到系统形式；通过矩阵运算:将矩阵第3,4行加到第1行:将矩阵第4行加到第2行,信息论与编码-循环码,另一种方法：第一行，前四列为1000，对应的多项式为，除以生成多项式，得余式为，所以对应的后三列为101；同样的办法，可以得到第二行为0100111；第三行为0010110；第四行为0001011；因此，得到系统形式的生成矩阵。,信息论与编码-循环码,（2）对应信息组（1001）的码字，可以由生成矩阵得到，也可以直接得到，

10、即用信息组多项式 乘以得到，除以码多项式，得余式为，因此，码多项式为对应的码字为：1001110,信息论与编码-循环码,循环码编码电路实现的硬件结构图,用除法器实现(7,4)循环码编码器,1,1,k2,k1,(m0,m1,m2,m3),信息论与编码-循环码,带反馈移存器构成除以g(x)=x3+x+1的除法电路，反馈线的位置与g(x)的项对应，左到右分别对应1，x,x2 和x3。正常做除法时，m(x)应从除法器最左端(对应g(x)常数项1)进入。如m(x)右移一位，则应从g(x)一次项x的位置进入，相当于作xm(x)运算再去做除法。,信息论与编码-循环码,m(x)从xn-k=x3 的位置进入，相

11、当于作xn-k m(x)运算再去除以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

12、)xk+r-1+(akb 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)运算电路,信息论与编码-循环码,工作开始时，r级移位存贮器中的存数全清洗为 0，且规定被乘多项式A(x)的高次项系数ak首先送入电路，电路的工作过程如下：(1)当A(x)的最高次系数ak首先送入时，乘积C(x)的最高次项xk+r的系数akb

13、r就出现在输出端，同时ak存入移存器的第一级(最左一级)。,信息论与编码-循环码,(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 初态，乘法 完成。由上面乘法过程可以看出,这种乘法电路完成一次乘法运算

14、,共需移位k+r+1次。,信息论与编码-循环码,图 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电路,信息论与编码-循环码,为了理解除法电路的工作过程，下面

15、我们列出B(x)除A(x)的竖式运算式子：brxr+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)的最

16、高次项xk的系数ak首先进入电路的最左一级。r次移位后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项所示的结果。,信息论与编码-循环码,(3)

17、依次类推，经k+1 次移位后，完成了整个除法运算过程。它的输出为商式q(x)，而移存器中的内容就是余式r(x)的系数,信息论与编码-循环码,例 设除式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电路,信息论与编码-循环码,完成上述两个多项式相除的长除法运算式如下：,x+1(商式)x3+x+1 x

18、4+x3+1(被除式)(除式)x4+x2+x x3+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

19、(x)=hrxr+h r-1 x r-1+h1x+h0 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)电路,信息论与编码-循

20、环码,例 设GF(2)上的 3 个多项式为：A(x)=x4+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)(x

21、3+x+1)=x7+x5+x3+x2+1=(x5+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)电路,信息论与编码-循环码,电路运算过程表,循环码将生成矩阵简化为生成多项式，从而将与编码矩阵对应的硬件阵列（平面型）简化为带反馈的移存器（直线型）。针对循环码的特点，在译码上也出了许多高效的算法，如捕错译码、大数逻辑译码等，限于篇幅

22、，这里不再讨论译码的问题。,信息论与编码-循环码,信息论与编码-循环码,一个码可以兼有很多的特点，循环特征仅是其中之一。前面讲过的汉明码也可以兼有循环特征，这类码叫循环汉明码，其分组长度是n=2m1,校验位nk=m，而任何码字的循环依然是码字。同样，兼有循环特征的高莱码叫作循环高莱码，比如用生成多项式g(x)=x11+x9+x7+x6+x5+x+1 产生的线性（23，12）高莱码就是循环高莱码。在无线信道上应用最广泛的BCH码、RS码也是循环码，它们在具有循环特性的基础上又兼有另一些特点。,信息论与编码-BCH码和RS码,BCH码BCH（Bose：Chaudhuri-Hocquenghem）码

23、是循环码中一大子类，它可以是二进制码，也可以是非二进制码。二进制本原BCH码具有下列参数：式中m（m=3）和纠错能力t()是任意正整数。,信息论与编码-BCH码和RS码,BCH码的基本特点是其生成多项式g(x)包含2t个连续幂次的根。由上面关于循环码的论述可知，若在二元域GF(2)上把 分解为l个最小多项式m(x)，i1,2,l 之积，其中l1个组成g(x)而剩余的组成h(x)，则包含于g(x)中的最小多项式一定满足式中“|”表示整除，C（x）表示码多项式。,信息论与编码-BCH码和RS码,由近世代数可进一步得知，在二元扩域GF(2m)上可把xn+1分解为如下n个根的乘积式中，a是GF(2m)

24、上本原元，n（2m1）。若对于每个j，j1，2，2t，均有即g(x)包含2t个连续幂次的根,则由该g(x)生成的循环码就是纠错能力不小于t的BCH码,信息论与编码-BCH码和RS码,BCH的出现为通讯系统设计者们在纠错能力，码长和码率的灵活设计上提供了很大的选择余地，一旦要求的纠错能力t给定，只要算出2t个连续幂次的根所对应的多项式作为生成多项式，即可得出纠错能力符合要求的码。又因其构码方法带来的译码特点，使之可以用伯利坎普（Berlekamp）迭代译码等通用，高效的译码算法，以致BCH码从70年代起已成为线性分组码的主流。,信息论与编码-BCH码和RS码,已知码长n及纠错能力t，二元本原BC

25、H码的具体设计步骤如下：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码,例 设计一个n=7的二元本原BCH码，求出不同纠错能力下的生成多项式。解：因7=23-1,因此m=3.1.查表找出一个三次本原多项式，本题为P(x)=

26、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+x3+x2+x+1纠错能力至少是t.,元素 多项式 矢量表示 极小多项式 0 0 000 x a0 1 001

27、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码,RS译码RS译码（ReedSolomon里德-索罗门码）属于BCH码的一个子类，是一种q进制（q2）的BCH码，其码的每个码元取值于符号集0,a0,a1,aq-2 实用时通常选取q为2的幂次（q2m），以便一组m个信息比特可以一一映射到q个符号之一，也便于与4，8，16，32，信号点集的PSK或Q

28、AM调制相适应。若m8即256进制，可以将整个8比特字节变为RS码的一个码元。,信息论与编码-BCH码和RS码,如果用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码,RS码的重量分布是已知的。码重多项式第i次项的系数（重量为i的码字个数）是 RS码之所以重要，原因之一是该码的距离特性好，是（MDC）码。第二是因为存在一

29、种有效的硬判决法，使得在许多需要长码得应用场合，该码能够被实现。第三是q进制RS码得二进衍生码具有良好的抗突发差错能力。,信息论与编码-BCH码和RS码,二进制衍生码 对于一个q=2m进制（n，k）RS码，如果不用q进制调制发送，而是将每码元对应为m比特后以二进制发送,实际上就是把q进制RS码化作了（mn，mk）二进制衍生码，这样的二进制衍生码特别适用于纠突发差错，下面举例说明。,信息论与编码-BCH码和RS码,例，一个8进制（7，3）RS码的a幂次，多项式及三比特组这三种形式的符号集如表6-7，写出相应的RS码的生成多项式。如输入的8进制信息元为a5a3a1，问编出的8进制RS码字是什么，纠

30、错能力如何？解：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)二进制衍生码：信息码元：a5a3a1(111,011,010)码字：a5a3aa6a4a21(111,011,010,101,110,100,001),信息论

31、与编码-BCH码和RS码,衍生码就突发错误的能力：八进制RS码能纠每码字两个字符的差错。对于其二进制衍生码，若以二进制信号在信道上传送，突发差错长度比特时最多影响到两个八进制符号时，可纠正；若突发差错长度等于5时，可能只影响两个八进制符号，也可能跨三各八进制符号，就不一定能纠正了。一般的结论：若q进制（q=2m）RS码的纠错能力是t个q进制符号，那么它的二进衍生码能纠正的二进制突发差错长度b为,信息论与编码-码的扩展和缩短,码的扩展和缩短：可以通过增加或删除信息位或校验位的方法改变码率，改变纠检错能力，以满足不同的需要。常用的方法有：增信，删余，增余，删信，及组合,信息论与编码-码的扩展和缩短

32、,扩展码 设C是一个最小距离为d的二进制n,k,d线性分组码，它的码字有奇数重量也有偶数重量。若对每一个码字(cn-1,cn-2,c1.c0)增加一个校验元c0，满足以下校验关系：cn-1+cn-2+c1+c0+c0=0 称c0为全校验位。,若原码的校验矩阵为H，则扩展码 的校验矩阵为,2m-1，2m-1-m，3汉明码的扩张码是2m，2m-1-m，4码，它的 中的H是汉明码的校验 矩阵。最小码距由3增加为4,信息论与编码-码的扩展和缩短,信息论与编码-码的扩展和缩短,码的缩短：缩短循环码就是在(n，k)循环码的 个码字中挑选出前i位均为0的所有码字，组成一个新的(n-i,k-i)缩短循环码码集

33、。该码集是原循环码码集的一个子集，子集里所有码多项式的阶数均小于n-i且能够被生成多项式g(x)整除。反之，次数小于n-i的所有g(x)倍式一定包含于该子集中，是(n-i,k-i),缩短循环码的一个码多项式。一般来讲，每缩短一位，码字数目减少一半。,信息论与编码-码的扩展和缩短,特点：码的重量没有变，校验位的数量也没有变（n-i-(k-i)=n-k）,因此(n-i,k-i)缩短循环码的纠错能力于原来的（n,k）循环码码完全一样，3.码率R下降了，由k/n变为(k-i)/(n-i).4.循环码的外部特征在缩短循环码中已不复存在，缩短码码字的循环未必仍是码字；5.循环码的内部特征仍然存在，即所有的

34、码多项式一定能够被g(x)整除。,信息论与编码-码的扩展和缩短,这样，缩短循环码的编、译码可以借用循环码的方法，将消息多项式m(x)乘以 后 除以g(x)即可，所不同的是这里的消息多项式m(x)由(k-i)项组成而不是k项组成。缩短循环码用于检错时也和循环码一样，只要将接收序列除以g(x)后检查其余式即可，余式全0(除尽)则表示接收的时码字(g(x)的倍式)，否则就不是码字。,信息论与编码-码的扩展和缩短,CRC：缩短循环码的最大应用在于帧校验，这就是在数据通信中大家所熟悉的循环冗余校验码(CRC：Cyclic Redundancy Check)。在数据通信中，信息都是先划分成小块再组装成帧后

35、(或叫分组、包、信元，仅名称不同而已)在线路上统计复用传送或存入共同物理介质的，帧尾一般都留有8，12，16或32位用作差错校验。如把一帧视为一个码字，则其校验位长度nk不变而信息位k和码长n是可变的，正符合(ni，ki)缩短循环码的特点。只要以一个选定的(n，k)循环码位基础，改变i值，就能适用于任何信息长度的编码。,信息论与编码-码的扩展和缩短,例546 用于HDLC，X.25，ISDN和7号信令的CRCITUT循环冗余校验码的生成多项式为,CRC nk16位 r(x)信息ki位,015次 16n-i-1次低次 高次(先发)带CRC的帧结构,信息论与编码-码的扩展和缩短,根据循环码定义，g

36、（x）必定是 的因式，而g（x）是本原多项式，它所能整除的 中n的最小值是216-1，所以，g(x)生成的循环码是一个（65535，65519）循环码将该码所有前i位为零的码字去除前i位后集合在一起就构成（ni，ki）缩短循环码，表现为ki信息位加上16位CRC组成长度（ni）的一个帧。由于i可变，因此帧长可变。,信息论与编码-码的扩展和缩短,g（x）本身也是码字，而且是最轻的码字，所以本码的 能纠一个错误（t1）或检3个差错。另外，由此g(x)生成的码字的重量一定是偶数，所以它就能检出所有奇数个差错。,信息论与编码-码的扩展和缩短,将该码所有前i位为零的码字去除前i位后集合在一起就构成（ni

37、，ki）缩短循环码，表现为ki信息位加上16位CRC组成长度（ni）的一个帧。由于i可变，因此帧长可变。,实施CRC编码时，信息在输出的同时由位置输入移存器，相当于信息移16位后即,再除以g（x）。输完ki信息位后断开移存器的反馈线，将此时移存器内的数据（余式，即CRC校验码）移位输出即可。,信息论与编码-码的扩展和缩短,接收端校验时，只要将整个帧除以g（x）检查余式是否为零即可。如为零，说明传输无误；如余式非零，说明该帧有差错，须反馈重发和丢弃。除法器的结构与图544（b）所示相同，只是接收序列由最左端而不是从 处输入而已。,信息论与编码-码的扩展和缩短,接收端校验时，只要将整个帧除以g（x）检查余式是否为零即可。如为零，说明传输无误；如余式非零，说明该帧有差错，须反馈重发和丢弃。,作业6-11，6-12，6-13,