信息论与编码-第六章4

1、信息论与编码-循环码上次课小结：线性分组码的一些概念：域、矢量空间、线性 分组码；生成矩阵和校验矩阵伴随式与译码：伴随式的定义、标准阵列译码 表。信息论与编码-循环码 循环码是线性分组码中最重要的一类码。 循环码的特点是：码集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-n210121021201nnnnnnxxxxCxxxCxCxCxxxCxCxx

3、CxC位：移位：移位：移 因为一个码字经过n次循环移位后又变回自身，所以一个码字经循环移位最多产生n个码字。 而对于码长为n的码字，共有 个不同的码字，因此，不可能由一个码字经循环移位得到所有可能的码字。 但是，可以由一个基底矢量经循环移位得到所有k个基底矢量，所有的码字都可以由这k个基底的线性组合构成。k2信息论与编码-循环码信息论与编码-循环码因此，设 对应一个码字，则其线性组合：其中，A(x)是任意多项式， 是一个码多项式。也就是说，任意一个码多项式与一个多项式之积，仍然是一个码多项式。上述运算是在模运算的前提下，即)(0 xC)()()()()()()()()(00112210011j

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

5、（n-k次）的首一（即第一项的系数为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）次因子为生

6、成多项式g(x)，与信息多项式m(x)相乘，得到的多项式C(x)=m(x)g(x)即为码多项式。1nx信息论与编码-循环码例题：研究一个长度为7的循环码的构成方法。解：根据上面的循环码编码方法，首先对 做因式分解，得到17x) 1)(1)(1(13237xxxxxx信息论与编码-循环码所以， 的因子共有以下几种： ：次数为1（1个）； ， ：次数为3（2个）； ， ：次数为4（2个）； ：次数为6（1个）；另外还有次数为0的因子： 1次数为7的因子：如果给定了n和k，那么只能选用满足要求的（n-k）次多项式作为生成多项式，本题中没有要求k，可以选用不同的多项式做生成多项式，当然会得到不同的码集

7、。17x) 1( x) 1(23 xx) 1(3 xx) 1)(1(23xxx) 1)(1(3xxx) 1)(1(233xxxx17x信息论与编码-循环码g(x) n-k k n,k1 0 7 7,7 x+1 1 6 7,6 3 4 7,4 3 4 7,4 4 3 7,3 4 3 7,3 6 1 7,1 7 0 7,0) 1(23 xx) 1(3 xx) 1)(1(23xxx) 1)(1(3xxx) 1)(1(233xxxx17x信息论与编码-循环码设选取 为生成多项式，则n-k=3，k=4，所以信息多项式为信息码组共有16种不同的组合，因此，共有16个码字。例如则循环编码后的码多项式为对应的

8、码字为（0101110）。) 1()(23xxxg1)(32231xmxmxmxm)0110()(0123mmmmmxxxxxxxxxC235232) 1)()(信息论与编码-循环码o 相同地，可以得到不同信息组的时候的码字。可以看出，码集中有四组码字循环信息比特码字（循环1）信息比特 码字（循环2） 信息比特 码字 （循环3和4）0001001001001000110101111110000110100110100110100110100010100010100011100011000110110110001011010100111110010111010111010111000111001

9、1110010110010110010110000101100000001111111信息论与编码-循环码一致校验多项式如果 分解为 ，选g(x)为生成多项式，则h(x)称为码的一致校验多项式，阶次为k，和校验矩阵类似，校验多项式满足：当然，也可以选择h(x)为码生成多项式，则g(x)就是一致校验多项式。因此，由g(x)生成的（n，k）码和由h(x)生成的（n，k）码互为对偶码。1nx)()(1xhxgxn) 1mod(0) 1)()()()()()(nnxxxmxhxgxmxhxC信息论与编码-循环码循环码是线性分组码的一种。对于线性分组码，可以用生成矩阵来描述。具体到循环码，则简化为生成多

10、项式。因此也一定可以用生成矩阵来描述循环码。所谓生成矩阵，就是码空间的一组基底。而生成多项式及其移位后的一组多项式，就可以作为一组基底，因此，如果循环码的生成多项式为1)(111xgxgxxgknknkn信息论与编码-循环码则生成矩阵为这种形式的生成矩阵不是系统形式的。如果要生成系统形式的生成矩阵，则第l行应是多项式1000000100101100010010001)()()()(12112121121121ggggggggggggGxgxxgxgxxgxknknknknkk信息论与编码-循环码这里， 是 除以g(x)的余式，因为所以由于g(x)是码字，所以 也是码字，因此 也一定是码字，可以

11、作为基底。klxRxlln, 2 , 1),()(xRllnx)()()(xRxgxQxllln)()()(xgxQxRxllln)()(xgxQl)(xRxlln信息论与编码-循环码实际上，可以由生成多项式直接得到系统码。因为系统码中，信息位占据了码字的前k个位置，而信息多项式为如果用 乘以m(x)，得到如果在其后加上n-k比特的校验位，就构成了码字.012211)(mxmxmxmxmkkkkknxknknnknkknxmxmxmxmxmx0112211)(信息论与编码-循环码也就是说，要在上面的多项式后面加上次数底于n-k的多项式。这个多项式应该是用g(x)除 ，得到的余式r(x)（商为Q

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

13、成矩阵；（2）对于给定的信息组（1001），求其对应的系统形式的码字。1)(3xxxg信息论与编码-循环码解： （1）生成矩阵 将生成多项式及其对应的循环移位多项式作为基底，得到一般形式的生成矩阵为1101000011010000110100001101G信息论与编码-循环码o 系统形式的生成矩阵：一种办法是将一般形式的生成矩阵通过行变换和列置换，得到系统形式；o 通过矩阵运算:将矩阵第3,4行加到第1行:o 将矩阵第4行加到第2行1101000011010011100101010001G信息论与编码-循环码另一种方法：第一行，前四列为1000，对应的多项式为 ，除以生成多项式 ，得余式为 ，

14、所以对应的后三列为101；同样的办法，可以得到第二行为0100111；第三行为0010110；第四行为0001011；因此，得到系统形式的生成矩阵。6x1)(3xxxg1)(2 xxr信息论与编码-循环码（2）对应信息组（1001）的码字，可以由生成矩阵得到，也可以直接得到，即用信息组多项式 乘以得到 ，除以码多项式 ，得余式为 ，因此，码多项式为对应的码字为：10011101)(3012233xmxmxmxmxm3xxkn36)(xxxmxkn1)(3xxxgxxxr2)(xxxxxrxmxxCkn236)()()(信息论与编码-循环码DDD1xX32循环码编码电路实现的硬件结构图 用除法器

15、实现(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)运算再去做除法。 信息论与编码-循环码o m(x)从xn-k =x3 的位置进入，相当于作xn-k m(x)运算再去除以g(x)。每编一个码需化n=7拍时间。前4拍时开关k1 ，k2 在位置1，消息位先m3 再m2,m1,m0 依次输入除法器做x

16、n-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 r-2+ak-1b r-1+ak-2br)xk+r-2+ +(akb r-i+ak-1b r-(i-1)+ak-ibr)xk+

17、r-i+ +(a1b0+a0b1)x+a0b0 可用下图所示的电路完成上述运算过程。 该电路由r个存贮单元组成的r 级移位寄存器， 至多r个模q相加器和至多(r+1)个模q常乘器所组成。 信息论与编码-循环码乘B(x)运算电路 信息论与编码-循环码o 工作开始时， r级移位存贮器中的存数全清洗为 0， 且规定被乘多项式A(x)的高次项系数ak首先送入电路， 电路的工作过程如下：o (1) 当A(x)的最高次系数ak首先送入时， 乘积C(x)的最高次项xk+r的系数akbr就出现在输出端， 同时ak存入移存器的第一级(最左一级)。 信息论与编码-循环码 (2) A(x)的第二个系数ak-1送入电

18、路时,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次。 信息论与编码-循环码图 5 - 4 另一种乘B(x)电路 多项式除

19、法电路 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)的竖式运算式子： brxr+b r-1 x r-

20、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首先进入电路的最左一级。

21、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项所示的结果。 信息论与编码-循环码o (3) 依次类

22、推， 经k+1 次移位后， 完成了整个除法运算过程。 它的输出为商式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

23、(商式) x3+x+1 x4+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)分

24、别为： A(x)=akxk+ak-1xk-1+a1x+a0 H(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)中最高次数设计移存器级数 即

25、可。 信息论与编码-循环码图 5 - 8 乘H(x)除G(x)电路 信息论与编码-循环码例 设GF(2)上的 3 个多项式为： A ( x ) = x 4 + x + 1 ， H ( x ) = x 2 + 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)电路 信息论

26、与编码-循环码 若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+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)电路信息论与编码-循环码电路运算过程表

27、o 循环码将生成矩阵简化为生成多项式，从而将与编码矩阵对应的硬件阵列（平面型）简化为带反馈的移存器（直线型）。o 针对循环码的特点，在译码上也出了许多高效的算法，如捕错译码、大数逻辑译码等，限于篇幅，这里不再讨论译码的问题。信息论与编码-循环码信息论与编码-循环码 一个码可以兼有很多的特点，循环特征仅是其中之一。前面讲过的汉明码也可以兼有循环特征，这类码叫循环汉明码，其分组长度是n=2m1,校验位nk=m，而任何码字的循环依然是码字。同样，兼有循环特征的高莱码叫作循环高莱码，比如用生成多项式g(x)=x11+x9+x7+x6+x5+x+1 产生的线性（23，12）高莱码就是循环高莱码。在无线信

28、道上应用最广泛的BCH码、RS码也是循环码，它们在具有循环特性的基础上又兼有另一些特点。信息论与编码-BCH码和RS码BCH码BCH（Bose：Chaudhuri-Hocquenghem）码是循环码中一大子类，它可以是二进制码，也可以是非二进制码。二进制本原BCH码具有下列参数：式中m（m=3）和纠错能力t( )是任意正整数。12mnmtkn12min td12m信息论与编码-BCH码和RS码o BCH码的基本特点是其生成多项式g(x)包含2t个连续幂次的根。由上面关于循环码的论述可知，若在二元域GF(2)上把 分解为l个最小多项式m(x)，i1,2,l 之积，其中l1个组成g(x)而剩余的组

29、成h(x)，则包含于g(x)中的最小多项式一定满足o 式中“|”表示整除，C（x）表示码多项式。o 1nx) 1( | )(| )(| )(nixxCxgxm信息论与编码-BCH码和RS码o 由近世代数可进一步得知，在二元扩域GF(2m)上可把xn+1分解为如下n个根的乘积o 式中，a是GF(2m)上本原元，n（2m1）。若对于每个j，j1，2，2t，均有o 即g(x)包含2t个连续幂次的根,则由该g(x)生成的循环码就是纠错能力不小于t的BCH码)()()() 1(1210nnaxxxxx11)()(| )liijxmxgax（信息论与编码-BCH码和RS码 BCH的出现为通讯系统设计者们在

30、纠错能力，码长和码率的灵活设计上提供了很大的选择余地，一旦要求的纠错能力t给定，只要算出2t个连续幂次的根所对应的多项式作为生成多项式，即可得出纠错能力符合要求的码。 又因其构码方法带来的译码特点，使之可以用伯利坎普（Berlekamp）迭代译码等通用，高效的译码算法，以致BCH码从70年代起已成为线性分组码的主流。信息论与编码-BCH码和RS码o 已知码长n及纠错能力t，二元本原BCH码的具体设计步骤如下：o 1。由关系式n=2m-1算出m，查表找到m次本原多项式P(x)，用它产生一个GF(2m)扩域o 2。以本原多项式P(x)的根为本原元a，分别计算2t个连续幂次根a，a2，a2t所对应的

31、二元域上的最小多项式m1(x), m2(x), , m2t(x).o 3。计算这些最小多项式的最小公倍式，得到生成多项式为o g(x)=LCM(m1(x), m2(x), , mt2(x)o 4. 得到BCH码字 c(x)=m(x)g(x)信息论与编码-BCH码和RS码o 例 设计一个n=7的二元本原BCH码，求出不同纠错能力下的生成多项式。o 解：因7=23-1,因此m=3.o 1.查表找出一个三次本原多项式，本题为P(x)=x3+x+1o 然后令a为P(x)的根，生成扩域GF(23)的所有元素，见表6-7o 最大纠错能力为t=3。信息论与编码-BCH码和RS码2。每个根所对应的最小多项式，

32、由表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 x+1 a1 a 010 x3+x+1 a2 a2 100 x3+x+1 a3 a x3+x2+1 a4 a2 +a 110 x3+x+1 a5 a2 +a

33、x3+x2+1 a6 a2 x3+x2+1 x3+x+1生成的GF（23）扩域信息论与编码-BCH码和RS码o RS码码o RS译码（译码（ReedSolomon里德里德-索罗门码）属于索罗门码）属于BCH码的一个子类，是一种码的一个子类，是一种q进制（进制（q2）的）的BCH码，其码的每个码元取值于符号集码，其码的每个码元取值于符号集0,a0,a1,aq-2 o 实用时通常选取实用时通常选取q为为2的幂次（的幂次（q2m），以便一），以便一组组m个信息比特可以一一映射到个信息比特可以一一映射到q个符号之一，也个符号之一，也便于与便于与4，8，16，32，信号点集的信号点集的PSK或或QAM调

34、制相适应。调制相适应。o 若若m8即即256进制，可以将整个进制，可以将整个8比特字节变为比特字节变为RS码的一个码元。码的一个码元。 信息论与编码-BCH码和RS码o 如果用N表示RS码的码长，K表示信息符号的长度，NK表示校验符号码的长度，则RS码的参数可以用以下式子来表达o 码长n=q-1o 校验位n-k=2to 最小距离dmin=n-k+1(MDC码)o 生成多项式g(x)=(x-a)(x-a2)(x-a2t)o =an-kxn-k+an-k-1xn-k-1+a1x+a0信息论与编码-BCH码和RS码o RS码的重量分布是已知的。码重多项式第i次项的系数（重量为i的码字个数）是 o R

35、S码之所以重要，原因之一是该码的距离特性好，是（MDC）码。第二是因为存在一种有效的硬判决法，使得在许多需要长码得应用场合，该码能够被实现。第三是q进制RS码得二进衍生码具有良好的抗突发差错能力。 qADjiDqinjiijjiminmin1) 1(0) 1( 信息论与编码-BCH码和RS码o 二进制衍生码 o 对于一个q=2m进制（n，k）RS码，如果不用q进制调制发送，而是将每码元对应为m比特后以二进制发送,实际上就是把q进制RS码化作了（mn，mk）二进制衍生码，这样的二进制衍生码特别适用于纠突发差错，下面举例说明。 信息论与编码-BCH码和RS码o 例，一个8进制（7，3）RS码的a幂

36、次，多项式及三比特组这三种形式的符号集如表6-7，写出相应的RS码的生成多项式。如输入的8进制信息元为a5a3a1，问编出的8进制RS码字是什么，纠错能力如何？o 解：n=7,k=3,dmin=n-k+1=5,纠错能力t=2，生成多项式为o 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)二

37、进制衍生码：信息码元： 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信息论与编码-码的

38、扩展和缩短o 码的扩展和缩短：o 可以通过增加或删除信息位或校验位的方法改变码率，改变纠检错能力，以满足不同的需要。常用的方法有：o 增信，删余，增余，删信，及组合信息论与编码-码的扩展和缩短o 扩展码o 设C是一个最小距离为d的二进制n,k,d线性分组码， 它的码字有奇数重量也有偶数重量。 若对每一个码字(cn -1,cn -2, ,c1. c0)增加一个校验元c0， 满足以下校验关系： o cn-1+cn-2+c1+c0+c0=0o 称c0为全校验位。 若原码的校验矩阵为H， 则扩展码 的校验矩阵为C1.1100HH2m-1， 2m-1-m， 3汉明码的扩张码是2m， 2m-1-m， 4码

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