《通信原理》第六版-第11章.ppt

,通信原理(第6版),单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,通信原理,1,.,通信原理,第,11,章差错控制编码,2,.,第,11,章差错控制编码,11.1,概述,信道分类：从差错控制角度看,随机信道：错码的出现是随机的,突发信道：错码是成串集中出现的,混合信道：既存在随机错码又存在突发错码,差错控制技术的种类,检错重发,前向纠错,反馈校验,检错删除,3,.,第,11,章差错控制编码,差错控制编码：常称为,纠错编码,监督码元：,上述,4,种技术中除第,3,种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。,不同的编码方法，有不同的,检错,或,纠错,能力。,多余度,：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为,1/3,。,编码效率,(,简称,码率,),：设编码序列中信息码元数量为,k,，总码元数量为,n,，则比值,k/n,就是码率。,冗余度：,监督码元数,(,n,-,k,),和信息码元数,k,之比。,理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,4,.,第,11,章差错控制编码,自动要求重发,(ARQ),系统,3,种,ARQ,系统,停止等待,ARQ,系统,数据按分组发送。每发送一组数据后发送端等待接收端的确认,(ACK),答复，然后再发送下一组数据。,图中的第,3,组接收数据有误，接收端发回一个否认,(NAK),答复。这时，发送端将重发第,3,组数据。,系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。,接收码组,ACK,ACK,NAK,ACK,ACK,NAK,ACK,t,1,2,3,3,4,5,5,发送码组,1,2,3,3,4,5,5,6,t,有错码组,有错码组,5,.,第,11,章差错控制编码,拉后,ARQ,系统,发送端连续发送数据组，接收端对于每个接收到的数据组都发回,确认,(,ACK,),或,否认,(,NAK,),答复。,例如，图中第,5,组接收数据有误，则在发送端收到第,5,组接收的否认答复后，从第,5,组开始重发数据组。,在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道,接收数据,有错码组,有错码组,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,重发码组,重发码组,6,.,第,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,7,.,第,11,章差错控制编码,ARQ,的主要优点：和前向纠错方法相比,监督码元较少即能使误码率降到很低，即码率较高；,检错的计算复杂度较低；,检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。,ARQ,的主要缺点：,需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。,因为重发而使,ARQ,系统的传输效率降低。,在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。,在要求实时通信的场合，例如电话通信，往往不允许使用,ARQ,法。,8,.,第,11,章差错控制编码,ARQ,系统的原理方框图,在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。,接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。,当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。,9,.,第,11,章差错控制编码,11.2,纠错编码的基本原理,分组码基本原理：举例说明如下。,设有一种由,3,位二进制数字构成的码组，它共有,8,种不同的可能组合。若将其全部用来表示天气，则可以表示,8,种不同天气，,例如：“,000”,（晴），“,001”,（云），,“,010”,（阴），“,011”,（雨），,“,100”,（雪），“,101”,（霜），,“,110”,（雾），“,111”,（雹）。,其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。,10,.,第,11,章差错控制编码,若在上述,8,种码组中只准许使用,4,种来传送天气，例如：,“,000”,晴 “,011”,云 “,101”,阴 “,110”,雨,这时，虽然只能传送,4,种不同的天气，但是接收端却有可能发现码组中的一个错码。,例如，若“,000”,（晴）中错了一位，则接收码组将变成“,100”,或“,010”,或“,001”,。这,3,种码组都是不准使用的，称为,禁用码组,。,接收端在收到禁用码组时，就认为发现了错码。当发生,3,个错码时，“,000”,变成了“,111”,，它也是禁用码组，故这种编码也能检测,3,个错码。,但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是,许用码组,。,11,.,第,11,章差错控制编码,检错和纠错,上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“,100”,时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“,100”,。,要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：“,000”,（晴），“,111”,（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。,例如，当收到禁用码组“,100”,时，若当作仅有一个错码，则可以判断此错码发生在“,1”,位，从而纠正为“,000”,（晴）。因为“,111”,（雨）发生任何一位错码时都不会变成“,100”,这种形式。,但是，这时若假定错码数不超过两个，则存在两种可能性：“,000”,错一位和“,111”,错两位都可能变成“,100”,，因而只能检测出存在错码而无法纠正错码。,12,.,第,11,章差错控制编码,分组码的结构,将信息码分组，为每组信息码附加若干监督码的编码称为,分组码,。,在分组码中，监督码元仅监督本码组中的信息码元。,信息位和监督位的关系：举例如下,信息位,监督位,晴,00,0,云,01,1,阴,10,1,雨,11,0,13,.,第,11,章差错控制编码,分组码的一般结构,分组码的符号：,(,n,k,),N,码组的总位数，又称为码组的长度（码长），,k,码组中信息码元的数目，,n,k,r,码组中的监督码元数目，或称监督位数目。,14,.,第,11,章差错控制编码,分组码的码重和码距,码重：把码组中“,1”,的个数目称为码组的重量，简称,码重,。,码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称,码距,。码距又称,汉明距离,。,例如，“,000”,晴，“,011”,云，“,101”,阴，“,110”,雨，,4,个码组之间，任意两个的距离均为,2,。,最小码距：把某种编码中各个码组之间距离的最小值称为,最小码距,(,d,0,),。例如，上面的编码的最小码距,d,0,=2,。,15,.,第,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,16,.,第,11,章差错控制编码,码距和检纠错能力的关系,一种编码的最小码距,d,0,的大小直接关系着这种编码的检错和纠错能力,为检测,e,个错码，要求最小码距,d,0,e,+1,【,证,】,设一个码组,A,位于,O,点。若码组,A,中发生一个错码，则我们可以认为,A,的位置将移动至以,O,点为圆心，以,1,为半径的圆上某点，但其位置不会超出此圆。,若码组,A,中发生两位错码，则其位置不会超出以,O,点为圆心，以,2,为半径的圆。因此，只要最小码距不小于,3,，码组,A,发生两位以下错码时，,不可能变成另一个准用,码组，因而能检测错码,的位数等于,2,。,0,1,2,3,B,A,汉明距离,e,d,0,17,.,第,11,章差错控制编码,同理，若一种编码的最小码距为,d,0,，则将能检测,(,d,0,-1),个错码。反之，若要求检测,e,个错码，则最小码距,d,0,至少应不小于,(,e,+1),。,为了纠正,t,个错码，要求最小码距,d,0,2,t,+1,【,证,】,图中画出码组,A,和,B,的距离为,5,。码组,A,或,B,若发生不多于两位错码，则其位置均不会超出半径为,2,以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以,A,为圆心的圆上就判决收到的是码组,A,，若落于以,B,为圆心的圆上就判决为码组,B,。,这样，就能够纠,正两位错码。,B,t,A,汉明距离,0,1,2,3,4,5,t,d,0,18,.,第,11,章差错控制编码,若这种编码中除码组,A,和,B,外，还有许多种不同码组，但任两码组之间的码距均不小于,5,，则以各码组的位置为中心以,2,为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距,d,0,5,时，能够纠正,2,个错码，且最多能纠正,2,个。若错码达到,3,个，就将落入另一圆上，从而发生错判。故一般说来，为纠正,t,个错码，最小码距应不小于,(2,t,+1),。,19,.,第,11,章差错控制编码,为纠正,t,个错码，同时检测,e,个错码，要求最小码距,在解释此式之前，先来分析下图所示的例子。图中码组,A,和,B,之间距离为,5,。按照检错能力公式，最多能检测,4,个错码，即,e,=,d,0,1=5 1=4,，按照纠错能力公式纠错时，能纠正,2,个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组,A,若错了,3,位，就会被误认为码组,B,错了,2,位造成的结果，从而被,错“纠”为,B,。这就,是说，检错和纠错,公式不能同时成立,或同时运用。,B,t,A,汉明距离,0,1,2,3,4,5,t,d,0,20,.,第,11,章差错控制编码,所以，为了在可以纠正,t,个错码的同时，能够检测,e,个错码，就需要像下图所示那样，使某一码组（譬如码组,A,）发生,e,个错误之后所处的位置，与其他码组（譬如码组,B,）的纠错圆圈至少距离等于,1,，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距,这种纠错和检错结合的工作方式简称,纠检结合,。,A,B,e,1,t,t,汉明距离,21,.,第,11,章差错控制编码,这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。,22,.,第,11,章差错控制编码,11.3,纠错编码的性能,系统带宽和信噪比的矛盾：,由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。,23,.,第,11,章差错控制编码,编码性能举例,未采用纠错编码时，,若接收信噪比等于,7dB,，编码前误码率,约为,8,10,-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),24,.,第,11,章差错控制编码,由图还可以看出，若,保持误码率在,10,-5,，,图中,C,点，未采用编,码时，约需要信噪比,E,b,/n,0,=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),25,.,第,11,章差错控制编码,传输速率和,E,b,/n,0,的关系,对于给定的传输系统,式中，,R,B,为码元速率。,若希望提高传输速率，,由上式看出势必使信,噪比下降，误码率增,大。假设系统原来工作,在图中,C,点，提高速率后,由,C,点升到,E,点。但加用,纠错编码后，仍可将误码,率降到,D,点。这时付出的,代价仍是带宽增大。,10,-6,10,-5,10,-4,10,-3,10,-2,10,-1,编码后,P,e,C,D,E,A,B,信噪比,(dB),26,.,第,11,章差错控制编码,11.4,简单的实用编码,11.4.1,奇偶监督码,奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有,1,位，它使码组中“,1”,的数目为偶数，即满足下式条件：,式中,a,0,为监督位，其他位为信息位。,这种编码能够检测奇数个错码。在接收端，按照上式求“模,2,和”，若计算结果为“,1”,就说明存在错码，结果为“,0”,就认为无错码。,奇数监督码与偶数监督码相似，只不过其码组中“,1”,的数目为奇数：,27,.,第,11,章差错控制编码,11.4.2,二维奇偶监督码（方阵码）,二维奇偶监督码的构成,它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示,图中,a,0,1,a,0,2,a,0,m,为,m,行奇偶监督码中的,m,个监督位。,c,n,-1,c,n,-2,c,1,c,0,为按列进行第二次编码所增加的监督位，它们构成了一监督位行。,28,.,第,11,章差错控制编码,二维奇偶监督码的性能,这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由,c,n,-1,c,n,-2,c,1,c,0,等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的,4,个错码，譬如图中,错了，就检测不出。,这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。,由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。,二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时。,29,.,第,11,章差错控制编码,11.4.3,恒比码,在恒比码中，每个码组均含有相同数目的“,1”,（和“,0”,）。由于“,1”,的数目与“,0”,的数目之比保持恒定，故得此名。,这种码在检测时，只要计算接收码组中“,1”,的数目是否对，就知道有无错码。,恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。,30,.,第,11,章差错控制编码,11.4.4,正反码,正反码的编码：,它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“,1”,的个数而定。,例如，若码长,n,=10,，其中信息位,k,=5,，监督位,r,=5,。其编码规则为：,当信息位中有奇数个“,1”,时，监督位是信息位的简单重复；,当信息位有偶数个“,1”,时，监督位是信息位的反码。,例如，若信息位为,11001,，则码组为,1100111001,；若信息位为,10001,，则码组为,1000101110,。,31,.,第,11,章差错控制编码,正反码的解码,在上例中，先将接收码组中信息位和监督位按模,2,相加，得到一个,5,位的合成码组。然后，由此合成码组产生一个校验码组。,若接收码组的信息位中有奇数个“,1”,，则合成码组就是校验码组；若接收码组的信息位中有偶数个“,1”,，则取合成码组的反码作为校验码组。,最后，观察校验码组中“,1”,的个数，按下表进行判决及纠正可能发现的错码。,32,.,第,11,章差错控制编码,校验码组和错码的关系,例如，若发送码组为,1100111001,，接收码组中无错码，则合成码组应为,11001,11001=00000,。由于接收码组信息位中有奇数个“,1”,，所以校验码组就是,00000,。按上表判决，结论是无错码。,校验码组的组成,错码情况,1,全为“,0”,无错码,2,有,4,个“,1”,和,1,个“,0”,信息码中有,1,位错码，其位置对应校验码组中“,0”,的位置,3,有,4,个“,0”,和,1,个“,1”,监督码中有,1,位错码，其位置对应校验码组中“,1”,的位置,4,其他组成,错码多于,1,个,33,.,第,11,章差错控制编码,若传输中产生了差错，使接收码组变成,1000111001,，则合成码组为,10001,11001,01000,。由于接收码组中信息位有偶数个“,1”,，所以校验码组应取合成码组的反码，即,10111,。由于其中有,4,个“,1”,和,1,个“,0”,，按上表判断信息位中左边第,2,位为错码。,若接收码组错成,1100101001,，则合成码组变成,11001,01001,10000,。由于接收码组中信息位有奇数个“,1”,，故校验码组就是,10000,，按上表判断，监督位中第,1,位为错码。,最后，若接收码组为,1001111001,，则合成码组为,10011,11001,01010,，校验码组与其相同，按上表判断，这时错码多于,1,个。,上述长度为,10,的正反码具有纠正,1,位错码的能力，并能检测全部,2,位以下的错码和大部分,2,位以上的错码。,34,.,第,11,章差错控制编码,11.5,线性分组码,基本概念,代数码,：,建立在代数学基础上的编码。,线性码,：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。,线性分组码,：按照一组线性方程构成的分组码。,本节将以汉明码为例引入线性分组码的一般原理。,35,.,第,11,章差错控制编码,汉明码,能够纠正,1,位错码且编码效率较高的一种线性分组码,汉明码的构造原理。,在偶数监督码中，由于使用了一位监督位,a,0,，它和信息位,a,n-1,a,1,一起构成一个代数式：,在接收端解码时，实际上就是在计算,若,S,=0,，就认为无错码；若,S,=1,，就认为有错码。现将上式称为,监督关系式,，,S,称为,校正子,。由于校正子,S,只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。,36,.,第,11,章差错控制编码,若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有,4,中组合：,00,，,01,，,10,，,11,，故能表示,4,种不同的信息。若用其中,1,种组合表示无错，则其余,3,种组合就有可能用来指示一个错码的,3,种不同位置。同理，,r,个监督关系式能指示,1,位错码的,(2,r,1),个可能位置。,一般来说，若码长为,n,，信息位数为,k,，则监督位数,r,n,k,。如果希望用,r,个监督位构造出,r,个监督关系式来指示,1,位错码的,n,种可能位置，则要求,下面通过一个例子来说明如何具体构造这些监督关系式。,37,.,第,11,章差错控制编码,例：设,分组码,(,n,k,),中,k,=4,，为了纠正,1,位错码，由上式可知，要求监督位数,r,3,。若取,r,=3,，则,n,=,k,+,r,=7,。我们用,a,6,a,5,a,0,表示这,7,个码元，用,S,1,、,S,2,和,S,3,表示,3,个监督关系式中的校正子，则,S,1,、,S,2,和,S,3,的值与错码位置的对应关系可以规定如下表所列：,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,无错码,38,.,第,11,章差错控制编码,由表中规定可见，仅当一位错码的位置在,a,2,、,a,4,、,a,5,或,a,6,时，校正子,S,1,为,1,；否则,S,1,为零。这就意味着,a,2,、,a,4,、,a,5,和,a,6,四个码元构成偶数监督关系：,同理，,a,1,、,a,3,、,a,5,和,a,6,构成偶数监督关系：,以及,a,0,、,a,3,、,a,4,和,a,6,构成偶数监督关系,39,.,第,11,章差错控制编码,在发送端编码时，信息位,a,6,、,a,5,、,a,4,和,a,3,的值决定于输入信号，因此它们是随机的。监督位,a,2,、,a,1,和,a,0,应根据信息位的取值按监督关系来确定，即监督位应使上,3,式中,S,1,、,S,2,和,S,3,的值为,0,（表示编成的码组中应无错码）：,上式经过移项运算，解出监督位,给定信息位后，可以直接按上式算出监督位，结果见下表：,40,.,第,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,41,.,第,11,章差错控制编码,接收端收到每个码组后，先计算出,S,1,、,S,2,和,S,3,，再查表判断错码情况。例如，若接收码组为,0000011,，按上述公式计算可得：,S,1,=0,，,S,2,=1,，,S,3,=1,。由于,S,1,S,2,S,3,等于,011,，故查表可知在,a,3,位有,1,错码。,按照上述方法构造的码称为汉明码。表中所列的,(7,4),汉明码的最小码距,d,0,=3,。因此，这种码能够纠正,1,个错码或检测,2,个错码。由于码率,k,/,n,=(,n,-,r,)/,n,=1,r,/,n,，故当,n,很大和,r,很小时，码率接近,1,。可见，汉明码是一种高效码。,42,.,第,11,章差错控制编码,线性分组码的一般原理,线性分组码的构造,H,矩阵,上面,(7,4),汉明码的例子有,现在将上面它改写为,上式中已经将“,”简写成“,+”,。,43,.,第,11,章差错控制编码,上式可以表示成如下矩阵形式：,上式还可以简记为,H,A,T,=,0,T,或,A,H,T,=,0,44,.,第,11,章差错控制编码,H,A,T,=,0,T,或,A,H,T,=,0,式中,A,=,a,6,a,5,a,4,a,3,a,2,a,1,a,0,0,=000,右上标“,T”,表示将矩阵转置。例如，,H,T,是,H,的转置，即,H,T,的第一行为,H,的第一列，,H,T,的第二行为,H,的第二列等等。,将,H,称为,监督矩阵,。,只要监督矩阵,H,给定，编码时监督位和信息位的关系就完全确定了。,45,.,第,11,章差错控制编码,H,矩阵的性质：,1),H,的行数就是监督关系式的数目，它等于监督位的数目,r,。,H,的每行中“,1”,的位置表示相应码元之间存在的监督关系。例如，,H,的第一行,1110100,表示监督位,a,2,是由,a,6,a,5,a,4,之和决定的。,H,矩阵可以分成两部分，例如,式中，,P,为,r,k,阶矩阵，,I,r,为,r,r,阶单位方阵。我们将具有,P I,r,形式的,H,矩阵称为,典型阵,。,46,.,第,11,章差错控制编码,2),由代数理论可知，,H,矩阵的各行应该是线性无关的，否则将得不到,r,个线性无关的监督关系式，从而也得不到,r,个独立的监督位。若一矩阵能写成典型阵形式,P I,r,，则其各行一定是线性无关的。因为容易验证,I,r,的各行是线性无关的，故,P I,r,的各行也是线性无关的。,G,矩阵：上面汉明码例子中的监督位公式为,也可以改写成矩阵形式：,47,.,第,11,章差错控制编码,或者写成,式中，,Q,为一个,k,r,阶矩阵，它为,P,的转置，即,Q,=,P,T,上式表示，在信息位给定后，用信息位的行矩阵乘矩阵,Q,就产生出监督位。,48,.,第,11,章差错控制编码,我们将,Q,的左边加上,1,个,k,k,阶单位方阵，就构成,1,个矩阵,G,G,称为,生成矩阵,，因为由它可以产生整个码组，即有,或者,因此，如果找到了码的生成矩阵,G,，则编码的方法就完全确定了。具有,I,k,Q,形式的生成矩阵称为,典型生成矩阵,。由典型生成矩阵得出的码组,A,中，信息位的位置不变，监督位附加于其后。这种形式的码称为,系统码,。,49,.,第,11,章差错控制编码,G,矩阵的性质：,1),G,矩阵的各行是线性无关的。因为由上式可以看出，任一码组,A,都是,G,的各行的线性组合。,G,共有,k,行，若它们线性无关，则可以组合出,2,k,种不同的码组,A,，它恰是有,k,位信息位的全部码组。若,G,的各行有线性相关的，则不可能由,G,生成,2,k,种不同的码组了。,2),实际上，,G,的各行本身就是一个码组。因此，如果已有,k,个线性无关的码组，则可以用其作为生成矩阵,G,，并由它生成其余码组。,50,.,第,11,章差错控制编码,错码矩阵和错误图样,一般说来，,A,为一个,n,列的行矩阵。此矩阵的,n,个元素就是码组中的,n,个码元，所以发送的码组就是,A,。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与,A,不一定相同。,若设接收码组为一,n,列的行矩阵,B,，即,则发送码组和接收码组之差为,B,A,=,E,(,模,2),它就是传输中产生的,错码,行,矩阵,式中,51,.,第,11,章差错控制编码,因此，若,e,i,=0,，表示该接收码元无错；若,e,i,=1,，则表示该接收码元有错。,B,A,=,E,可以改写成,B,=,A,+,E,例如，若发送码组,A,=1000111,，错码矩阵,E,=0000100,，则接收码组,B,=1000011,。,错码矩阵有时也称为,错误图样,。,52,.,第,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,H,T,=,0,，所以,S,=,E,H,T,式中,S,称为校正子。它能用来指示错码的位置。,S,和错码,E,之间有确定的线性变换关系。若,S,和,E,之间一一对应，则,S,将能代表错码的位置。,53,.,第,11,章差错控制编码,线性分组码的性质,封闭性：,是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。,这就是说，若,A,1,和,A,2,是一种线性码中的两个许用码组，则,(,A,1,+,A,2,),仍为其中的一个码组。这一性质的证明很简单。若,A,1,和,A,2,是两个码组，则有,A,1,H,T,=0,A,2,H,T,=0,将上两式相加，得出,A,1,H,T,+,A,2,H,T,=(,A,1,+,A,2,),H,T,=0,所以,(,A,1,+,A,2,),也是一个码组。,由于线性码具有封闭性，所以两个码组,(,A,1,和,A,2,),之间的距离（即对应位不同的数目）必定是另一个码组,(,A,1,+,A,2,),的重量（即“,1”,的数目）。因此，码的最小距离就是码的最小重量（除全“,0”,码组外）。,54,.,第,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,55,.,第,11,章差错控制编码,一般说来，若,(,a,n,-1,a,n,-2,a,0,),是循环码的一个码组，则循环移位后的码组,(,a,n,-2,a,n,-3,a,0,a,n,-1,),(,a,n,-3,a,n,-4,a,n,-1,a,n,-2,),(,a,0,a,n,-1,a,2,a,1,),也是该编码中的码组。,56,.,第,11,章差错控制编码,码多项式,码组的多项式表示法,把码组中各码元当作是一个多项式的系数，即把一个长度为,n,的码组表示成,例如，上表中的任意一个码组可以表示为,其中第,7,个码组可以表示为,这种多项式中，,x,仅是码元位置的标记，例如上式表示第,7,码组中,a,6,、,a,5,、,a,2,和,a,0,为“,1”,，其他均为,0,。因此我们并不关心,x,的取值。,57,.,第,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,除得的余数。,58,.,第,11,章差错控制编码,在码多项式运算中也有类似的按模运算。,若一任意多项式,F,(,x,),被一,n,次多项式,N,(,x,),除，得到商式,Q,(,x,),和一个次数小于,n,的余式,R,(,x,),，即,则写为,这时，码多项式系数仍按模,2,运算，即系数只取,0,和,1,。例如，,x,3,被,(,x,3,+1),除，得到余项,1,。所以有,同理,因为,x,x,3,+1,x,4,+,x,2,+1,x,4,+,x,x,2,+,x,+1,应当注意，由于在模,2,运算中，用加法代替了减法，故余项不是,x,2,x,+1,，而是,x,2,+,x,+1,。,59,.,第,11,章差错控制编码,循环码的码多项式,在循环码中，若,T(,x,),是一个长为,n,的许用码组，则,x,i,T(,x,),在按模,x,n,+1,运算下，也是该编码中的一个许用码组，即若,则,T,(,x,),也是该编码中的一个许用码组。,【,证,】,因为若,则,（模,(,x,n,+1),）,所以，这时有,60,.,第,11,章差错控制编码,上式中,T,(,x,),正是,T,(,x,),代表的码组向左循环移位,i,次的结果。因为原已假定,T,(,x,),是循环码的一个码组，所以,T,(,x,),也必为该码中一个码组。例如，循环码组,其码长,n,=7,。现给定,i,=3,，则,其对应的码组为,0101110,，它正是表中第,3,码组。,由上述分析可见，一个长为,n,的循环码必定为按模,(,x,n,+1),运算的一个余式。,61,.,第,11,章差错控制编码,循环码的生成矩阵,G,由上节中公式,可知，有了生成矩阵,G,，就可以由,k,个信息位得出整个码组，而且生成矩阵,G,的每一行都是一个码组。例如，在此式中，若,a,6,a,5,a,4,a,3,=1000,，则码组,A,就等于,G,的第一行；若,a,6,a,5,a,4,a,3,=0100,，则码组,A,就等于,G,的第二行；等等。由于,G,是,k,行,n,列的矩阵，因此若能找到,k,个已知码组，就能构成矩阵,G,。如前所述，这,k,个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。,在循环码中，一个,(,n,k,),码有,2,k,个不同的码组。若用,g,(,x,),表示其中前,(,k,-1),位皆为“,0”,的码组，则,g,(,x,),，,x g,(,x,),，,x,2,g,(,x,),，,，,x,k-1,g,(,x,),都是码组，而且这,k,个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵,G,。,62,.,第,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,),循环码就被确定了。,63,.,第,11,章差错控制编码,因此，循环码的生成矩阵,G,可以写成,例：在上表所给出的,(7,3),循环码中，,n,=7,k,=3,n,k,=4,。由此表可见，唯一的一个,(,n,k,)=4,次码多项式代表的码组是第二码组,0010111,，与它相对应的码多项式（即生成多项式）,g,(,x,)=,x,4,+,x,2,+,x,+1,。将此,g,(,x,),代入上式，得到,或,64,.,第,11,章差错控制编码,由于上式不符合,G,=,I,k,Q,的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。,我们可以写出此循环码组，即,上式表明，所有码多项式,T,(,x,),都可被,g,(,x,),整除，而且任意一个次数不大于,(,k,1),的多项式乘,g,(,x,),都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是,T,(,x,),。为了简洁，式中直接将乘积写为此元素。,65,.,第,11,章差错控制编码,如何寻找任