笫七、八讲 数据链路层功能、差错检测与校正.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 小结两种编码方式 除非在单向传输或实时要求特别高 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水平奇偶校验 发送时 不能边发送信息位边产生冗余位并插入发送 垂直奇偶校验 必须等到要发送的完整信息块到奇后 才能产生冗余位 且 一定要使用记忆寄存器 接收时 同样要等到信息块到奇后才能校验 所以 和垂直奇偶校验相比 它的编码和检测实现起来都要复杂一些 水平奇偶校验 11110111100000000000000000000011110 信息位 冗余位 如果采用偶校验 发送4个字符CC为100011 水平奇偶校验 编码效率0 8漏检率没垂直奇偶校验高 1111001110 1查出错误 1个错 奇数位错误01100 0无法查出错误 2个错 偶数错01110 1查出错误 3个错 奇数位错误000000000011110 信息位 冗余位 例子 验证1 可检测出各段同一位上的奇数位错 水平奇偶校验 10110 1查出错误10110 1查出错误01000 1查出错误10000 1查出错误10000 1查出错误10000 1查出错误01110 1查出错误 信息位 冗余位 例子 验证2 可检测出突发长度 p的所有错 在这儿 P 7 突发长度为7的错误 意味着每行一个错 水平奇偶校验 奇偶校验码 水平垂直奇偶校验 同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验 图3 3水平垂直奇偶校验 水平垂直奇偶校验的编码效率为它能检测出所有3位或3位以下的错误 因为此时至少在某一行或某一列上为一位错 奇数位错 突发长度 p 1的突发错以及很大一部分偶数位错 水平垂直奇偶校验 1111011110000000000000000000001111011110 冗余位 如果采用偶校验 发送4个字符CC为100011 水平垂直奇偶校验 冗余位 漏检率没垂直或者水平奇偶校验高 11110 111100000000000 00000000001111011110 冗余位 如果采用偶校验 水平垂直奇偶校验 冗余位 检测出所有3位或3位以下的错误 因为此时至少在某一行或某一列上为一位错 如图 两次报错 11110 111100000000000 000000000011110 11110 冗余位 如果采用偶校验 水平垂直奇偶校验 冗余位 检测出部分偶位错如图 四次报错 图中 和四位错 就可在第2行 第p行 第1列与第2列检测出来 自然 仍然会有一些偶数位错检测不出 例如 图中 和4位错 它们正好在一个矩阵的四角 对第2行 第p 1行 第1列和第q列来说都是两位错 因而检测不出来 水平垂直奇偶校验 1111011110000000000000000000001111011110 冗余位 如果采用偶校验 水平垂直奇偶校验 冗余位 这种每行每列都有两个错无法检测 漏检 如图 无报错 11110 11110 00000 00000 00000 00000 11110 11110 冗余位 如果采用偶校验 水平垂直奇偶校验 冗余位 突发长度 p 1的突发错如图 P 7 正反码 一种简单的能够纠正差错的编码 其中冗余位的个数与信息位个数相同 冗余位与信息位或者完全相同或者完全相反 由信息位中 1 的个数来决定 正反码 例如电报通信中常用五单位电码编成正反码的规则如下 k 5 r k 5 n k r 10 当信息位中有奇数个 1 时 冗余位就是信息位的简单重复 当信息位中有偶数个 1 时 冗余位是信息位的反码 例如 若信息位为01011 则码字为0101101011若信息位为10010 则码字为1001001101 K 信息位r 冗余位n 码字长度 正反码 接收端的校验方法为 先将接收码字中信息位和冗余位按位半加 得到一个k位的合成码组 对上述具体的码长为10的正反码来说 就是得到一个5位的合成码组 若接收码字中的信息位中有奇数个 1 则就取合成码组 校验码组 若接收码字中信息位中有偶数个 1 则取合成码组的反码作为校验码组 0101101011的合成码组 00000信息位中有3个1 合成码组为校验码组 010110101100000 正反码 例子1 发送码字为0101101011 传输中无差错 则合成码组为01011 01011 00000 由于接收码字的信息位中有3个 1 故00000就是校验码组 查前表知无差错 若传输中发生了一位差错 接收端收到1101101011 则合成码组为11011 01011 10000 由于接收的码字中信息位中有4个 1 故校验码组为01111 查前表知 信息位的第1位错 故可将接收到的1101101011纠正为0101101011 若传输中发生了两位错 接收端收到1101111011 则合成码组为11011 11011 00000 而此时校验码组为11111 查前表可判断出为两位或两位以上的差错 正反码 又如 若传输中发生了四位错 接收端收到1101011010 则合成码组为11010 11010 00000 而此时校验码组也为00000 查表会认为是无差错 也就是说对这种差错是漏捡了 再如 若传输中发生了三位错 接收端收到1101011011 则合成码组为11010 11011 00001 此时校验码组也为00001 查表会认为是冗余位中有一位差错 其位置对应于校验码组中 1 的位置 从而将其误纠为1101011010 实际上 任何一种检错码 都会发生漏检的情况 而任何一种纠错码 也都会发生误纠的情况 漏检率和误纠率都是差错控制编码的重要技术指标 当然是越小差错控制能力越强 例子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 无错 一位冗余位一个校正因子 0100100 信息位 冗余位 S 在奇偶校验情况下 只有一个监督关系式 一个校正因子 其取值只有两种 0或1 分别代表了无错和有错两种情况 而不能指出差错所在的位置若增加冗余位 也相应地增加监督关系式和校正因子 就能区分更多的情况 信息位为k位 增加r位冗余位 构成n k r位码字 若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错 则要求或 3 2 3海明码 例子 以k 4为例来说明 要满足 则r 3 现取r 3 则n k r 7在4位信息位a6a5a4a3后面加上3位冗a2a1a0位 构成7位码字a6a5a4a3a2a1a0 其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错 S2S1S0这三个校正因子其它4种编码的值可用来区分a3 a4 a5或a6一位错 a2 a4 a5或a6的一位错都应使S2 1 由此可以得到监督关系式 a1 a3 a5或a6的一位错都应使S1 1 由此可以得到监督关系式 a0 a3 a4或a6的一位错都应使S0 1 由此可以得到监督关系式 3 2 3海明码 那么如图所示得出监督关系式 在发送端编码时 信息位a6 a5 a4和a3的值取决于输入信号 是随机的 冗余位a2 a1和a0的值应根据信息位的取值按监督关系式来决定 使上述三式中的S2 S1和S0取值为零由此可求得 已知信息位后 按此三式即可算出各冗余位 对于各种信息位算出的冗余位如后表 例子 在接收端收到每个码字后 按监督关系式算出S2 S1和S0 若为全 0 则认为无错 若不全为 0 在一位错的情况下 可查表来判定是哪一位错 从而纠正之 例如码字0010101传输中发生一位错 在接收端收到的为0011101 代入监督关系式可算得S2 0 S1 1和S0 1 由查表得S2S1S0 011对应于a3错 因而可将0011101纠正为0010101 但是 若码字0010101传输中发生两位错 在接收端收到的为0011111 代入监督关系式可算得S2 0 S1 0和S0 1 查表得S2S1S0 001对应于a0错 从而会将0011111纠正为0011110 这就是误纠的情况 例子 16 7 4 1 12 例子 再如 若码字0010101传输中发生三位错 在接收端收到的为0101101 代入监督关系式可算得S2 0 S1 0和S0 0 查表可得S2S1S0 000对应于无错 从而认为传输中无差错 这就是漏检的情况 我们这个例子中正好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差错检测与校正3 2 3海明码3 2 4循环冗余码3 3数据链路协议3 3 1停等协议3 3 2顺序接收的管道协议3 3 3选择重传协议 是要求同学了解的 这些内容在本电子教案中并未讲解而是要求同学自己阅读教材 3 2 4循环冗余码 在计算机网络和数据通信中