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

《笫七、八讲数据链路层功能、差错检测与校正.ppt》由会员分享，可在线阅读，更多相关《笫七、八讲数据链路层功能、差错检测与校正.ppt（75页珍藏版）》请在三一文库上搜索。

1、数据通信与计算机网络（第二版）电子教案,笫七、八讲 数据链路层功能、 差错检测与校正,本章内容,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,作业评讲 第三章 数据链路层 3.1 数据链路层的功能 3.2 差错检测与校正 3.3 数据链路协议 3.4 协议描述与验证 3.5 数据链路层协议举例,知识点：数据链路层的功能、差错检测与校正、数据链路层协议、协议举例。 重 点：数据链路层协议 。 难 点：顺序接收的管道协议、滑动窗口协议,本章教学要求,本讲内容,作业评讲 第三章 数据链路层 3.1 数据链路层的功能 3.2 差错检测与校正 3.2.1 传输差错的特性

2、3.2.2 常用的简单差错控制编码,3.1 数据链路层的功能,基本功能： 将物理层提供的原始的传送比特流的可能出错的物理连接改造成为逻辑上无差错的数据链路 最基本的服务:将源机器网络层来的数据可靠地传输到相邻节点的目标机网络层 要完成许多特定的功能 主要有如何将比特组合成帧（frame）； 处理传输中出现的差错； 调节发送方的发送速率不至于使较慢的接收方不能承受，以及数据链路层连接的建立、维持和释放，称之为链路管理。,3.1 数据链路层的功能,1. 帧同步 2. 差错控制 3. 流量控制 链路管理,注意，物理层里的同步是位同步,3.1.1 帧同步,字符填充 首尾定界符 比特填充 首尾标志 字节

3、记数 违例编码,3.1.2 差错控制,由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。 实现复杂一点的机制，要用： 保留己发的帧：以便出错后重发 计时器 (timer)：避免无限等待 帧编号 ：保证每帧最终都能正确地交付给接收方网络层一次,3.1.3 流量控制,发送方发送能力大于接受方的接受能力 使用反馈机制通知发送方 数据链路层的流量控制,控制的是:相邻两节点间数据链路上的流量 其他高层也提供流量控制的功能,3.1.4 链路管理,主要用于面向连接的服务 包括链路建立,链路维持,链路释放 在通信站点间分配管理信道,本讲内容,第三

4、章 数据链路层 3.1 数据链路层的功能 3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2 差错检测与校正,为什么需要差错检测？ 信号幅度、频率、相位的衰减和畸变,3.2 差错检测与校正,为什么会有衰减和畸变 原因: 线路本身电气特性造成的随机噪声（热噪声）的影响 电信号在线路上产生反射造成的回音效应 相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等）,什么是差错检测与校正 在一个实用的通信系统中一定要能发现（检测）这种差错

5、并采用措施纠正（校正），把差错控制在所能允许的尽可能小的范围内,3.2 差错检测与校正,本讲内容,第三章 数据链路层 3.1 数据链路层的功能 3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2.1 传输差错的特性,噪声分类： 随机热噪声:信道所固有的，持续存在的 冲击噪声:由于外界特定的短暂原因所造成的 噪声比较： 随机错通常较少 冲击噪声的幅度可以相当大 ，它是传输中产生差错的重要原因,衡量一个信道质量的重要参数是误码率： 通常用10的负若干次方来标志信道的误码率Pe。

6、 例子： 在一条话频线路中，误码率若为10-5 ，则意味着平均十万位中有一位出错。 差错控制最常用的方法是差错控制编码。,3.2.1 传输差错的特性,差错控制编码的原理： 信息位：要发送的数据 冗余位：在向信道发送之前，先按照某种关系加上一定的冗余位 发送与接收的过程： 发送时：信息位+冗余位 构成码字发送 接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生,3.2.1 传输差错的特性,差错控制编码分类： 检错码 指能自动发现差错的编码 纠错码 指不仅能发现差错而且能自动纠正差错的编码,3.2.1 传输差错的特性,衡量编码性能的参数 编码效率

7、R 意思是码字中信息位所占的比例 若码字中信息位为k位，编码时外加冗余位为r位，则编码后得到的码字长为n = k + r位。,3.2.1 传输差错的特性,数据通信中，利用编码方法来进行差错控制的方式，基本上有两类： 自动请求重发ARQ 接收端检测出有差错时，就设法通知发送端重发，直到正确的码字收到为止。 前向纠错FEC 接收端不但能发现差错，而且能确定二进制错码元的位置，从而就可以加以纠正。,3.2.1 传输差错的特性,比较ARQ与FEC,小结两种编码方式,除非在单向传输或实时要求特别高（FEC由于不需要重发，实时性较好）等场合外，数据通信中使用更多的还是ARQ差错控制方式 可以将上述两者混合

8、使用 当码字中的差错个数在纠正能力以内时，直接进行纠正； 当码字中的差错个数超出纠正能力时，则检出差错令其重发来纠正差错。,本讲内容,第三章 数据链路层 3.1 数据链路层的功能 3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的简单差错控制编码,*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。,3.2.2 常用的简单差错控制编码,介绍三种较为实用的简单编码 奇偶校验码 (检错码) 定比码 (检错码) 正反码 (纠错码),垂直奇偶校验 水平奇偶校验 水平垂直奇偶校验,3.2.2 常用的简单差错控制编码,奇偶校验码 奇偶校验码是通过增加冗余位来使得

9、码字中“1”的个数保持奇或偶数的编码方法，是一种检错码,奇偶校验码 垂直奇偶校验,垂直奇偶校验是将整个发送的信息块分为定长p位的若干段（比如说q段），每段后面为了保持“1”的个数为奇或偶数,加上一位奇偶位,图3.1 垂直奇偶校验,图中，pq位信息位（I11，I21，IP1，I12，Ipq）中，p位构成一段（即图中一列），共q段（即共有q列）。每段加上一位奇偶校验冗余位，即图中的ri(i= 1,2,q)。若用偶校验，则 若用奇校验，则 编码效率：,垂直奇偶校验,发送时，边发送信息位，边产生冗余位，并插入发送 接收时，边接收，边校验，并拿去校验位,垂直奇偶校验,注意，如果发送方采用奇校验，那么接受

10、方也必须采用奇校验。 如果发送方采用偶校验，那么接受方也必须采用偶校验。,垂直奇偶校验,在7位字符代码（即用7位二进制数位表示一个字符）中，p = 7，编码效率为7 / 8 。这种奇偶校验方法能检测出每列中的所有奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于1 / 2 。 为了降低对突发错误的漏检率，人们又引进了水平奇偶检验。,垂直奇偶校验,奇偶校验码 水平奇偶校验,水平奇偶检验。它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。 （i=1,2,p） （i=1,2,p） 编码效率为,图3.2 水平奇偶校验,发送时，不

11、能边发送信息位边产生冗余位并插入发送（垂直奇偶校验） 必须等到要发送的完整信息块到奇后，才能产生冗余位。且，一定要使用记忆寄存器。 接收时，同样要等到信息块到奇后才能校验。 所以，和垂直奇偶校验相比，它的编码和检测实现起来都要复杂一些。,水平奇偶校验,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

12、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的所有错,在这儿，P7，突发长度为7的错误，意味着每行一个错,水平奇偶校验,奇

13、偶校验码 水平垂直奇偶校验,同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验,图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

14、* 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 * * *,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗 余 位,检测出部分偶位错 如图：四次报错,图中 、 、 和 四位错

15、，就可在第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

16、0 0 0 0 * 0 0 0 0 0 * 1 1 1 1 0 * 1 1 1 1 0 * * *,冗余位,如果采用偶校验：,水平垂直奇偶校验,冗 余 位,突发长度p+1的突发错 如图：P7,正反码,一种简单的能够纠正差错的编码，其中冗余位的个数与信息位个数相同。冗余位与信息位或者完全相同或者完全相反，由信息位中“1”的个数来决定。,正反码,例如电报通信中常用五单位电码编成正反码的规则如下：k=5,r=k=5,n=k+r=10； 当信息位中有奇数个“1”时，冗余位就是信息位的简单重复； 当信息位中有偶数个“1”时，冗余位是信息位的反码。 例如：若信息位为01011，则码字为0101101011

17、 若信息位为10010，则码字为1001001101。,K：信息位 r ：冗余位 n ：码字长度,正反码,接收端的校验方法为：先将接收码字中信息位和冗余位按位半加，得到一个k位的合成码组（对上述具体的码长为10的正反码来说，就是得到一个5位的合成码组）。 若接收码字中的信息位中有奇数个“1”，则就取合成码组=校验码组； 若接收码字中信息位中有偶数个“1”，则取合成码组的反码作为校验码组。 0101101011的合成码组 ：00000 信息位中有3个1，合成码组 为 校验码组,01011 01011 00000,正反码,例子1,发送码字为0101101011，传输中无差错，则合成码组为01011

18、01011=00000，由于接收码字的信息位中有3个“1”，故00000就是校验码组，查前表知无差错。 若传输中发生了一位差错，接收端收到1101101011，则合成码组为1101101011=10000，由于接收的码字中信息位中有4个“1”，故校验码组为01111。查前表知，信息位的第1位错，故可将接收到的1101101011纠正为0101101011。 若传输中发生了两位错，接收端收到1101111011，则合成码组为1101111011=00000，而此时校验码组为11111，查前表可判断出为两位或两位以上的差错。,正反码,又如，若传输中发生了四位错，接收端收到1101011010，则合

19、成码组为1101011010=00000，而此时校验码组也为00000，查表会认为是无差错，也就是说对这种差错是漏捡了。 再如，若传输中发生了三位错，接收端收到1101011011，则合成码组为1101011011=00001，此时校验码组也为00001，查表会认为是冗余位中有一位差错，其位置对应于校验码组中“1”的位置，从而将其误纠为1101011010。 实际上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是差错控制编码的重要技术指标，当然是越小差错控制能力越强。,例子2,正反码,正反码的编码效率较低，只有1/2。但其差错控制能力还是较强，如

20、上述长度为10的正反码，能检测出全部两位差错和大部分两位以上的差错，并且还具有纠正一位差错的能力。由于正反码的编码效率较低，只能用于信息位较短的场合,正反码,本讲内容,第三章 数据链路层 3.2 差错检测与校正 3.2.3海明码 3.2.4 循环冗余码,海明码、循环冗余码 编码效率较高，差错控制能力较强的纠错和检错码。,3.2.3海明码,也是一种可以纠正一位差错的编码，但当信息位足够长时，它的编码效率要比正反码高得多 回顾奇偶校验，若信息位为k=n-1位 加上一位偶校验位a0，构成一个n位的码字 。在接收端校验时，可按关系式 若S=0，则无错；若S=1，则有错。上式可称为监督关系式，S称为校正

21、因子,3.2.3海明码,回顾奇偶校验，若信息位为k=n-1位 加上一位偶校验位a0，构成一个n位的码字 。在接收端校验时，可按关系式 若S=0，则无错；若S=1，则有错。上式可称为监督关系式，S称为校正因子,3.2.3海明码,例如：码字长n6，信息位为01001，采用偶校验位，冗余位为0，码字为：010010 那么，信息位k=n-1615位01001 加上一位偶校验位0，构成一个6位的码字010010。在接收端校验时，可按关系式 若S=0，无错； 一位冗余位一个校正因子,0 1 0 0 1 0 0,信息位,冗余位,S=,在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（0或1

22、），分别代表了无错和有错两种情况，而不能指出差错所在的位置 若增加冗余位，也相应地增加监督关系式和校正因子，就能区分更多的情况。 信息位为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就分别和这些位半

23、加构成三个不同的监督关系式。,例子,假如，我们这三个不同的监督关系式设定为： 无错， 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,

24、由此可以得到监督关系式:,3.2.3海明码,那么如图所示 得出监督关系式,在发送端编码时，信息位a6、a5、a4和a3的值取决于输入信号，是随机的。冗余位a2、a1和a0的值应根据信息位的取值按监督关系式来决定，使上述三式中的S2、S1和S0取值为零 由此可求得: 已知信息位后，按此三式即可算出各冗余位。对于各种信息位算出的冗余位如后表,例子,在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若为全“0”则认为无错。若不全为“0”，在一位错的情况下，可查表来判定是哪一位错，从而纠正之。 例如码字0010101传输中发生一位错，在接收端收到的为0011101，代入监督关系式可算得S2=0

25、、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，这就是误纠的情况。,例子,=167+4+1=12,例子,再如，若码字0010101传输中发生三位错，在接收端收到的为0101101，代入监督关系式可算得S2=0、S1=0和S0=0，查表可得S2 S1 S0=000对应于无错，从而认为传输中无差错，这就是漏检的情况。 我们

26、这个例子中正好 2r =k+r+1，若 2r k+r+1则在查表中还有多余的位置可用来表示两位以上的错误，就可降低漏检率了。比如，若k=7，则满足2r k+r+1的最小r为4。此时,上述例子中，k=4的海明码的编码效率为4/7；若k=7，则编码效率为7/11。由此可见，信息位长度越长时编码效率越高。 只能纠正一位错，若用在纠正传输中出现突发性差错时可以采用下述方法：将连续P个码字排成一个矩阵，每行一个码字,图3.4 海明码用于纠正突发错误的情况,3.2.3海明码,连续8个码字排成一个矩阵， 每行一个码字，突发长度8 那么，在8个码字里最多每个 码字一位错误,本讲内容,第三章 数据链路层 3.2

27、 差错检测与校正 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）次多项式

28、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 （信息位为10

29、10001）， 取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 循环冗余码,