笫五讲 差错检测与校正-new

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,数据通信与计算机网络（第二版）电子教案,笫五讲,差错检测与校正,1,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,2,3.1 数据链路层的功能,基本功能：,将物理层提供的原始的传送比特流的可能出错的物理连接改造成为逻辑上无差错的数据链路,最基本的服务就是将源机器网络层来的数据可靠地传输到相邻节点的目标机网络层,要完成许多特定的功能,主要有如何将比特组合成帧（,frame,）；,处理传输中出现的差错；,调节发送方的发送速率不至于使较慢的接收方不能承受，以及数据链路层连接的建立、维持和释放，称之为链路管理。,3,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,4,3.1.2 差错控制,由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。,实现复杂一点的机制，要用：,保留己发的帧：以便出错后重发,计时器,(timer),：避免无限等待,帧编号 ：保证每帧最终都能正确地交付给接收方网络层一次,5,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,6,3.2 差错检测与校正,为什么需要差错检测？,有如下原因造成信号幅度、频率和相位的衰减或畸变（又称为失真）,线路本身电气特性造成的随机噪声（又称热噪声）的影响,电信号在线路上产生反射造成的回音效应,相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等）,7,3.2 差错检测与校正（续）,差错：,数据通信中，前面的原因就会造成接收端收到的二进制数位（或称为码元）和发送端实际发送的二进制数位不一致,由“,1”,变为“,0”,，或由“,0”,变为“,1”,什么是差错检测与校正,在一个实用的通信系统中一定要能发现（检测）这种差错,并采用措施纠正（校正），把差错控制在所能允许的尽可能小的范围内,8,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,9,3.2.1 传输差错的特性,噪声分类,：,信道所固有的，持续存在的随机热噪声,由于外界特定的短暂原因所造成的冲击噪声,噪声比较：,随机错通常较少,冲击噪声的幅度可以相当大 ，它是传输中产生差错的重要原因,10,3.2.1 传输差错的特性（续）,衡量一个信道质量的重要参数是误码率：,通常用,10,的负若干次方来标志信道的误码率,Pe,。,例子：,在一条话频线路中，误码率若为 ，则意味着平均十万位中有一位出错。,差错控制最常用的方法是差错控制编码。,11,差错控制编码的原理：,信息位：要发送的数据,冗余位：在向信道发送之前，先按照某种关系加上一定 ,发送与接收的过程：,发送时：信息位,+,冗余位构成码字发送；,接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生。,12,差错控制编码分类：,检错码,指能自动发现差错的编码,纠错码,指不仅能发现差错而且能自动纠正差错的编码,13,衡量编码性能的参数,编码效率,R,意思是码字中信息位所占的比例,若码字中信息位为,k,位，编码时外加冗余位为,r,位，则编码后得到的码字长为,n = k + r,位。,判定规律,编码效率越高，即,R,越大，则信道中用来传送信息码元的有效利用率就越高。,14,3.2.1 传输差错的特性（续）,数据通信中，利用编码方法来进行差错控制的方式，基本上有两类：,自动请求重发,ARQ,（,Automatic,ReQuest,for repeat,）,接收端检测出有差错时，就设法通知发送端重发，直到正确的码字收到为止。,前向纠错,FEC,（,Forward Error Correction,）,接收端不但能发现差错，而且能确定二进制错码元的位置，从而就可以加以纠正。,15,比较,ARQ,与,FEC,16,小结两种编码方式,除非在单向传输或实时要求特别高（,FEC,由于不需要重发，实时性较好）等场合外，数据通信中使用更多的还是,ARQ,差错控制方式。,自然，也可以将上述两者混合使用，即当码字中的差错个数在纠正能力以内时，直接进行纠正；当码字中的差错个数超出纠正能力时，则检出差错令其重发来纠正差错。,17,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,18,3.2.2 常用的简单差错控制编码,将介绍奇偶校验码、定比码和正反码等三种较为实用的简单编码,奇偶校验码,奇偶校验码是通过增加冗余位来使得码字中“,1”,的个数保持奇或偶数的编码方法，是一种检错码,分类：,垂直奇偶校验,水平奇偶校验,水平垂直奇偶校验,19,奇偶校验码,垂直奇偶校验,垂直奇偶校验是将整个发送的信息块分为定长p位的若干段（比如说q段），每段后面按“1”的个数为奇或偶数的规律加上一位奇偶位,图,3.1,垂直奇偶校验,20,垂直奇偶校验,图中，,pq,位信息位（,I11,，,I21,，,，,IP1,，,I12,，,，,Ipq,）中，,p,位构成一段（即图中一列），共,q,段（即共有,q,列）。每段加上一位奇偶校验冗余位，即图中的,ri(i,= 1,2,q),。若用偶校验，则,若用奇校验，则,编码效率：,21,例子,通常，我们取一个字符的代码为一个信息位段，这种垂直奇偶校验有时也称为字符奇偶校验。,在,7,位字符代码（即用,7,位二进制数位表示一个字符）中，,p = 7,，编码效率为,7 / 8,。这种奇偶校验方法能检测出每列中的所有奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于,1 / 2,。,为了降低对突发错误的漏检率，人们又引进了水平奇偶检验。,22,垂直奇偶校验,字母,前,7,行为对应字母的,ASCII,码，最后一行是垂直奇校验编码（粗体）,a,b,c,d,e,f,g,校验位,1 1 0 0 0 0 1,1 1 0 0 0 1 0,1 1 0 0 0 1 1,1 1 0 0 1 0 0,1 1 0 0 1 0 1,1 1 0 0 1 1 0,1 1 0 0 1 1 1,0 0 1 1 1 1 1,23,水平垂直奇偶校验,字母,最后一行是垂直奇校验编码，最后一列是水平奇校验编码（均为粗体）,a,b,c,d,e,f,g,校验位,1 1 0 0 0 0 1,0,1 1 0 0 0 1 0,0,1 1 0 0 0 1 1,1,1 1 0 0 1 0 0,0,1 1 0 0 1 0 1,1,1 1 0 0 1 1 0,1,1 1 0 0 1 1 1,0,0 0 1 1 1 1 1 0,24,奇偶校验码,水平奇偶校验,水平奇偶检验。它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。,（,i=1,2,p,）,（,i=1,2,p,）,编码效率为,图3.2 水平奇偶校验,25,奇偶校验码,水平,垂直奇偶校验,同时进行水平奇偶校验和垂直奇偶校验就构成,水平垂直奇偶校验,图,3.3,水平垂直奇偶校验,26,奇偶校验码,水平,垂直奇偶校验（续）,水平垂直奇偶校验的编码效率为,它能检测出所有,3,位或,3,位以下的错误（因为此时至少在某一行或某一列上为一位错）、奇数位错、突发长度,p+1,的突发错以及很大一部分偶数位错。,27,例子,图中 、 、,和 四位错，就可在第,2,行、第,p,行、第,1,列与第,2,列检测出来。自然，仍然会有一些偶数位错检测不出。例如，图中,、,、 和,4,位错，它们正好在一个矩阵的四角，对第,2,行、第,p+1,行、第,1,列和第,q,列来说都是两位错，因而检测不出来。,28,奇偶校验码小结,水平垂直奇偶校验不仅可检错，还可用来纠正部分差错。,垂直奇偶校验有时又称为纵向奇偶校验,水平奇偶校验有时又称为横向奇偶校验,水平垂直奇偶校验则又称为纵横奇偶校验,29,定比码,每个码字中均含有相同数目的“,1”,（码字长一定，“,1”,的数目一定后，所含“,0”,的数目也就必然相同）。正由于每个码字中“,1”,的个数与“,0”,的个数之比保持恒定，故得此名，有时也称为恒比码,若,n,位码字中“,1”,的个数恒定为,m,，还可称为“,n,中取,m”,码。这种码在检测时，只要计算接收码字中“,1”,的数目，就能知道是否有差错,在国际无线电报通信中广泛采用的就是,7,中取,3,定比码。这种码字长为,7,位，规定总有,3,个“,1”,。共有,种码字，可用来分别代表性,26,个英文字母和其它符号,30,定比码（续）,定比码（,n,中取,m,）的编码效率为,对于,7,中取,3,码来说，,其编码效率是不高的。但是，定比码能检测出全部奇数位错以及部分偶数位错。实际上，除了码字中“,1”,变成“,0”,和“,0”,变成“,1”,成对出现的差错外，所有其它差错都能被检测出来，检错能力还是很强的,若信源产生的是随机的二进制数字序列，就不能采用定比码了。,31,正反码,一种简单的能够纠正差错的编码，其中冗余位的个数与信息位个数相同。冗余位与信息位或者完全相同或者完全相反，由信息位中“,1”,的个数来决定。,例如电报通信中常用五单位电码编成正反码的规则如下：,k=5,r=k=5,n=,k+r,=10,；当信息位中有奇数个“,1”,时，冗余位就是信息位的简单重复；当信息位中有偶数个“,1”,时，冗余位是信息位的反码。具体说来，若信息位为,01011,，则码字为,0101101011,；若信息位为,10010,，则码字为,1001001101,。,接收端的校验方法为：先将接收码字中信息位和冗余位按位半加，得到一个,k,位的合成码组（对上述具体的码长为,10,的正反码来说，就是得到一个,5,位的合成码组）。,若接收码字中的信息位中有奇数个“,1”,，则就取合成码组为校验码组；若接收码字中信息位中有偶数个“,1”,，则取合成码组的反码作为校验码组。,32,正反码（续）,校验码组,差错情况,全“,0”,无差错,4,个“,1”,、,1,个“,0”,信息位中有一位差错，其位置对应于校验码组中“,0”,的位置,4,个“,0”,、,1,个“,1”,冗余位中有一位差错，其位置对应于校验码组中“,1”,的位置,其它情况,差错在两位或两位以上,33,例子,发送码字为,0101101011,，传输中无差错，则合成码组为,0101101011=00000,，由于接收码字的信息位中有,3,个“,1”,，故,00000,就是校验码组，,查前表,知无差错。,若传输中发生了一位差错，接收端收到,1,101101011,，则合成码组为,1101101011=10000,，由于接收的码字中信息位中有,4,个“,1”,，故校验码组为,01111,。,查前表,知，信息位的第,1,位错，故可将接收到的,1,101101011,纠正为,0101101011,。,若传输中发生了两位错，接收端收到,1,1011,1,1011,，则合成码组为,1101111011=00000,，而此时校验码组为,11111,，,查前表,可判断出为两位或两位以上的差错。,34,例子（续）,又如，若传输中发生了四位错，接收端收到,1,101,01,101,0,，则合成码组为,1101011010=00000,，而此时校验码组也为,00000,，,查表,会认为是无差错，也就是说对这种差错是漏捡了。,再如，若传输中发生了三位错，接收端收到,1,101,01,1011,，则合成码组为,1101011011=00001,，此时校验码组也为,00001,，,查表,会认为是冗余位中有一位差错，其位置对应于校验码组中“,1”,的位置，从而将其误纠为,1101011010,。,实际上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是差错控制编码的重要技术指标，当然是越小差错控制能力越强。,35,正反码的编码效率较低，只有,1/2,。但其差错控制能力还是较强，如上述长度为,10,的正反码，能检测出全部两位差错和大部分两位以上的差错，并且还具有纠正一位差错的能力。由于正反码的编码效率较低，只能用于信息位较短的场合。,下面将介绍两种编码效率较高的，且差错控制能力较强的纠错和检错码。,36,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,37,3.2.3海明码,介绍,由,R. Hamming,在,1950,年首次提出,也是一种可以纠正一位差错的编码，但当信息位足够长时，它的编码效率要比正反码高得多,回顾奇偶校验，若信息位为,k=n-1,位 ，加上一位偶校验位,a0,，构成一个,n,位的码字 。在接收端校验时，可按关系式,若,S=0,，则无错；若,S=1,，则有错。上式可称为监督关系式，,S,称为校正因子,38,海明码（续）,在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（,0,或,1,），分别代表了无错和有错两种情况，而不能指出差错所在的位置,若增加冗余位，也相应地增加监督关系式和校正因子，就能区分更多的情况。,信息位为,k,位，增加,r,位冗余位，构成,n=k+r,位码字 。若希望用,r,个监督关系式产生的,r,个校正因子来区分无错和在码字中,n,个不同位置的一位错，则要求,或,39,例子,以,k = 4,为例来说明，要满足,前述不等式,，则,r3,。现取,r = 3,，则,n = k + r = 7,。,在,4,位信息位,后面加上,3,位冗余位,，构成,7,位码字,。其,a2,、,a1,和,a0,分别由,4,位信息位中某几位半加得到。那么在校验时，,a2,、,a1,和,a0,就分别和这些位半加构成三个不同的监督关系式。在无错时，这三个关系式的值,S2,、,S 1,和,S0,全为“,0”,。若,a2,错，则,S2 = 1,，而,S1=S0=0,；若,a1,错，则,S1=1,而,S2=S0=0,；若,a0,错，则,S0=1,，而,S2=S1=0,。,S2 S1 S0,这三个校正因子其它,4,种编码的值可用来区分,a3,、,a4,、,a5,或,a6,一位错。,40,例子（续）,a2、a4、a5或a6的一位错都应使S2 = 1,由此可以得到监督关系式,41,例子（续）,在发送端编码时，信息位,a6,、,a5,、,a4,和,a3,的值取决于输入信号，是随机的。冗余位,a2,、,a1,和,a0,的值应根据信息位的取值按监督关系式来决定，使上述三式中的,S2,、,S1,和,S0,取值为零,由此可求得,已知信息位后，按此三式即可算出各冗余位。对于各种信息位算出的冗余位如后表,42,信息位,冗余位,信息位,冗余位,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,43,例子（续）,在接收端收到每个码字后，按监督关系式算出,S2,、,S1,和,S0,，若为全“,0”,则认为无错。若不全为“,0”,，在一位错的情况下，可,查表,来判定是哪一位错，从而纠正之。,例如码字传输中发生一位错，在接收端收到的为,001,1,101,，代入监督关系式可算得,S2=0,、,S1=1,和,S0=1,，由,查表,得,S2 S1 S0=011,对应于,a3,错，因而可将纠正为。但是，若码字传输中发生两位错，在接收端收到的为，代入监督关系式可算得,S2=0,、,S1=0,和,S0=1,，,查表,得,S2 S1 S0=001,对应于,a0,错，从而会将纠正为，这就是误纠的情况。,=16,7+4+1=12,再如，若码字传输中发生三位错，在接收端收到的为，代入监督关系式可算得,S2=0,、,S1=0,和,S0=0,，,查表,可得,S2 S1 S0=000,对应于无错，从而认为传输中无差错，这就是漏检的情况。我们这个例子中正好,=k+r+1,，若,k+r+1,则在,查表,中还有多余的位置可用来表示两位以上的错误，就可降低漏检率了。比如，若,k=7,，则满足,k+r+1,的最小,r,为,4,。此时,r,2,44,海明码（续）,上述例子中，,k=4,的海明码的编码效率为,4/7,；若,k=7,，则编码效率为,7/11,。由此可见，信息位长度越长时编码效率越高。,只能纠正一位错，若用在纠正传输中出现突发性差错时可以采用下述方法：将连续,P,个码字排成一个矩阵，每行一个码字,图,3.4,海明码用于纠正突发错误的情况,45,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.1.1 帧同步*,3.1.2 差错控制,3.1.3 流量控制*,3.1.4 链路管理*,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.2.3海明码,3.2.4 循环冗余码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,46,3.2.4 循环冗余码,在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码,CRC,（,Cyclic Redundancy Code,）,CRC,码又称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有,0,和,1,两个系数的多项式建立一一对应的关系。,47,（,2,）循环冗余码（,CRC,）,CRC,（,Cyclic Redundancy Check,）是在所传送的,k,位信息后面附加一 个,r,位检验序列。,工作原理：,设,f(x),为一个,k,阶多项式,其系数是待发送信息的比特序列；,例如，待发送的信息序列是,1010001101,，则对应,f(x)=x9+x7+x3+x2+1,（,k=9),。,G(x),为一个,r,阶的,生成多项式,，由发收双方预先约定。,G,（,x),有国际标准。,48,CRC,码的产生：, 检验序列的生成：,用,x,r,f(x),除以,G(x),得余式,R(x),，其系数序列即是检验序列。,进行除法运算时，采用模,2,算术，即加法不进位，减法不借位（异或运算）。,49,例如，生成多项式,G(x)= x,5,+x,4,+x,2,+1,即,110101,（,r=5),x,5,f(x)=x,14,+x,12,+x,8,+x,7,+x,5,，即,1000,，也就是,f(x),信息序列向左移动,r=5,位。,x,5,f(x)/ G(x)=,（,1000,）,/,（,110101,），得余数为,01110,，对应的余式,R(x)=0x,4,+x,3,+x,2,+x+0 x,0,(,注意：若,G(x),为,r,阶，则余数序列有,r,位 ）。,50,1 1 0 1 0 1 0 1 1 0,1 1 0 1 0 1,）,1 0 1 0 0 0,1 1 0 1,0 0 0 0 0,1 1 0 1 0 1,0 1 1 1 0 1,1,1 1 0 1 0 1,0 0 1 1 1 0,1 0,1 1 0 1 0 1,0 0 1 1 1 1,1 0,1 1 0 1 0 1,0 0 1 0 1 1,0 0,1 1 0 1 0 1,0 1 1 0 0 1,0,1 1 0 1 0 1,0 1 1 1,0,余数，也就是检验序列（,r,位，这里,r=5,，,r,也是,G(x),的阶,）,51, 编码：,在原信息序列后面附加上检验序列（,r,位），得到,CRC,编码（发送序列）。,例如，,x,5,f(x)-R(x) =1010001101,01110,，即为发送的序列。,检验：在接收方，用相同的生成多项式,G(x),除所收到的序列，若余数为,0,，则传输无差错，否则传输出现差错。,52,练习题,3.3 某信道误码率为10,-5,，每帧长度为10,kbits，,那末,(1) 若差错都是单个错，则在该信道上传送的帧的平均出错率是多少？,(2) 若差错大多为突发错，平均突发长度为100,bits，,则在该信道上传送的帧的平均出错率是多少？,3.9,若信息位为,7,位，要构成能纠正一位错的海明码，则至少要加上多少位冗余位？并写出其监督关系式。,3.11,已知海明码的监督关系式为,s,0,= a,0,+ a,3,+ a,5,+ a,6,s,1,= a,1,+ a,4,+ a,5,+ a,6,s,2,= a,2,+ a,3,+ a,4,+ a,5,接收端收到的码字,a,6,a,5,a,4,a,3,a,2,a,1,a,0,=1011110，,在最多一位错的情况下，问发送端发送的码字是什么？,3.14,已知循环冗余码的生成多项式,G,（,X,）,= x,5,+x,4,+x+1,，,若接收方收到的码字为,11,，问传输中是否有差错？,53,