笫七、八讲 数据链路层功能、差错检测与校正.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据通信与计算机网络（第二版）电子教案,笫七、八讲,数据链路层功能、,差错检测与校正,本章内容,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,作业评讲,第三章 数据链路层,3.1 数据链路层的功能,3.2 差错检测与校正,3.3 数据链路协议,3.4 协议描述与验证,3.5 数据链路层协议举例,知识点：,数据链路层的功能、差错检测与校正、数据链路层协议、协议举例。,重 点：,数据链路层协议,。,难 点：,顺序接收的管道协议、滑动窗口协议,本章教学要求,本讲内容,作业评讲,第三章 数据链路层,3.1 数据链路层的功能,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,3.1 数据链路层的功能,基本功能：,将物理层提供的原始的传送比特流的,可能出错的物理连接,改造成为逻辑上无差错的数据链路,最基本的服务,:,将源机器网络层来的数据可靠地传输到相邻节点的目标机网络层,要完成许多特定的功能,主要有如何将比特组合成帧（,frame,）；,处理传输中出现的差错；,调节发送方的发送速率不至于使较慢的接收方不能承受，以及数据链路层连接的建立、维持和释放，称之为链路管理。,3.1 数据链路层的功能,1.帧同步,2.,差错控制,3.,流量控制,链路管理,注意，物理层里的同步是位同步,3.1.,1,帧同步,字符填充 首尾定界符,比特填充 首尾标志,字节记数,违例编码,3.1.2 差错控制,由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。,实现复杂一点的机制，要用：,保留己发的帧：以便出错后重发,计时器,(timer),：避免无限等待,帧编号：保证每帧最终都能正确地交付给接收方网络层一次,3.1.,3,流量控制,发送方发送能力大于接受方的接受能力,使用反馈机制通知发送方,数据链路层的流量控制,控制的是,:,相邻两节点间,数据链路上的流量,其他高层也提供流量控制的功能,3.1.,4,链路管理,主要用于面向连接的服务,包括链路建立,链路维持,链路释放,在通信站点间分配管理信道,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2,差错检测与校正,为什么需要差错检测？,信号幅度、频率、相位的衰减和畸变,3.2,差错检测与校正,为什么会有衰减和畸变 原因,:,线路本身电气特性造成的随机噪声（热噪声）的影响,电信号在线路上产生反射造成的回音效应,相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等）,什么是差错检测与校正,在一个实用的通信系统中一定要能发现（检测）这种差错,并采用措施纠正（校正），把差错控制在所能允许的尽可能小的范围内,3.2,差错检测与校正,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2.1 传输差错的特性,噪声分类：,随机热噪声,:,信道所固有的，持续存在的,冲击噪声,:,由于外界特定的短暂原因所造成的,噪声比较：,随机错通常较少,冲击噪声的幅度可以相当大，它是传输中产生差错的重要原因,衡量一个信道质量的重要参数是误码率：,通常用,10,的负若干次方来标志信道的误码率,Pe,。,例子：,在一条话频线路中，误码率若为,10,-5,，则意味着平均十万位中有一位出错。,差错控制最常用的方法是差错控制编码。,3.2.1 传输差错的特性,差错控制编码的原理：,信息位：要发送的数据,冗余位：在向信道发送之前，先按照某种关系加上一定的冗余位,发送与接收的过程：,发送时：信息位,+,冗余位,构成码字发送,接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生,3.2.1 传输差错的特性,差错控制编码分类：,检错码,指能自动发现差错的编码,纠错码,指不仅能发现差错而且能自动纠正差错的编码,3.2.1 传输差错的特性,衡量编码性能的参数,编码效率,R,意思是码字中信息位所占的比例,若码字中信息位为,k,位，编码时外加冗余位为,r,位，则编码后得到的码字长为,n=k+r,位。,3.2.1 传输差错的特性,数据通信中，利用编码方法来进行差错控制的方式，基本上有两类：,自动请求重发,ARQ,接收端检测出有差错时，就设法通知发送端重发，直到正确的码字收到为止。,前向纠错,FEC,接收端不但能发现差错，而且能确定二进制错码元的位置，从而就可以加以纠正。,3.2.1 传输差错的特性,比较,ARQ,与,FEC,ARQ,FEC,使用编码种类,只要用检错码,必须用纠错码,是否需要双向信道,必须,不需,发送方是否需要缓冲区,需要,不需,其他,冗余位多（编码效率低）,设备复杂,小结两种编码方式,除非在单向传输或实时要求特别高（,FEC,由于不需要重发，实时性较好）等场合外，数据通信中使用更多的还是,ARQ,差错控制方式,可以将上述两者混合使用,当码字中的差错个数在纠正能力以内时，直接进行纠正；,当码字中的差错个数超出纠正能力时，则检出差错令其重发来纠正差错。,本讲内容,第三章 数据链路层,3.1 数据链路层的功能,3.2 差错检测与校正,3.2.1 传输差错的特性,3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2.2 常用的简单差错控制编码,介绍三种较为实用的简单编码,奇偶校验码,(,检错码,),定比码,(,检错码,),正反码,(,纠错码,),垂直奇偶校验,水平奇偶校验,水平垂直奇偶校验,3.2.2 常用的简单差错控制编码,奇偶校验码,奇偶校验码是通过增加冗余位来使得码字中“,1”,的个数保持奇或偶数的编码方法，是一种检错码,奇偶校验码,垂直奇偶校验,垂直奇偶校验是将整个发送的信息块分为定长,p,位的若干段（比如说,q,段），每段后面为了保持“,1”,的个数为奇或偶数,加上一位奇偶位,图,3.1,垂直奇偶校验,图中，,pq,位信息位（,I11,，,I21,，,，,IP1,，,I12,，,，,Ipq,）中，,p,位构成一段（即图中一列），共,q,段（即共有,q,列）。每段加上一位奇偶校验冗余位，即图中的,ri,(i=1,2,q),。若用偶校验，则,若用奇校验，则,编码效率：,垂直奇偶校验,发送时,，边发送信息位，边产生冗余位，并插入发送,接收时,，边接收，边校验，并拿去校验位,垂直奇偶校验,注意，如果发送方采用奇校验，那么接受方也必须采用奇校验。,如果发送方采用偶校验，那么接受方也必须采用偶校验。,垂直奇偶校验,在,7,位字符代码（即用,7,位二进制数位表示一个字符）中，,p=7,，编码效率为,7/8,。这种奇偶校验方法能检测出每列中的所有奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于,1/2,。,为了降低对突发错误的漏检率，人们又引进了水平奇偶检验。,垂直奇偶校验,奇偶校验码,水平奇偶校验,水平奇偶检验。它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。,（,i=1,2,p,）,（,i=1,2,p,）,编码效率为,图,3.2,水平奇偶校验,发送时,，不能边发送信息位边产生冗余位并插入发送（垂直奇偶校验）,必须等到要发送的完整信息块到奇后，才能产生冗余位。且，一定要使用记忆寄存器。,接收时,，同样要等到信息块到奇后才能校验。,所以，和垂直奇偶校验相比，它的编码和检测实现起来都要复杂一些。,水平奇偶校验,1 1 1 1 0,1 1 1 1 0,0 0 0 0 0,0 0 0 0 0,0 0 0 0 0,0 0 0 0 0,1 1 1 1 0,信息位,冗余位,如果采用偶校验：,发送,4,个字符,C,C,为,100011,水平奇偶校验,编码效率,0.8,漏检率没垂直奇偶校验高,1 1 1 1 0,0,1 1 1 0,1,查出错误，,1,个错，奇数位错误,0,1 1,0 0,0,无法查出错误，,2,个错，偶数错,0,1 1 1,0 1,查出错误，,3,个错，奇数位错误,0 0 0 0 0,0 0 0 0 0,1 1 1 1 0,信息位,冗余位,例子：（验证,1,）可检测出各段同一位上的奇数位错,水平奇偶校验,1,0,1 1 0,1,查出错误,1,0,1 1 0,1,查出错误,0,1,0 0 0,1,查出错误,1,0 0 0 0 1,查出错误,1,0 0 0 0,1,查出错误,1,0 0 0 0,1,查出错误,0,1 1 1 0,1,查出错误,信息位,冗余位,例子：（验证,2,）可检测出突发长度,p,的所有错,在这儿，,P,7,，突发长度为,7,的错误，意味着每行一个错,水平奇偶校验,奇偶校验码,水平,垂直奇偶校验,同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验,图,3.3,水平垂直奇偶校验,水平垂直奇偶校验的编码效率为,它能检测出所有,3,位或,3,位以下的错误（因为此时至少在某一行或某一列上为一位错）、奇数位错、突发长度,p+1,的突发错以及很大一部分偶数位错。,水平垂直奇偶校验,1 1 1 1 0,1 1 1 1 0,0 0 0 0 0,0 0 0 0 0,0 0 0 0 0,0 0 0 0 0,1 1 1 1 0,1 1 1 1 0,冗余位,如果采用偶校验：,发送,4,个字符,C,C,为,100011,水平垂直奇偶校验,冗,余,位,漏检率没垂直或者水平奇偶校验高,1,1,1,1 0 *,1 1 1 1 0,0 0 0 0 0,0 0,0,0 0,*,0 0 0 0 0,0 0 0 0 0,1 1 1,1 0,1 1 1 1 0,*,*,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗,余,位,检测出所有,3,位或,3,位以下的错误（因为此时至少在某一行或某一列上为一位错）,如图：两次报错,1,1,1,1 0 *,1 1 1 1 0,0 0 0 0 0,0 0,0,0 0,*,0 0 0 0 0,0 0 0 0 0,1 1 1,1,0,*,1 1 1 1 0,*,*,*,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗,余,位,检测出部分偶位错,如图：四次报错,图中 、,和 四位错，就可在第,2,行、第,p,行、第,1,列与第,2,列检测出来。自然，仍然会有一些偶数位错检测不出。例如，图中,、,、和,4,位错，它们正好在一个矩阵的四角，对第,2,行、第,p+1,行、第,1,列和第,q,列来说都是两位错，因而检测不出来。,水平垂直奇偶校验,1,1,1,1 0,1 1 1 1 0,0,0,0,0 0,0 0 0 0 0,0 0 0 0 0,0 0 0 0 0,1 1 1 1 0,1 1 1 1 0,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗,余,位,这种每行每列都有两个错无法检测（漏检）,如图：无报错,1 1,1,1 0,*,1 1,1,1 0,*,0 0,0,0 0,*,0 0,0,0 0,*,0,0,0 0 0,*,0,0,0 0 0,*,1,1,1 1 0,*,1,1,1 1 0,*,*,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗,余,位,突发长度,p+1,的突发错,如图：,P,7,正反码,一种,简单的,能够,纠,正差,错,的编,码,，其中冗余位的个数与信息位个数相同。冗余位与信息位或者完全相同或者完全相反，由信息位中“,1”,的个数来决定。,正反码,例如电报通信中常用五单位电码编成正反码的规则如下：,k=5,r=k=5,n=k+r=10,；,当信息位中有,奇数个“,1”,时，冗余位就是信息位的简单重复；,当信息位中有,偶数个“,1”,时，冗余位是信息位的反码。,例如：若信息位为,01011,，则码字为,01011,01011,若信息位为,10010,，则码字为,10010,01101,。,K,：信息位,r,：冗余位,n,：码字长度,正反码,接收端的校验方法为：先将接收码字中信息位和冗余位按位半加，得到一个,k,位的合成码组（对上述具体的码长为,10,的正反码来说，就是得到一个,5,位的合成码组）。,若接收码字中的信息位中有,奇数个“,1”,，则就取,合成码组,=,校验码组,；,若接收码字中信息位中有,偶数个“,1”,，则取,合成码组的反码,作为校验码组。,01011,01011,的合成码组：,00000,信息位中有,3,个,1,，合成码组 为 校验码组,01011,01011,00000,校验码组,差错情况,全“,0”,无差错,4,个“,1”,、,1,个“,0”,信息位中有一位差错，其位置对应于校验码组中“,0”,的位置,4,个“,0”,、,1,个“,1”,冗余位中有一位差错，其位置对应于校验码组中“,1”,的位置,其它情况,差错在两位或两位以上,正反码,例子,1,发送码字为,0101101011,，传输中无差错，则合成码组为,0101101011=00000,，由于接收码字的信息位中有,3,个“,1”,，故,00000,就是校验码组，,查前表,知无差错。,若传输中发生了一位差错，接收端收到,1,101101011,，则合成码组为,1,101101011=10000,，由于接收的码字中信息位中有,4,个“,1”,，故校验码组为,01111,。,查前表,知，信息位的第,1,位错，故可将接收到的,1101101011,纠正为,0101101011,。,若传输中发生了两位错，接收端收到,1,1011,1,1011,，则合成码组为,1,1011,1,1011=00000,，而此时校验码组为,11111,，,查前表,可判断出为两位或两位以上的差错。,正反码,又如，若传输中发生了四位错，接收端收到,1,101,01,101,0,，则合成码组为,1,101,0,1,101,0,=00000,，而此时校验码组也为,00000,，,查表,会认为是无差错，也就是说对这种差错是,漏捡,了。,再如，若传输中发生了三位错，接收端收到,1,101,01,1011,，则合成码组为,1,101,0,1,1011=00001,，此时校验码组也为,00001,，,查表,会认为是冗余位中有一位差错，其位置对应于校验码组中“,1”,的位置，从而将其,误纠,为,110101101,0,。,实际上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是差错控制编码的重要技术指标，当然是越小差错控制能力越强。,例子,2,正反码,正反码的编码效率较低，只有,1/2,。但其差错控制能力还是较强，如上述长度为,10,的正反码，能检测出全部两位差错和大部分两位以上的差错，并且还具有纠正一位差错的能力。由于正反码的编码效率较低，只能,用于信息位较短的场合,正反码,本讲内容,第三章 数据链路层,3.2 差错检测与校正,3.2.3海明码,3.2.4 循环冗余码,海明码,、,循环冗余码,编码效率较高，差错控制能力较强的纠错和检错码。,3.2.3海明码,也是一种可以,纠正一位差错,的编码，但当信息位足够长时，它的编码效率要比正反码高得多,回顾奇偶校验，若信息位为,k=n-1,位,加上一位偶校验位,a0,，构成一个,n,位的码字 。在接收端校验时，可按关系式,若,S=0,，则无错；若,S=1,，则有错。上式可称为监督关系式，,S,称为校正因子,3.2.3海明码,回顾奇偶校验，若信息位为,k=n-1,位,加上一位偶校验位,a0,，构成一个,n,位的码字 。在接收端校验时，可按关系式,若,S=0,，则无错；若,S=1,，则有错。上式可称为监督关系式，,S,称为校正因子,3.2.3海明码,例如：码字长,n,6,，信息位为,01001,，采用偶校验位，冗余位为,0,，码字为：,010010,那么，信息位,k=n-1,6,1,5,位,01001,加上一位偶校验位,0,，构成一个,6,位的码字,010010,。在接收端校验时，可按关系式,若,S=0,，无错；,一位冗余位一个校正因子,0,1,0,0,1,0,0,信息位,冗余位,S=,在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（,0,或,1,），分别代表了无错和有错两种情况，而不能指出差错所在的位置,若增加冗余位，也相应地增加监督关系式和校正因子，就能区分更多的情况。,信息位为,k,位，,增加,r,位冗余位,，构成,n=k+r,位码字。若希望用,r,个监督关系式产生的,r,个校正因子,来区分无错和在码字中,n,个不同位置的一位错，则要求 或,3.2.3海明码,例子,以,k=4,为例来说明，要满足 ，,则,r3,。现取,r=3,，则,n=k+r=7,在,4,位信息位,a6a5a4a3,后面加上,3,位冗,a2a1a0,位，构成,7,位码字,a6a5a4a3 a2a1a0,。,其,a2,、,a1,和,a0,分别由,4,位信息位中某几位半加得到。,那末在校验时，,a2,、,a1,和,a0,就分别和这些位半加构成三个不同的监督关系式。,例子,假如，我们这三个不同的监督关系式设定为：,无错，,S2=0,S1=0,S0=0,若,a0,错，则,S2=0,S1=0,S0=1,若,a1,错，则,S2=0,S1=1,S0=0,若,a2,错，则,S2=1,S1=0,S0=0,；,若,a3,错，,若,a4,错，,若,a5,错，,若,a6,错，,S2 S1 S0,这三个校正因子其它,4,种编码的值可用来区分,a3,、,a4,、,a5,或,a6,一位错。,a2,、,a4,、,a5,或,a6,的一位错都应使,S2=1,由此可以得到监督关系式,:,a1,、,a3,、,a5,或,a6,的一位错都应使,S1=1,由此可以得到监督关系式,:,a0,、,a3,、,a4,或,a6,的一位错都应使,S0=1,由此可以得到监督关系式,:,000,00,1,0,1,0,1,00,0,1,1,1,0,1,1,1,0,1,1,1,错码位置,无错,3.2.3海明码,那么如图所示 得出监督关系式,在发送端编码时，信息位,a6,、,a5,、,a4,和,a3,的值取决于输入信号，是随机的。冗余位,a2,、,a1,和,a0,的值应根据信息位的取值按监督关系式来决定，使上述三式中的,S2,、,S1,和,S0,取值为零,由此可求得,:,已知信息位后，按此三式即可算出各冗余位。对于各种信息位算出的冗余位如后表,例子,信息位,冗余位,信息位,冗余位,0,0,00,00,0,1,0,10,01,0,00,0,0,0,0,0,10,1,0,0,1,0,000,0,0,00,101,0,0,10,信息位,冗余位,信息位,冗余位,0,0,00,00,0,1000,111,00,0,1,0,1,1,1001,100,001,0,1,01,1010,010,0011,110,1011,001,0100,110,1100,001,0101,101,1101,010,0110,011,1110,100,0111,000,1111,111,在接收端收到每个码字后，按监督关系式算出,S2,、,S1,和,S0,，若为全“,0”,则认为无错。若不全为“,0”,，在一位错的情况下，可,查表,来判定是哪一位错，从而纠正之。,例如码字,0010101,传输中发生一位错，在接收端收到的为,0011101,，代入监督关系式可算得,S2=0,、,S1=1,和,S0=1,，由,查表,得,S2 S1 S0=011,对应于,a3,错，因而可将,0011101,纠正为,0010101,。,但是，若码字,0010101,传输中发生两位错，在接收端收到的为,0011111,，代入监督关系式可算得,S2=0,、,S1=0,和,S0=1,，,查表,得,S2 S1 S0=001,对应于,a0,错，从而会将,0011111,纠正为,0011110,，这就是,误纠,的情况。,例子,=16,7+4+1=12,例子,再如，若码字,0010101,传输中发生三位错，在接收端收到的为,0101101,，代入监督关系式可算得,S2=0,、,S1=0,和,S0=0,，,查表,可得,S2 S1 S0=000,对应于无错，从而认为传输中无差错，这就是,漏检,的情况。,我们这个例子中正好,2,r,=k+r+1,，若,2,r,k+r+1,则在,查表,中还有多余的位置可用来表示两位以上的错误，就可降低漏检率了。比如，若,k=7,，则满足,2,r,k+r+1,的最小,r,为,4,。此时,上述例子中，,k=4,的海明码的编码效率为,4/7,；若,k=7,，则编码效率为,7/11,。由此可见，信息位长度越长时编码效率越高。,只能纠正一位错，若用在纠正传输中出现突发性差错时可以采用下述方法：将连续,P,个码字排成一个矩阵，每行一个码字,图,3.4,海明码用于纠正突发错误的情况,3.2.3海明码,连续,8,个码字排成一个矩阵，,每行一个码字，突发长度,8,那么，在,8,个码字里最多每个,码字一位错误,本讲内容,第三章 数据链路层,3.2 差错检测与校正,3.2.3海明码,3.2.4 循环冗余码,3.3,数据链路协议,3.3.1,停等协议,3.3.2,顺序接收的管道协议,3.3.3,选择重传协议,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2.4 循环冗余码,在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码,CRC,CRC,码又称为多项式码。,任何一个由二进制数位串组成的代码都可以和一个只含有,0,和,1,两个系数的多项式建立一一对应的关系。,例子,代码,1011011,对应的多项式为,而多项式,对应的代码为,110110,k,位要发送的信息位可对应于一个（,k-1,）次多项式,K,（,x,），,r,位冗余位对应于一个（,r-1,）次多项式,R,（,x,）。由,k,位信息位后面加上,r,位冗余位组成的,n=k+r,位码字则对应于一个（,n-1,）次多项式,编码过程：已知,K,（,x,）求,R,（,x,）的过程，在,CRC,码中可以通过找到一个特定的,r,次多项式,G,（,x,）（最高项,的系数为,1,）来实现用,G,（,x,）去除,K,（,x,）得到的余式就是,R,（,x,）,例子,信息位,1010001 K(x)=,冗余位,1101 R(x)=,码字,10100011101,T(x)=,这里，最后的余数,1101,就是冗,余位，而,R,（,x,）,=x3+x2+1,。,使用模二除法：进行多项式除法时，只要对其相应系数相除就可以了。例如：,K,（,x,）,=x6+x4+1,（信息位为,1010001,），取,r=4 G,（,x,）,=x4+x2+x+1,（代码,10111,）则,X,r,K,（,x,）,=x10+x8+x4,（对应的代码为,10100010000,）那末由除法来求余式,R,（,X,）,4,3.2.4 循环冗余码,4,3.2.4 循环冗余码,X,r,K,（,x,）,R,（,x,）,G,（,x,）,Q,（,x,）,K(x)=1010001,G(x)=10111,=R(x)=1101,T(x)=1010001 1101,当,T(x)/G(x)=0,时，,传输无差错,4,3.2.4 循环冗余码,K(x)=1010001,G(x)=10111,=R(x)=1101,T(x)=1010001 1101,当,T(x)/G(x)=0,时，,传输无差错,P115,3.3 3.6 3.8 3.11 3.13,3.14,做一点改动,已知,G(x)=110011,，接收方接收的码字,1010110001101,1),传输中是否有差错,?,2),发送方发送的码字是什么,?,可以知道吗,?,(,提示,:,有两种情况,),3.2.4 循环冗余码,