资源描述
,通信原理(第6版),单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,通信原理,1,通信原理,第11章过失掌握编码,2,过失掌握 error-control,信道编码器 channel encoder,反响信道 feedback channel,检错重发 error detection and retransmission,前向纠错 forward error correction,自动恳求重发 automatic-repeat request,3,第11章过失掌握编码,11.1 概述,信道分类：从过失掌握角度看,随机信道：错码的消失是随机的,突发信道：错码是成串集中消失的,混合信道：既存在随机错码又存在突发错码,过失掌握技术的种类,检错重发,前向纠错,反响校验,检错删除,4,第11章过失掌握编码,过失掌握编码：常称为纠错编码,监视码元：在发送端需要在信息码元序列中增加一些过失掌握码元，它们称为监视码元。,不同的编码方法，有不同的检错或纠错力量。,多余度：就是指增加的监视码元多少。例如，假设编码序列中平均每两个信息码元就添加一个监视码元，则这种编码的多余度为1/3。,编码效率(简称码率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。,冗余度：监视码元数(n-k) 和信息码元数 k 之比。,理论上，过失掌握以降低信息传输速率为代价换取提高传输牢靠性。,5,第11章过失掌握编码,自动要求重发(ARQ)系统,3种ARQ系统,停顿等待ARQ系统,数据按分组发送。每发送一组数据后发送端等待接收端确实认(ACK)答复，然后再发送下一组数据。,系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。,接收码组,ACK,ACK,NAK,ACK,ACK,NAK,ACK,t,1,2,3,3,4,5,5,发送码组,1,2,3,3,4,5,5,6,t,有错码组,有错码组,6,第11章过失掌握编码,拉后ARQ系统,发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。,在这种系统中需要对发送的数据组和答复进展编号，以便识别。明显，这种系统需要双工信道,接收数据,有错码组,有错码组,9,10,11,10,11,12,2,1,4,3,6,5,7,9,8,5,7,6,ACK,1,NAK,5,NAK,9,ACK,5,发送数据,5,7,6,9,5,2,1,4,3,6,7,9,8,10,11,10,11,12,重发码组,重发码组,7,第11章过失掌握编码,选择重发ARQ系统,它只重发出错的数据组，因此进一步提高了传输效率。,接收数据,有错码组,有错码组,9,2,1,4,3,6,5,7,5,9,8,10,11,13,14,12,发送数据,9,9,5,8,5,2,1,4,3,6,7,10,11,13,14,12,重发码组,重发码组,NAK,9,ACK,1,NAK,5,ACK,5,ACK,9,8,第11章过失掌握编码,ARQ的主要优点：和前向纠错方法相比,监视码元较少即能使误码率降到很低，即码率较高；,检错的计算简单度较低；,检错用的编码方法和加性干扰的统计特性根本无关，能适应不同特性的信道。,ARQ的主要缺点：,需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。,由于重发而使ARQ系统的传输效率降低。,在信道干扰严峻时，可能发生因不断反复重发而造成事实上的通信中断。,在要求实时通信的场合，例如 通信，往往不允许使用ARQ法。,9,第11章过失掌握编码,ARQ系统的原理方框图,在发送端，输入的信息码元在编码器中被分组编码参加监视码元后，除发送外，还暂存于缓冲存储器中。,接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。,当解码器未觉察错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即连续发送后一码组，发送端的缓冲存储器中的内容也随之更新。,10,11.2 纠错编码的根本原理,实例：,000(晴) 001(云) 010(阴) 011(雨) 100(雪) 101(霜) 110(雾) 111(雹),000(晴) 011(云) 101(阴) 110(雨),000(晴) 111(雨),只允许使用4组,使用2组,不能觉察错误,可能觉察一个错误或检测3个错码,检测2个以下错码，或能订正一个错码,11,第11章过失掌握编码,信息位,监督位,晴,00,0,云,01,1,阴,10,1,雨,11,0,假设不要求检(纠)错，为了传输4种不同的信息，我们用两位码组：00，01，10，11。代表所传信息的这些两位码，称为信息位。,12,第11章过失掌握编码,将信息码分组，为每组信码附加假设干监视码的编码集合，称为分组码。,分组码一般用符号(n,k)表示，其中k是每组二进信息码元的数目，n是编码组的总位数，又称为码组长度码长，n-k=r为每码组中的监视码元数目，或称监视位数目。,13,第11章过失掌握编码,分组码的码重和码距,码重：把码组中“1”的个数目称为码组的重量，简称,码重,。,码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称,码距,。码距又称,汉明距离,。,例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。,最小码距：把某种编码中各个码组之间距离的最小值称为,最小码距,(,d,0,)。例如，上面的编码的最小码距,d,0,= 2。,14,第11章过失掌握编码,码距的几何意义,对于3位的编码组，可以在3维空间中说明码距的几何意义。,每个码组的3个码元的值(,a,1,a,2,a,3,)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。,由此图可以直观看出，上例中4个准用码组之间的距离均为2。,(0,0,0),(0,0,1),(1,0,1),(1,0,0),(1,1,0),(0,1,0),(0,1,1),(1,1,1),a,2,a,0,a,1,15,第11章过失掌握编码,码距和检纠错力量的关系,一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错力量,为检测e个错码，要求最小码距 d0 e + 1,【证】设一个码组A位于O点。假设码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。,假设码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，,不行能变成另一个准用,码组，因而能检测错码,的位数等于2。,0,1,2,3,B,A,汉明距离,e,d,0,16,第11章过失掌握编码,同理，假设一种编码的最小码距为d0，则将能检测(d0 - 1)个错码。反之，假设要求检测e个错码，则最小码距d0至少应不小于( e + 1)。,为了订正t个错码，要求最小码距d0 2t + 1,【证】图中画出码组A和B的距离为5。码组A或B假设发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规章为：假设接收码组落于以A为圆心的圆上就判决收到的是码组A，假设落于以B为圆心的圆上就判决为码组B。,这样，就能够纠,正两位错码。,B,t,A,汉明距离,0,1,2,3,4,5,t,d,0,17,第11章过失掌握编码,假设这种编码中除码组A和B外，还有很多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会相互重叠。这样，每种码组假设发生不超过两位错码都将能被订正。因此，当最小码距d05时，能够订正2个错码，且最多能订正2个。假设错码到达3个，就将落入另一圆上，从而发生错判。故一般说来，为订正t个错码，最小码距应不小于(2t + 1)。,18,第11章过失掌握编码,为订正t个错码，同时检测e个错码，要求最小码距,在解释此式之前，先来分析以下图所示的例子。图中码组A和B之间距离为5。依据检错力量公式，最多能检测4个错码，即e = d0 1 = 5 1 = 4，依据纠错力量公式纠错时，能订正2个错码。但是，不能同时作到两者，由于当错码位数超过纠错力量时，该码组马上进入另一码组的圆内而被错误地“订正”了。,B,t,A,汉明距离,0,1,2,3,4,5,t,d,0,19,第11章过失掌握编码,所以，为了在可以订正t个错码的同时，能够检测e个错码，就需要像以下图所示那样，使某一码组譬如码组A发生e个错误之后所处的位置，与其他码组譬如码组B的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“订正”。因此，由此图可以直观看出，要求最小码距,这种纠错和检错结合的工作方式简称纠检结合。,A,B,e,1,t,t,汉明距离,20,第11章过失掌握编码,这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反响重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的状况。,21,第11章过失掌握编码,11.3 纠错编码的性能,系统带宽和信噪比的冲突：,由上节所述的纠错编码原理可知，为了削减接收错误码元数量，需要在发送信息码元序列中参加监视码元。这样作的结果使发送序列增长，冗余度增大。假设仍须保持发送信息码元速率不变，则传输速率必需增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，承受纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。,22,第11章过失掌握编码,编码性能举例,未承受纠错编码时，,假设接收信噪比等于,7dB，编码前误码率,约为810-4，图中A,点，在承受纠错编码,后，误码率降至约4,10-5，图中B点。这样，,不增大发送功率就能,降低误码率约一个半,数量级。,10,-6,10,-5,10,-4,10,-3,10,-2,10,-1,编码后,P,e,C,D,E,A,B,信噪比 (dB),23,第11章过失掌握编码,由图还可以看出，假设,保持误码率在10-5，,图中C点，未承受编,码时，约需要信噪比,Eb / n0 = 10.5 dB。在,承受这种编码时，约,需要信噪比7.5 dB，图,中D点。可以节省功率,2 dB。通常称这2 dB为,编码增益。,上面两种状况付出的代,价是带宽增大。,10,-6,10,-5,10,-4,10,-3,10,-2,10,-1,编码后,P,e,C,D,E,A,B,信噪比 (dB),24,第11章过失掌握编码,传输速率和Eb/n0的关系,对于给定的传输系统,式中，RB为码元速率。,假设希望提高传输速率，,由上式看出势必使信,噪比下降，误码率增,大。假设系统原来工作,在图中C点，提高速率后,由C点升到E点。但加用,纠错编码后，仍可将误码,率降到D点。这时付出的,代价仍是带宽增大。,10,-6,10,-5,10,-4,10,-3,10,-2,10,-1,编码后,P,e,C,D,E,A,B,信噪比 (dB),25,例,码组集中有8个码组为000000、001110、010101、011011、100011、101101、110110、111000，假设用于检错，能检出几位错码？假设用于纠错，能订正几位错码？,解：最小码距dmin =3。所以,用于检错，由dmin e+1得e=2，能检出2位错码。,用于纠错，由dmin 2t+1得t=1，能订正1位错码。,26,线性分组码 linear block codes,循环码 cyclic codes,卷积码 convolutional codes,纠错码 error-correcting codes,检错 error detection,纠错 error correcting,混合纠错 hybrid error correct,27,第11章过失掌握编码,11.4简洁的有用编码,11.4.1 奇偶监视码,奇偶监视码分为奇数监视码和偶数监视码两种，两者的原理一样。在偶数监视码中，无论信息位多少，监视位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：,式中a0为监视位，其他位为信息位。,这种编码能够检测奇数个错码。在接收端，依据上式求“模2和”，假设计算结果为“1”就说明存在错码，结果为“0”就认为无错码。,奇数监视码与偶数监视码相像，只不过其码组中“1”的数目为奇数：,28,第11章过失掌握编码,11.4.2 二维奇偶监视码方阵码,二维奇偶监视码的构成,它是先把上述奇偶监视码的假设干码组排成矩阵，每一码组写成一行，然后再按列的方向增加其次维监视位，如以下图所示,图中a01 a02 a0m为m行奇偶监视码中的m个监视位。,cn-1 cn-2 c1 c0为按列进展其次次编码所增加的监视位，它们构成了一监视位行。,29,第11章过失掌握编码,二维奇偶监视码的性能,这种编码有可能检测偶数个错码。由于每行的监视位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监视位检测出来。有一些偶数错码不行能检测出来。例如，构成矩形的4个错码，譬如图中,错了，就检测不出。,这种二维奇偶监视码适于检测突发错码。由于突发错码常常成串消失，随后有较长一段无错区间。,由于方阵码只对构成矩形四角的错码无法检测，故其检错力量较强。,二维奇偶监视码不仅可用来检错，还可以用来订正一些错码。 例如，仅在一行中有奇数个错码时。,30,第11章过失掌握编码,11.4.3 恒比码,在恒比码中，每个码组均含有一样数目的“1”和“0”。由于“1”的数目与“0”的数目之比保持恒定，故得此名。,这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。,恒比码的主要优点是简洁和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。,31,第11章过失掌握编码,11.4.4 正反码,正反码的编码：,它是一种简洁的能够订正错码的编码。其中的监视位数目与信息位数目一样，监视码元与信息码元一样或者相反则由信息码中“1”的个数而定。,例如，假设码长n = 10，其中信息位 k = 5，监视位 r = 5。其编码规章为：,当信息位中有奇数个“1”时，监视位是信息位的简洁重复；,当信息位有偶数个“1”时，监视位是信息位的反码。,例如，假设信息位为11001，则码组为1100111001；假设信息位为10001，则码组为1000101110。,32,第11章过失掌握编码,正反码的解码,在上例中，先将接收码组中信息位和监视位按模 2 相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。,假设接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；假设接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。,最终，观看校验码组中“1”的个数，按下表进展判决及订正可能觉察的错码。,33,第11章过失掌握编码,校验码组和错码的关系,例如，假设发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。,校验码组的组成,错码情况,1,全为“0”,无错码,2,有4个“1”和1个“0”,信息码中有1位错码，其位置对应校验码组中“0”的位置,3,有4个“0”和1个“1”,监督码中有1位错码，其位置对应校验码组中“1”的位置,4,其他组成,错码多于1个,34,第11章过失掌握编码,假设传输中产生了过失，使接收码组变成1000111001，则合成码组为100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。由于其中有4个“1”和1个“0”，按上表推断信息位中左边第2位为错码。,假设接收码组错成1100101001，则合成码组变成110010100110000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表推断，监视位中第1位为错码。,最终，假设接收码组为1001111001，则合成码组为100111100101010，校验码组与其一样，按上表推断，这时错码多于1个。,上述长度为10的正反码具有订正1位错码的力量，并能检测全部2位以下的错码和大局部2位以上的错码。,35,第11章过失掌握编码,11.5 线性分组码,根本概念,代数码：建立在代数学根底上的编码。,线性码：依据一组线性方程构成的代数码。在线性码中信息位和监视位是由一些线性代数方程联系着的。,线性分组码：依据一组线性方程构成的分组码 。,本节将以汉明码为例引入线性分组码的一般原理。,36,第11章过失掌握编码,汉明码,能够订正1位错码且编码效率较高的一种线性分组码,汉明码的构造原理。,在偶数监视码中，由于使用了一位监视位a0，它和信息位an-1 a1一起构成一个代数式：,在接收端解码时，实际上就是在计算,假设S = 0，就认为无错码；假设S = 1，就认为有错码。现将上式称为监视关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。,37,第11章过失掌握编码,假设监视位增加一位，即变成两位，则能增加一个类似的监视关系式。由于两个校正子的可能值有4中组合： 00，01，10，11，故能表示4种不同的信息。假设用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监视关系式能指示1位错码的 个可能位置。,一般来说，假设码长为n，信息位数为k，则监视位数rnk。假设希望用r个监视位构造出r个监视关系式来指示1位错码的n种可能位置，则要求,下面通过一个例子来说明如何具体构造这些监视关系式。,38,第11章过失掌握编码,例：设分组码(n, k)中k = 4，为了订正1位错码，由上式可知，要求监视位数 r 3。假设取 r = 3，则n = k + r = 7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监视关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：,S,1,S,2,S,3,错码位置,S,1,S,2,S,3,错码位置,001,a,0,101,a,4,010,a,1,110,a,5,100,a,2,111,a,6,011,a,3,000,无错码,39,第11章过失掌握编码,由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监视关系：,同理， a1、a3、a5和a6构成偶数监视关系：,以及a0、a3、a4 和a6构成偶数监视关系,40,第11章过失掌握编码,在发送端编码时，信息位a6、a5、a4和a3的值打算于输入信号，因此它们是随机的。监视位a2、a1和a0应依据信息位的取值按监视关系来确定，即监视位应使上3式中S1、S2和S3的值为0表示编成的码组中应无错码：,上式经过移项运算，解出监视位,给定信息位后，可以直接按上式算出监视位， 结果见下表：,41,第11章过失掌握编码,信息位,a,6,a,5,a,4,a,3,监督位,a,2,a,1,a,0,信息位,a,6,a,5,a,4,a,3,监督位,a,2,a,1,a,0,0000,000,1000,111,0001,011,1001,100,0010,101,1010,010,0011,110,1011,001,0100,110,1100,001,0101,101,1101,010,0110,011,1110,100,0111,000,1111,111,42,第11章过失掌握编码,接收端收到每个码组后，先计算出S1、S2和S3，再查表推断错码状况。例如，假设接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。,依据上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够订正1个错码或检测2个错码。由于码率k/n = (n - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。,43,第11章过失掌握编码,线性分组码的一般原理,线性分组码的构造,H,矩阵,上面(7, 4)汉明码的例子有,现在将上面它改写为,上式中已经将“,”简写成“+”。,44,第11章过失掌握编码,上式可以表示成如下矩阵形式：,上式还可以简记为,H,A,T,=,0,T,或,A,H,T,=,0,45,第11章过失掌握编码,H AT = 0T 或A HT = 0,式中,A = a6 a5 a4 a3 a2 a1 a0,0 = 000,右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的第一行为H的第一列，HT的其次行为H的其次列等等。,将H称为监视矩阵。,只要监视矩阵H给定，编码时监视位和信息位的关系就完全确定了。,46,第11章过失掌握编码,H矩阵的性质：,1) H的行数就是监视关系式的数目，它等于监视位的数目r。H的每行中“1”的位置表示相应码元之间存在的监视关系。例如，H的第一行1110100表示监视位a2是由a6 a5 a4之和打算的。H矩阵可以分成两局部，例如,式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型阵。,47,第11章过失掌握编码,2) 由代数理论可知，H矩阵的各行应当是线性无关的，否则将得不到 r个线性无关的监视关系式，从而也得不到 r个独立的监视位。假设一矩阵能写成典型阵形式P Ir，则其各行肯定是线性无关的。由于简洁验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。,G矩阵：上面汉明码例子中的监视位公式为,也可以改写成矩阵形式：,48,第11章过失掌握编码,或者写成,式中，Q为一个k r阶矩阵，它为P的转置，即 Q = PT,上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监视位。,49,第11章过失掌握编码,我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G,G称为生成矩阵，由于由它可以产生整个码组，即有,或者,因此，假设找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监视位附加于其后。这种形式的码称为系统码。,50,第11章过失掌握编码,G矩阵的性质：,1) G矩阵的各行是线性无关的。由于由上式可以看出，任一码组A都是G的各行的线性组合。G共有k行，假设它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部码组。假设G的各行有线性相关的，则不行能由G生成2k种不同的码组了。,2) 实际上，G的各行本身就是一个码组。因此，假设已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。,51,第11章过失掌握编码,错码矩阵和错误图样,一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入过失，故接收码组一般说来与A不肯定一样。,假设设接收码组为一n列的行矩阵B，即,则发送码组和接收码组之差为,B A = E (模2),它就是传输中产生的错码行矩阵,式中,52,第11章过失掌握编码,因此，假设ei = 0，表示该接收码元无错；假设ei = 1，则表示该接收码元有错。,B A = E 可以改写成 B = A + E,例如，假设发送码组A = 1000111，错码矩阵E = 0000100，则接收码组B = 1000011。,错码矩阵有时也称为错误图样。,53,第11章过失掌握编码,校正子S,当接收码组有错时，E 0，将B当作A代入公式(A H T = 0)后，该式不肯定成立。在错码较多，已超过这种编码的检错力量时，B变为另一许用码组，则该式仍能成立。这样的错码是不行检测的。在未超过检错力量时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即,B H T = S,将B = A + E代入上式，可得,S = (A + E) H T = A H T + E H T,由于A HT = 0，所以,S = E H T,式中S称为校正子。它能用来指示错码的位置。,S和错码E之间有确定的线性变换关系。假设S和E之间一一对应，则S将能代表错码的位置。,54,第11章过失掌握编码,线性分组码的性质,封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。,这就是说，假设A1和A2是一种线性码中的两个许用码组，则(A1+A2)仍为其中的一个码组。这一性质的证明很简洁。假设A1和A2是两个码组，则有,A1 HT = 0,A2 HT = 0,将上两式相加，得出,A1 HT + A2 HT = (A1 + A2) HT = 0,所以(A1 + A2)也是一个码组。,由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离即对应位不同的数目必定是另一个码组(A1 + A2)的重量即“1”的数目。因此，码的最小距离就是码的最小重量除全“0”码组外。,55,例,一码长n=15的汉明码，监视位r应为多少？编码效率为多少？,解：汉明码的监视位数目r与码长n满足关系式2r-1=n。此题中，n15，所以r4。,编码效率为,56,57,生成多项式 generator polynomial,奇偶校验 parity-check,移位存放器 shift register,约束长度 constraint length,编码器 encoder,系统码systematic code,58,第11章过失掌握编码,11.6 循环码,11.6.1 循环码原理,循环性：循环性是指任一码组循环一位马上最右端的一个码元移至左端，或反之以后，仍为该码中的一个码组。在下表中给出一种(7, 3)循环码的全部码组。,例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第7码组。,码组编号,信息位,监督位,码组编号,信息位,监督位,a,6,a,5,a,4,a,3,a,2,a,1,a,0,a,6,a,5,a,4,a,3,a,2,a,1,a,0,1,000,0000,5,100,1011,2,001,0111,6,101,1100,3,010,1110,7,110,0101,4,011,1001,8,111,0010,59,第11章过失掌握编码,一般说来，假设(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组,(an-2 an-3 a0 an-1),(an-3 an-4 an-1 an-2), (a0 an-1 a2 a1),也是该编码中的码组。,60,第11章过失掌握编码,码多项式,码组的多项式表示法,把码组中各码元当作是一个多项式的系数，即把一个长度为,n,的码组表示成,例如，上表中的任意一个码组可以表示为,其中第7个码组可以表示为,61,第11章过失掌握编码,码多项式的按模运算,在整数运算中，有模n运算。例如，在模2运算中，有,1 + 1 = 2 0 (模2)，,1 + 2 = 3 1 (模2)，,2 3 = 6 0 (模2),等等。一般说来，假设一个整数m可以表示为,式中，Q 整数，,则在模 n 运算下，有,m p (模n),即，在模 n 运算下，一个整数m等于它被 n 除得的余数。,62,第11章过失掌握编码,在码多项式运算中也有类似的按模运算。,假设一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即,则写为,这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3 + 1)除，得到余项1。所以有,同理,由于,x,x,3,+ 1,x,4,+,x,2,+ 1,x,4,+,x,x,2,+,x,+1,应当留意，由于在模2运算中，用加法代替了减法，故余项不是x2 x + 1，而是x2 + x + 1。,63,第11章过失掌握编码,循环码的码多项式,在循环码中，假设T(x)是一个长为n的许用码组，则xiT(x)在按模xn + 1运算下，也是该编码中的一个许用码组，即假设,则T (x)也是该编码中的一个许用码组。,【证】由于假设,则,模(xn + 1),所以，这时有,64,第11章过失掌握编码,上式中T (x)正是T(x)代表的码组向左循环移位i次的结果。由于原已假定T(x)是循环码的一个码组，所以T (x)也必为该码中一个码组。例如，循环码组,其码长n = 7。现给定i = 3，则,其对应的码组为0101110，它正是表中第3码组。,由上述分析可见，一个长为n的循环码必定为按模(xn + 1)运算的一个余式。,65,第11章过失掌握编码,循环码的生成矩阵G,由上节中公式,可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。,在循环码中，一个(n, k)码有2k个不同的码组。假设用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,66,第11章过失掌握编码,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有(k - 1)位。否则，在经过假设干次循环移位后将得到一个k位信息位全为“0”，但监视位不全为“0”的一个码组。这在线性码中明显是不行能的。因此，g(x)必需是一个常数项不为“0”的(n - k)次多项式，而且这个g(x)还是这种(n, k)码中次数为(n k)的唯一多项式。由于假设有两个，则由码的封闭性，把这两个相加也应当是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。明显，这是与前面的结论冲突的，故是不行能的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n, k)循环码就被确定了。,67,第11章过失掌握编码,因此，循环码的生成矩阵G可以写成,例：在上表所给出的(7, 3)循环码中，n = 7, k = 3, n k = 4。由此表可见，唯一的一个(n k) = 4次码多项式代表的码组是其次码组0010111，与它相对应的码多项式即生成多项式g(x) = x4 + x2 + x + 1。将此g(x)代入上式，得到,或,68,第11章过失掌握编码,由于上式不符合G = IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。,我们可以写出此循环码组，即,上式说明，全部码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。,69,第11章过失掌握编码,如何查找任一(n, k)循环码的生成多项式,由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故它可以写成,T(x) = h(x)g(x),而生成多项式g(x)本身也是一个码组，即有,T (x) = g(x),由于码组T (x)是一个(n k)次多项式，故xk T (x)是一个n次多项式。由下式,可知，xk T (x)在模(xn + 1)运算下也是一个码组，故可以写成,70,第11章过失掌握编码,上式左端分子和分母都是n次多项式，故商式Q(x) = 1。因此，上式可以化成,将T(x)和T(x)表示式代入上式，经过化简后得到,上式说明，生成多项式g(x)应当是(xn + 1)的一个因子。例如，(x7 + 1)可以分解为,为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一个(n k) = 4次的因子。不难看出，这样的因子有两个，即,71,第11章过失掌握编码,以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。,72,第11章过失掌握编码,11.6.2 循环码的编解码方法,循环码的编码方法,编码原则,在编码时，首先要依据给定的(n, k)值选定生成多项式g(x)，即从(xn + 1)的因子中选一个(n - k)次多项式作为g(x)。,由于全部码多项式T(x)都可以被g(x)整除。依据这条原则，就可以对给定的信息位进展编码：,设m(x)为信息码多项式，其次数小于k。用xn - k乘m(x)，得到的xn-k m(x)的次数必定小于n。用g(x)除xn - k m(x)，得到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n k)。将此余式r(x)加于信息位之后作为监视位，马上r(x)和xn - k m(x)相加，得到的多项式必定是一个码多项式。由于它必需能被g(x)整除，且商的次数不大于(k 1)。,73,第11章过失掌握编码,编码步骤：,用xn - k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它相当于m(x) = x2 + x。当n k = 7 3 = 4时，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相当于1100000。,用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即,例如，假设选定g(x) = x4 + x2 + x + 1，则,上式相当于,74,第11章过失掌握编码,编出的码组,T,(,x,)为,T,(,x,) =,x,n - k,m,(,x,) +,r,(,x,),在上例中，,T,(,x,) = 1100000 + 101 = 1100101，它就是上表中的第7码组。,75,第11章过失掌握编码,循环码的解码方法,解码要求：检错和纠错。,检错解码原理：由于任意一个码组多项式T(x)都应当能被生成多项式g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。当传输中未发生错误时，接收码组与发送码组一样，即R(x) = T(x)，故接收码组R(x)必定能被g(x)整除；假设码组在传输中发生错误，则R(x) T(x)，R(x)被g(x)除时可能除不尽而有余项，即有,因此，就以余项是否为零来判别接收码组中有无错码。,需要指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不行检错误。不行检错误中的误码数必定超过了这种编码的检错力量。,76,第11章过失掌握编码,纠错解码原理：为了能够纠错，要求每个可订正的错误图样必需与一个特定余式有一一对应关系。由于只有存在上述一一对应的关系时，才可能从上述余式唯一地打算错误图样，从而订正错码。因此，原则上纠错可按下述步骤进展：,用生成多项式g(x)除接收码组R(x)，得出余式r(x)。,按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。,从R(x)中减去E(x)，便得到已经订正错码的原发送码组T(x)。,通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。,目前多承受软件运算实现上述编解码运算。,77,第11章过失掌握编码,11.6.3 截短循环码,截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错力量都是预先给定的。但是，并不肯定有恰好满足这些条件的循环码存在。这时，可以承受将码长截短的方法，得出满足要求的编码。,截短方法：设给定一个(n, k)循环码，它共有2k种码组，现使其前i (0 i k)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这i位全“0”的信息位，最终得到一个(n i, k i)的线性码。将这种码称为截短循环码。,截短循环码性能：循环码截短前后至少具有一样的纠错力量，并且编解码方法仍和截短前的方法一样。,例：要求构造一个能够订正1位错码的(13, 9)码。这时可以由(15, 11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为(13, 9)截短循环码。,78,第11章过失掌握编码,11.6.4 BCH码,什么是BCH码？它是一种获得广泛应用的能够订正多个错码的循环码，是以3位制造这种码的人名(Bose - Chaudhuri - Hocguenghem)命名的。BCH码的重要性在于它解决了生成多项式与纠错力量的关系问题，可以在给定纠错力量要求的条件下查找到码的生成多项式。有了生成多项式，编码的根本问题就随之解决了。,BCH码分类：,本原BCH码：其生成多项式g(x)中含有最高次数为m的本原多项式，且码长为n = 2m 1，(m 3，为正整数)。,非本原BCH码：其生成多项式中不含这种本原多项式，且码长n是(2m 1)的一个因子，即码长n肯定除得尽2m 1。,79,第11章过失掌握编码,BCH码的性能：,码长n与监视位、纠错个数 t 之间的关系：,对于正整数m (m 3)和正整数t 1，且除得尽(2m -1)，则为非本原BCH码。,汉明码是能够订正单个随机错误的码。可以证明，具有循环性质的汉明码就是能订正单个随机错误的本原BCH码。,例如，(7, 4)汉明码就是以g1(x) = x3 + x + 1或g2(x) = x3 + x2 + 1生成的BCH码，而用g3(x) = x4 + x + 1或g4(x) = x4 + x3 + 1都能生成(15, 11)汉明码。,80,第11章过失掌握编码,BCH码的设计,在工程设计中，一般不需要用计算方法去查找生成多项式g(x)。由于前人早已将查找到的g(x)列成表，故可以用查表法找到所需的生成多项式。,下表给出了码长n 127的二进制本原BCH码生成多项式。,81,第11章过失掌握编码,n,= 3,k,t,g,(,x,),1 1 7,n,= 63,k,t,g,(,x,),57 1 103,51 2 12471,45 3 1701317,39 4 166623567,36 5 1033500423,30 6 157464165347,24 7 17323260404441,18 10 1363026512351725,16 11 6331141367235453,10 13 472622305527250155,7 15 5231045543503271737,1 31 全部为1,n,= 7,k,t,g,(,x,),4 1 13,1 3 77,n,= 15,k,t,g,(,x,),11 1 23,7 2 721,5 3 2467,1 7 77777,82,第11章过失掌握编码,n,= 31,k t,g,(,x,),26 1 45,21 2 3551,16 3 107657,11 5 5423325,6 7 313365047,1 15 17777777777,n,= 127,k,t,g,(,x,),120 1 211,113 2 41567,106 3 11554743,99 4 3447023271,92 5 624730022327,85 6 130704476322273,78 7 26230002166130115,71 9 6255010713253127753,64 10 1206534025570773100045,57 11 235265252505705053517721,50 13 54446512523314012421501421,43 15 17721772213651227521220574343,36,15,3146074666522075044764574721735,29 ,22,403114461367670603667530141176155,22 ,23,123376070404722522435445626637647043,15 ,27,22057042445604554770523013762217604353,8 ,31,7047264052751030651476224271567733130217,1 63 全部为1,83,第11章过失掌握编码,表中给出的生成多项式系数是用8进制数字列出的。例如，g(x) = (13)8是指g(x) = x3 + x + 1，由于(13)8 = (1011)2，后者就是此3次方程g(x)的各项系数。,下表列出了局部非本原BCH码的生成多项式参数。,n,k,t,g,(,x,),n,k,t,g,(,x,),17,21,23,33,41,9,12,12,22,21,2,2,3,2,4,727,1663,5343,5145,6647133,47,65,65,73,24,53,40,46,5,2,4,4,43073357,10761,354300067,1717773537,84,第11章过失掌握编码,戈莱码：,在上表中的(23, 12)码称为戈莱(Golay)码。它能订正3个随机错码，并且简洁解码，实际应用较多。,扩展BCH码：,BCH码的长度都为奇数。在应用中，为了得到偶数长度的码，并增大检错力量，可以在BCH码生成多项式中乘上一个因式(x + 1)，从而得到扩展BCH码(n + 1, k)。扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛有用的扩展戈莱码(24, 12)，其最小码距为8，码率为1/2，能够订正3个错码和检测4个错码。它比汉明码的纠错力量强很多，付出的代价是解码更简单，码率也比汉明码低。此外，它不再是循环码了。,85,第11章过失掌握编码,11.6.5 RS码：它是一类具有很强纠错力量的多进制BCH码。,假设仍用n表示RS码的码长，则对于m进制的RS码，其码长需要满足下式：n = m 1 = 2q 1,式中 q 2，为整数。,对于能够订正t个错误的RS码，其监视码元数目为r = 2t，这时的最小码距d0 = 2t + 1。,RS码的生成多项式为,g(x) = (x + )(x +2) (x +2t),式中， 伽罗华域GF(2q)中的本原元。,假设将每个m进制码元表示成相应的q位二进制码元，则得到的二进制码的参数为：,码长：n = q(2q 1)二进制码元,监视码：r = 2qt二进制码元,86,第11章过失掌握编码,由于RS码能够订正t个m进制错码，或者说，能够订正码组中t个不超过q位连续的二进制错码，所以RS码特殊适用于存在突发错误的信道，例如移动通信网等衰落信道中。此外，由于它是多进制纠错编码，所以特殊适合用于多进制调制的场合。,87,88,89,90,码树 code tree,网格图 trellis diagram,状态图 state diagram,维特比算法 the Viterbi algorithm,幸存路径surviving path,91,第11章过失掌握编码,11.7 卷积码,非分组码概念：,卷积码是一种非分组码。通常它更适用于前向纠错，由于对于很多实际状况它的性能优于分组码，而且运算较简洁。,卷积码在编码时虽然也是把k个比特的信息段编成n个比特的码组，但是监视码元不仅和当前的k比特信息段有关，而且还同前面m = (N 1)个信息段有关。所以一个码组中的监视码元监视着N个信息段。通常将N称为编码约束度，并将nN称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。码率则仍定义为k / n。,92,第11章过失掌握编码,11.7.1 卷积码的根本原理,编码器原理方框图,编码输出,每次输入,k,比特,1,k,1,k,1,k,1,k, ,1,k,2,k,3,k,Nk, , ,1,2,n,Nk,级,移存器,n,个模2,加法器,每输入,k,比特,旋转1周,93,第11章过失掌握编码,例： (,n,k,N,) = (3, 1, 3)卷积码编码器,方框图,编码器输出3比特,c,i,d,i,e,i,，输入和输出的关系如下：,b,i-2,b,i,输入,b,i,b,i-1,编码输出,d,i,c,i,e,i,M,2,M,3,M,1,94,c,i-2,d,i-,2,e,i,-2,c,i,-1,d,i,-1,e,i,-1,c,i,d,i,e,i,b,i-,2,b,i,1,b,i,t,t,输入,输出,第11章过失掌握编码,在以下图中用虚线示出了信息位bi的监视位和各信息位之间的约束关系。这里的编码约束长度nN等于9
展开阅读全文