第11章-差错控制编码-通信原理-樊昌信优秀PPT.ppt

《第11章-差错控制编码-通信原理-樊昌信优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第11章-差错控制编码-通信原理-樊昌信优秀PPT.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通信原理第第11章差错限制编码章差错限制编码 1数字通信系统信源译码信源信源编码加密信道调制信道编码解调解密信道译码信宿数字频带传输系统数字基带传输系统Ch9Ch9Ch11Ch11Ch7、Ch10Ch6、Ch11、数字传输系统模数变换数模变换数字基带处理数字基带处理2Ch 13 同步2第第11章差错限制编码章差错限制编码l11.1 概述概述l信道分类：从差错限制角度看信道分类：从差错限制角度看l随机信道：错码的出现是随机的随机信道：错码的出现是随机的 l突发信道：错码是成串集中出现的突发信道：错码是成串集中出现的l混合信道：既存在随机错码又存在突发错码混合信道：既存在随机错码又存在突发错码 l

2、差错限制技术的种类差错限制技术的种类l 检错重发检错重发(ARQ)接收端在收到的信码中检测接收端在收到的信码中检测出出(发觉发觉)错码时，马上设法通知发送端重发，直错码时，马上设法通知发送端重发，直到正确收到为止。到正确收到为止。l前向纠错前向纠错(FEC)接收端不仅能发觉错码，还接收端不仅能发觉错码，还能够确定错码的位置，能够订正它。能够确定错码的位置，能够订正它。l反馈校验反馈校验(FC)接收端收到信码原封不动地发接收端收到信码原封不动地发回发送端，与原发信码比较，发觉错误，重发知回发送端，与原发信码比较，发觉错误，重发知道正确。道正确。l检错删除检错删除(DEL)接收端在收到的信码中发觉

3、接收端在收到的信码中发觉错码时，马上将其删除，该法只适用于少数有大错码时，马上将其删除，该法只适用于少数有大量多余数据的状况。量多余数据的状况。3第第11章差错限制编码章差错限制编码n差错限制编码：常称为纠错编码差错限制编码：常称为纠错编码n监督码元：上述监督码元：上述4种技术中除第种技术中除第3种外，都是在种外，都是在接收端识别有无错码。所以在发送端须要在信接收端识别有无错码。所以在发送端须要在信息码元序列中增加一些差错限制码元，它们称息码元序列中增加一些差错限制码元，它们称为监督码元。为监督码元。n不同的编码方法，有不同的检错或纠错实力。不同的编码方法，有不同的检错或纠错实力。n多余度：就

4、是指增加的监督码元多少。例如，多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为监督码元，则这种编码的多余度为1/3。n编码效率编码效率(简称码率简称码率)：设编码序列中信息码元：设编码序列中信息码元数量为数量为k，总码元数量为，总码元数量为n，则比值，则比值k/n 就是码就是码率。率。n冗余度：监督码元数冗余度：监督码元数(n-k)和信息码元数和信息码元数 k 之比。之比。n理论上，差错限制以降低信息传输速率为代价理论上，差错限制以降低信息传输速率为代价换取提高传输牢靠性。换取提高传输牢靠性。

5、4第第11章差错限制编码章差错限制编码n自动要求重发自动要求重发(ARQ)系统系统u3种种ARQ系统系统p停止等待停止等待ARQ系统系统 数据按分组发送。每发送一组数据后发送端等待接数据按分组发送。每发送一组数据后发送端等待接收端的确认收端的确认(ACK)答复，然后再发送下一组数据。答复，然后再发送下一组数据。图中的第图中的第3组接收数据有误，接收端发回一个否认组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第答复。这时，发送端将重发第3组数据。组数据。系统是工作在半双工状态，时间没有得到充分利用，系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。传输效率较低。接

6、收码组接收码组ACKACKNAKACKACKNAKACKt1233455发送码组发送码组12334556t有错码组有错码组有错码组有错码组5第第11章差错限制编码章差错限制编码p拉后拉后ARQ系统系统p发送端连续发送数据组，接收端对于每个接收到的数据组发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认都发回确认(ACK)或否认或否认(NAK)答复。答复。p例如，图中第例如，图中第5组接收数据有误，则在发送端收到第组接收数据有误，则在发送端收到第5组接组接收的否认答复后，从第收的否认答复后，从第5组起先重发数据组。组起先重发数据组。p在这种系统中须要对发送的数据组和答复进行编号，以便在

7、这种系统中须要对发送的数据组和答复进行编号，以便识别。明显，这种系统须要双工信道识别。明显，这种系统须要双工信道 接收数据接收数据有错码组有错码组有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据发送数据576952143679810 1110 11 12重发码组重发码组重发码组重发码组6第第11章差错限制编码章差错限制编码p选择重发选择重发ARQ系统系统它只重发出错的数据组，因此进一步提高了传输效率。它只重发出错的数据组，因此进一步提高了传输效率。接收数据接收数据有错码组有错码组有错码组有错码组9214365759810 1113141

8、2发送数据发送数据995852143671011131412重发码组重发码组重发码组重发码组NAK9ACK1NAK5ACK5ACK97第第11章差错限制编码章差错限制编码uARQ的主要优点：和前向纠错方法相比的主要优点：和前向纠错方法相比u监督码元较少，能使误码率降到很低，即码率较高；监督码元较少，能使误码率降到很低，即码率较高；u检错的计算困难度较低；检错的计算困难度较低；u检错用的编码方法和加性干扰的统计特性基本无关，检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。能适应不同特性的信道。uARQ的主要缺点：的主要缺点：u须要双向信道来重发，不能用于单向信道，也不能须要双

9、向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。用于一点到多点的通信系统。u因为重发而使因为重发而使ARQ系统的传输效率降低。系统的传输效率降低。u在信道干扰严峻时，可能发生因不断反复重发而造在信道干扰严峻时，可能发生因不断反复重发而造成事实上的通信中断。成事实上的通信中断。u在要求实时通信的场合，例如电话通信，往往不允在要求实时通信的场合，例如电话通信，往往不允许运用许运用ARQ法。法。8第第11章差错限制编码章差错限制编码uARQ系统的原理方框图系统的原理方框图u在发送端，输入的信息码元在编码器中被分组编码（加在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，

10、除了马上发送外，还暂存于缓冲存储入监督码元）后，除了马上发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器限制产生器中。若接收端解码器检出错码，则由解码器限制产生一个重发指令。此指令经过反向信道送到发送端。由发一个重发指令。此指令经过反向信道送到发送端。由发送端重发限制器限制缓冲存储器重发一次。送端重发限制器限制缓冲存储器重发一次。u接收端仅当解码器认为接收信息码元正确时，才将信息接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码码元送给收信者，否则在输出缓冲存储器中删除接收码元。元。u当解码器未发觉错码时，经过反向信道发出不需重发指

11、当解码器未发觉错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即接着发送后一码组，发送令。发送端收到此指令后，即接着发送后一码组，发送端的缓冲存储器中的内容也随之更新。端的缓冲存储器中的内容也随之更新。9第第11章差错限制编码章差错限制编码l11.2 纠错编码的基本原理纠错编码的基本原理l分组码基本原理：举例说明如下。分组码基本原理：举例说明如下。l设有一种由设有一种由3位二进制数字构成的码组，它位二进制数字构成的码组，它共有共有8种不同的可能组合。若将其全部用来种不同的可能组合。若将其全部用来表示天气，则可以表示表示天气，则可以表示8种不同天气，种不同天气，l 例如：例如：“000

12、”（晴），（晴），“001”（云），（云），l “010”（阴），（阴），“011”（雨）（雨），l “100”（雪），（雪），“101”（霜）（霜），l “110”（雾），（雾），“111”（雹）。（雹）。l其中任一码组在传输中若发生一个或多个错其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收码，则将变成另一个信息码组。这时，接收端将无法发觉错误。端将无法发觉错误。10第第11章差错限制编码章差错限制编码u若在上述若在上述8种码组中只准许运用种码组中只准许运用4种来传送天气，例如：种来传送天气，例如：u“000”晴晴 “011”云云 “101”阴阴 “110”雨雨

13、u这时，虽然只能传送这时，虽然只能传送4种不同的天气，但是接收端却有可种不同的天气，但是接收端却有可能发觉码组中的一个错码。能发觉码组中的一个错码。u例如，若例如，若“000”（晴）中错了一位，则接收码组将变成（晴）中错了一位，则接收码组将变成“100”或或“010”或或“001”。这。这3种码组都是不准运用种码组都是不准运用的，称为禁用码组。的，称为禁用码组。u接收端在收到禁用码组时，就认为发觉了错码。当发生接收端在收到禁用码组时，就认为发觉了错码。当发生3个错码时，个错码时，“000”变成了变成了“111”，它也是禁用码组，它也是禁用码组，故这种编码也能检测故这种编码也能检测3个错码。个错

14、码。u但是这种码不能发觉一个码组中的两个错码，因为发生但是这种码不能发觉一个码组中的两个错码，因为发生两个错码后产生的是许用码组。两个错码后产生的是许用码组。11第第11章差错限制编码章差错限制编码u检错和纠错检错和纠错u上面这种编码只能检测错码，不能订正错码。例如，当上面这种编码只能检测错码，不能订正错码。例如，当接收码组为禁用码组接收码组为禁用码组“100”时，接收端将无法推断是哪时，接收端将无法推断是哪一位码发生了错误，因为晴一位码发生了错误，因为晴000、阴、阴101、雨、雨110三者错三者错了一位都可以变成了一位都可以变成“100”。u要能够订正错误，还要增加多余度。例如，若规定许用

15、要能够订正错误，还要增加多余度。例如，若规定许用码组只有两个：码组只有两个：“000”（晴），（晴），“111”（雨），其他（雨），其他都是禁用码组，则能够检测两个以下错码，或能够订正都是禁用码组，则能够检测两个以下错码，或能够订正一个错码。一个错码。u例如，当收到禁用码组例如，当收到禁用码组“100”时，若当作仅有一个错码，时，若当作仅有一个错码，则可以推断此错码发生在则可以推断此错码发生在“1”位，从而订正为位，从而订正为“000”（晴）。因为（晴）。因为“111”（雨）发生任何一位错码（雨）发生任何一位错码时都不会变成时都不会变成“100”这种形式。这种形式。u但是，这时若假定错码数不超

16、过两个，则存在两种可能但是，这时若假定错码数不超过两个，则存在两种可能性：性：“000”错一位和错一位和“111”错两位都可能变成错两位都可能变成“100”，因而只能检测出存在错码而无法订正错码。，因而只能检测出存在错码而无法订正错码。12第第11章差错限制编码章差错限制编码u分组码的结构分组码的结构p将信息码分组，为每组信息码附加若干监督码的编码称将信息码分组，为每组信息码附加若干监督码的编码称为为分组码分组码。p在分组码中，监督码元仅监督本码组中的信息码元。在分组码中，监督码元仅监督本码组中的信息码元。p信息位和监督位的关系：举例如下信息位和监督位的关系：举例如下13第第11章差错限制编码

17、章差错限制编码p分组码的一般结构分组码的一般结构u分组码的符号：分组码的符号：(n,k)pN 码组的总位数，又称为码组的长度（码长），码组的总位数，又称为码组的长度（码长），pk 码组中信息码元的数目，码组中信息码元的数目，pn k r 码组中的监督码元数目，或称监督位数目。码组中的监督码元数目，或称监督位数目。14第11章差错限制编码u分组码的码重和码距分组码的码重和码距u码重：把码组中码重：把码组中“1”的个数目称为码组的重量，简称码的个数目称为码组的重量，简称码重。重。u码距：把两个码组中对应位上数字不同的位数称为码组码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距

18、又称汉明距离。的距离，简称码距。码距又称汉明距离。u例如，例如，“000”晴，晴，“011”云，云，“101”阴，阴，“110”雨，雨，4个码组之间，随意两个的距离均为个码组之间，随意两个的距离均为2。u最小码距：把某种编码中各个码组之间距离的最小值称最小码距：把某种编码中各个码组之间距离的最小值称为最小码距为最小码距(d0)。例如，上面的编码的最小码距。例如，上面的编码的最小码距d0=2。15第11章差错限制编码u码距的几何意义码距的几何意义p对于对于3位的编码组，可以在位的编码组，可以在3维空间中说明码距的几何意义。维空间中说明码距的几何意义。p每个码组的每个码组的3个码元的值个码元的值(

19、a1,a2,a3)就是此立方体各顶点的就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。体各边行走的几何距离。p由此图可以直观看出，上例中由此图可以直观看出，上例中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)a2a0a116第11章差错限制编码u码距和检纠错实力的关系码距和检纠错实力的关系u一种编码的最小码距一种编码的最小码距d0的大小干脆关系着这种编码的检的大小干脆关系着这种编

20、码的检错和纠错实力错和纠错实力u为检测为检测e个错码，要求最小码距个错码，要求最小码距 d0 e+1u【证】设一个码组【证】设一个码组A位于位于O点。若码组点。若码组A中发生一个中发生一个错码，则我们可以认为错码，则我们可以认为A的位置将移动至以的位置将移动至以O点为圆心，点为圆心，以以1为半径的圆上某点，但其位置不会超出此圆。为半径的圆上某点，但其位置不会超出此圆。u若码组若码组A中发生两位错码，则其位置不会超出以中发生两位错码，则其位置不会超出以O点为圆心，以点为圆心，以2为半径的圆。因此，只要最小码距不小于为半径的圆。因此，只要最小码距不小于3，码组，码组A发生两位以下错码时，发生两位以

21、下错码时，u不行能变成另一个准用不行能变成另一个准用u码组，因而能检测错码码组，因而能检测错码u的位数等于的位数等于2。0123BA汉明距离ed017第11章差错限制编码即：若一种编码的最小码距为d0，则能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0必大于等于(e+1)。为了订正t个错码，要求最小码距d0 2t+1【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。B

22、tA汉明距离012345td018第11章差错限制编码若这种编码中除码组A和B外，还有很多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会相互重叠。这样，每种码组假如发生不超过两位错码都将能被订正。因此，当最小码距d05时，能够订正2个错码，且最多能订正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为订正t个错码，最小码距应不小于(2t+1)。19第11章差错限制编码p为订正为订正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距p在说明此式之前，先来分析下图所示的例子。图中码组在说明此式之前，先来分析下图

23、所示的例子。图中码组A和和B之间距离为之间距离为5。依据检错实力公式，最多能检测。依据检错实力公式，最多能检测4个错码，个错码，即即e=d0 1=5 1=4，依据纠错实力公式纠错时，能订正，依据纠错实力公式纠错时，能订正2个错码。但是，不能同时作到两者，因为当错码位数超过纠个错码。但是，不能同时作到两者，因为当错码位数超过纠错实力时，该码组马上进入另一码组的圆内而被错误地错实力时，该码组马上进入另一码组的圆内而被错误地“订订正正”了。例如，码组了。例如，码组A若错了若错了3位，就会被误认为码组位，就会被误认为码组B错了错了2位造成的结果，从而被位造成的结果，从而被p错错“纠纠”为为B。这就。这

24、就p是说，检错和纠错是说，检错和纠错p公式不能同时成立公式不能同时成立p或同时运用。或同时运用。BtA汉明距离012345td020第11章差错限制编码所以，为了在可以订正t个错码的同时，能够检测e个错码，就须要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“订正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离21第11章差错限制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节约重发时间，提高

25、传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的状况。22第11章差错限制编码l11.3 纠错编码的性能纠错编码的性能l系统带宽和信噪比的冲突：系统带宽和信噪比的冲突：l由上节所述的纠错编码原理可知，为了削减由上节所述的纠错编码原理可知，为了削减接收错误码元数量，须要在发送信息码元序接收错误码元数量，须要在发送信息码元序列中加入监督码元。这样作的结果使发送序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必需增大，因而码

26、元速率不变，则传输速率必需增大，因而增大了系统带宽。系统带宽的增大将引起系增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码的下降反而又使系统接收码元序列中的错码增多。一般说来，接受纠错编码后，误码率增多。一般说来，接受纠错编码后，误码率总是能够得到很大改善的。改善的程度和所总是能够得到很大改善的。改善的程度和所用的编码有关。用的编码有关。23第11章差错限制编码u编码性能举例编码性能举例u未接受纠错编码时，未接受纠错编码时，u若接收信噪比等于若接收信噪比等于u7dB，编码前误码率，编码前误码

27、率u约为约为8 10-4，图中，图中Au点，在接受纠错编码点，在接受纠错编码u后，误码率降至约后，误码率降至约4u 10-5，图中，图中B点。这样，点。这样，u不增大发送功率不增大发送功率就能就能u降低误码率约一个半降低误码率约一个半u数量级。数量级。10-610-510-410-310-210-1编码后PeCDEAB信 噪 比 (dB)24第第11章差错限制编码章差错限制编码p由图还可以看出，若由图还可以看出，若p保持误码率在保持误码率在10-5，p图中图中C点，未接受编点，未接受编p码时，约须要信噪比码时，约须要信噪比pEb/n0=9.5 dB。在。在p接受这种编码时，约接受这种编码时，约

28、p须要信噪比须要信噪比7.5 dB，图，图p中中D点。可以节约功率点。可以节约功率p2 dB。通常称这。通常称这2 dB为为p编码增益。编码增益。p上面两种状况付出的代上面两种状况付出的代p价是带宽增大。价是带宽增大。10-610-510-410-310-210-1编码后编码后Pe CDE A B信信 噪噪 比比 (dB)25第第11章差错限制编码章差错限制编码p传输速率和传输速率和Eb/n0的关系的关系对于给定的传输系统对于给定的传输系统式中，式中，RB为码元速率。为码元速率。若希望提高传输速率，若希望提高传输速率，由上式看出势必使信由上式看出势必使信噪比下降，误码率增噪比下降，误码率增大。

29、假设系统原来工作大。假设系统原来工作在图中在图中C点，提高速率后点，提高速率后由由C点升到点升到E点。但加用点。但加用纠错编码后，仍可将误码纠错编码后，仍可将误码率降到率降到D点。这时付出的点。这时付出的代价仍是带宽增大。代价仍是带宽增大。26第11章差错限制编码l11.4简洁的好用编码简洁的好用编码l11.4.1 奇偶监督码奇偶监督码l奇偶监督码分为奇数监督码和偶数监督码两奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有论信息位多少，监督位只有1位，它使码组位，它使码组中中“1”的数目为偶数，即满足下式

30、条件：的数目为偶数，即满足下式条件：l式中式中a0为监督位，其他位为信息位。为监督位，其他位为信息位。l这种编码能够检测奇数个错码。在接收这种编码能够检测奇数个错码。在接收端，依据上式求端，依据上式求“模模2和和”，若计算结果为，若计算结果为“1”就说明存在错码，结果为就说明存在错码，结果为“0”就认为就认为无错码。无错码。l奇数监督码与偶数监督码相像，只不过奇数监督码与偶数监督码相像，只不过其码组中其码组中“1”的数目为奇数：的数目为奇数：27第11章差错限制编码n11.4.2 二维奇偶监督码（方阵码）n二维奇偶监督码的构成n它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再

31、按列的方向增加其次维监督位，如下图所示n图中a01 a02 a0m为m行奇偶监督码中的m个监督位。ncn-1 cn-2 c1 c0为按列进行其次次编码所增加的监督位，它们构成了一监督位行。28第第11章差错限制编码章差错限制编码u二维奇偶监督码的性能二维奇偶监督码的性能u这种编码有可能检测偶数个错码。因为每行的监督位虽这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有然不能用于检测本行中的偶数个错码，但按列的方向有可能由可能由cn-1 cn-2 c1 c0等监督位检测出来。有一些偶等监督位检测出来。有一些偶数错码不行能检测出来。例如，构成矩形的数错

32、码不行能检测出来。例如，构成矩形的4个错码，譬个错码，譬如图中如图中u错了，就检测不出。错了，就检测不出。u这种二维奇偶监督码适于检测突发错码。因为突发错码这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。常常成串出现，随后有较长一段无错区间。u由于方阵码只对构成矩形四角的错码无法检测，故其检由于方阵码只对构成矩形四角的错码无法检测，故其检错实力较强。错实力较强。u二维奇偶监督码不仅可用来检错，还可以用来订正一些二维奇偶监督码不仅可用来检错，还可以用来订正一些错码。错码。例如，仅在一行中有奇数个错码时。例如，仅在一行中有奇数个错码时。29第第11章差错限制编

33、码章差错限制编码n 11.4.3 恒比码恒比码n在恒比码中，每个码组均含有相同数目的在恒比码中，每个码组均含有相同数目的“1”（和（和“0”）。由于）。由于“1”的数目与的数目与“0”的数目之的数目之比保持恒定，故得此名。比保持恒定，故得此名。n这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1”的数的数目是否对，就知道有无错码。目是否对，就知道有无错码。n恒比码的主要优点是简洁和适于用来传输电传机恒比码的主要优点是简洁和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合运用了。的二进

34、制随机数字序列，这种码就不适合运用了。30第第11章差错限制编码章差错限制编码n11.4.4 正反码正反码n正反码的编码：正反码的编码：n它是一种简洁的能够订正错码的编码。其中的监它是一种简洁的能够订正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中元相同或者相反则由信息码中“1”的个数而定。的个数而定。n例如，若码长例如，若码长n=10，其中信息位，其中信息位 k=5，监督位，监督位 r=5。其编码规则为：。其编码规则为：n当信息位中有奇数个当信息位中有奇数个“1”时，监督位是信息位的时，监督位是信息位的简洁重

35、复；简洁重复；n当信息位有偶数个当信息位有偶数个“1”时，监督位是信息位的反时，监督位是信息位的反码。码。n例如，若信息位为例如，若信息位为11001，则码组为，则码组为1100111001；若信息位为若信息位为10001，则码组为，则码组为1000101110。31第第11章差错限制编码章差错限制编码u正反码的解码正反码的解码u在上例中，先将接收码组中信息位和监督位按模在上例中，先将接收码组中信息位和监督位按模 2 相加，相加，得到一个得到一个5位的合成码组。然后，由此合成码组产生一个位的合成码组。然后，由此合成码组产生一个校验码组。校验码组。u若接收码组的信息位中有奇数个若接收码组的信息位

36、中有奇数个“1”，则合成码组就，则合成码组就是校验码组；若接收码组的信息位中有偶数个是校验码组；若接收码组的信息位中有偶数个“1”，则，则取合成码组的反码作为校验码组。取合成码组的反码作为校验码组。u最终，视察校验码组中最终，视察校验码组中“1”的个数，按下表进行判决的个数，按下表进行判决及订正可能发觉的错码。及订正可能发觉的错码。32第第11章差错限制编码章差错限制编码p校验码组和错码的关系校验码组和错码的关系 例如，若发送码组为例如，若发送码组为1100111001，接收码组中无错码，则，接收码组中无错码，则合成码组应为合成码组应为11001 11001=00000。由于接收码组信息。由于

37、接收码组信息位中有奇数个位中有奇数个“1”，所以校验码组就是，所以校验码组就是00000。按上表。按上表判决，结论是无错码。判决，结论是无错码。33第第11章差错限制编码章差错限制编码若传输中产生了差错，使接收码组变成若传输中产生了差错，使接收码组变成1000111001，则合成，则合成码组为码组为10001 1100101000。由于接收码组中信息位有偶数。由于接收码组中信息位有偶数个个“1”，所以校验码组应取合成码组的反码，即，所以校验码组应取合成码组的反码，即10111。由。由于其中有于其中有4个个“1”和和1个个“0”，按上表推断信息位中左边第，按上表推断信息位中左边第2位为错码。位为

38、错码。若接收码组错成若接收码组错成1100101001，则合成码组变成，则合成码组变成11001 0100110000。由于接收码组中信息位有奇数个。由于接收码组中信息位有奇数个“1”，故校验码，故校验码组就是组就是10000，按上表推断，监督位中第，按上表推断，监督位中第1位为错码。位为错码。最终，若接收码组为最终，若接收码组为1001111001，则合成码组为，则合成码组为10011 1100101010，校验码组与其相同，按上表推断，这，校验码组与其相同，按上表推断，这时错码多于时错码多于1个。个。上述长度为上述长度为10的正反码具有订正的正反码具有订正1位错码的实力，并能检测全位错码的

39、实力，并能检测全部部2位以下的错码和大部分位以下的错码和大部分2位以上的错码。位以上的错码。34第11章差错限制编码l11.5 线性分组码线性分组码l基本概念基本概念l代数码：建立在代数学基础上的编码。代数码：建立在代数学基础上的编码。l线性码：依据一组线性方程构成的代数码。线性码：依据一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代在线性码中信息位和监督位是由一些线性代数方程联系着的。数方程联系着的。l线性分组码：依据一组线性方程构成的分组线性分组码：依据一组线性方程构成的分组码码。l本节将以汉明码为例引入线性分组码的一般本节将以汉明码为例引入线性分组码的一般原理。原理。35

40、第11章差错限制编码n汉明码汉明码n能够订正能够订正1位错码且编码效率较高的一种线性分位错码且编码效率较高的一种线性分组码组码n汉明码的构造原理。汉明码的构造原理。n在偶数监督码中，由于运用了一位监督位在偶数监督码中，由于运用了一位监督位a0，它，它和信息位和信息位an-1 a1一起构成一个代数式：一起构成一个代数式：n在接收端解码时，事实上就是在计算在接收端解码时，事实上就是在计算n若若S=0，就认为无错码；若，就认为无错码；若S=1，就认为有错，就认为有错码。现将上式称为监督关系式，码。现将上式称为监督关系式，S称为校正子。称为校正子。由于校正子由于校正子S只有两种取值，故它只能代表有错只

41、有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。和无错这两种信息，而不能指出错码的位置。36第11章差错限制编码p若监督位增加一位，即变成两位，则能增加一个类似的监督若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有关系式。由于两个校正子的可能值有4中组合：中组合：00，01，10，11，故能表示，故能表示4种不同的信息。若用其中种不同的信息。若用其中1种组合表示无错，种组合表示无错，则其余则其余3种组合就有可能用来指示一个错码的种组合就有可能用来指示一个错码的3种不同位置。种不同位置。同理，同理，r个监督关系式个监督关系式,就能出就能出r

42、位校正子，能指示位校正子，能指示1位错码的位错码的(2r 1)个可能位置。个可能位置。p一般来说，若码长为一般来说，若码长为n，信息位数为，信息位数为k，则监督位数，则监督位数rnk。假如希望用假如希望用r个监督位构造出个监督位构造出r个监督关系式来指示个监督关系式来指示1位错码位错码的的n种可能位置，则要求种可能位置，则要求p下面通过一个例子来说明如何具体构造这些监督关系式。下面通过一个例子来说明如何具体构造这些监督关系式。37第11章差错限制编码p例：设分组码例：设分组码(n,k)中中k=4，为了订正，为了订正1位错码，由上式可位错码，由上式可知，要求监督位数知，要求监督位数 r 3。若取

43、。若取 r=3，则，则n=k+r=7。我们。我们用用a6 a5 a0表示这表示这7个码元，用个码元，用S1、S2和和S3表示表示3个监督关个监督关系式中的校正子，则系式中的校正子，则S1、S2和和S3的值与错码位置的对应关系的值与错码位置的对应关系可以规定如下表所列：可以规定如下表所列：38第11章差错限制编码由表中规定可见，仅当一位错码的位置在由表中规定可见，仅当一位错码的位置在a2、a4、a5或或a6时，时，校正子校正子S1为为1；否则；否则S1为零。这就意味着为零。这就意味着a2、a4、a5和和a6四个四个码元构成偶数监督关系：码元构成偶数监督关系：同理，同理，a1、a3、a5和和a6构

44、成偶数监督关系：构成偶数监督关系：以及以及a0、a3、a4 和和a6构成偶数监督关系构成偶数监督关系39第11章差错限制编码在发送端编码时，信息位在发送端编码时，信息位a6、a5、a4和和a3的值确定于输入信号，的值确定于输入信号，因此它们是随机的。监督位因此它们是随机的。监督位a2、a1和和a0应依据信息位的取值按监督应依据信息位的取值按监督关系来确定，即监督位应使上关系来确定，即监督位应使上3式中式中S1、S2和和S3的值为的值为0（表示编成（表示编成的码组中应无错码）：的码组中应无错码）：上式经过移项运算，解出监督位上式经过移项运算，解出监督位给定信息位后，可以干脆按上式算出监督位，给定

45、信息位后，可以干脆按上式算出监督位，结果见下表：结果见下表：40第11章差错限制编码41第11章差错限制编码接收端收到每个码组后，先计算出接收端收到每个码组后，先计算出S1、S2和和S3，再查表，再查表推断错码状况。例如，若接收码组为推断错码状况。例如，若接收码组为a6 a5 a4 a3 a2 a1 a0=0000011，按上述公式计算可得：，按上述公式计算可得：S1=0，S2=1，S3=1。由于。由于S1 S2 S3 等于等于011，故查表可知在，故查表可知在a3位有位有1错码。错码。依据上述方法构造的码称为汉明码。表中所列的依据上述方法构造的码称为汉明码。表中所列的(7,4)汉汉明码的最小

46、码距明码的最小码距d0=3。因此，这种码能够订正。因此，这种码能够订正1个错码个错码或检测或检测2个错码。由于码率个错码。由于码率k/n=(n-r)/n=1 r/n，故当，故当n很大和很大和r很小时，码率接近很小时，码率接近1。可见，汉明码是一种高效。可见，汉明码是一种高效码。码。42第11章差错限制编码n线性分组码的一般原理线性分组码的一般原理u线性分组码的构造线性分组码的构造pH矩阵矩阵上面上面(7,4)汉明码的例子有汉明码的例子有现在将上面它改写为现在将上面它改写为上式中已经将上式中已经将“”简写成简写成“+”。43第11章差错限制编码上式可以表示成如下矩阵形式：上式可以表示成如下矩阵形

47、式：上式还可以简记为上式还可以简记为H AT=0T 或或A HT=044第11章差错限制编码H AT=0T 或或A HT=0式中式中 A=a6 a5 a4 a3 a2 a1 a00=000右上标右上标“T”表示将矩阵转置。例如，表示将矩阵转置。例如，HT是是H的转置，即的转置，即HT的第一行为的第一行为H的第一列，的第一列，HT的其次行为的其次行为H的其次列等等。的其次列等等。将将H称为监督矩阵。称为监督矩阵。只要监督矩阵只要监督矩阵H给定，编码时监督位和信息位的关系就完全给定，编码时监督位和信息位的关系就完全确定了。确定了。45第11章差错限制编码H矩阵的性质：矩阵的性质：1)H的行数就是监

48、督关系式的数目，它等于监督位的行数就是监督关系式的数目，它等于监督位的数目的数目r。H的每行中的每行中“1”的位置表示相应码元之间存在的位置表示相应码元之间存在的监督关系。例如，的监督关系。例如，H的第一行的第一行1110100表示监督位表示监督位a2是是由由a6 a5 a4之和确定的。之和确定的。H矩阵可以分成两部分，例如矩阵可以分成两部分，例如 式中，式中，P为为r k阶矩阵，阶矩阵，Ir为为r r阶单位方阵。我们阶单位方阵。我们将具有将具有P Ir形式的形式的H矩阵称为典型阵。矩阵称为典型阵。46第11章差错限制编码2)由代数理论可知，H矩阵的各行应当是线性无关的，否则将得不到 r个线性

49、无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式P Ir，则其各行确定是线性无关的。因为简洁验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。生成矩阵-G矩阵：上面汉明码例子中的监督位公式为 也可以改写成矩阵形式：47第11章差错限制编码或者写成或者写成式中，式中，Q为一个为一个k r阶矩阵，它为阶矩阵，它为P的转置，即的转置，即 Q=PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位就产生出监督位。48第11章差错限制编码我们将我们将Q的左边加上的左边加上1个个k k阶单位方阵，就构成阶单

50、位方阵，就构成1个矩阵个矩阵G G称为生成矩阵，因为由它可以产生整个码组，即有称为生成矩阵，因为由它可以产生整个码组，即有或者或者因此，假如找到了码的生成矩阵因此，假如找到了码的生成矩阵G，则编码的方法就完全确，则编码的方法就完全确定了。具有定了。具有IkQ形式的生成矩阵称为典型生成矩阵。由典形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组型生成矩阵得出的码组A中，信息位的位置不变，监督位附中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。加于其后。这种形式的码称为系统码。49第11章差错限制编码G矩阵的性质：矩阵的性质：1)G矩阵的各行是线性无关的。因为由上式可以看矩阵