数据通信与计算机网络--04差错控制.ppt

《数据通信与计算机网络--04差错控制.ppt》由会员分享，可在线阅读，更多相关《数据通信与计算机网络--04差错控制.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4讲 差错检测与校正第第4 4讲讲 差错检测与校正差错检测与校正 课时授课计划 课 程 内 容第4讲 差错检测与校正内容：同步的基本概念 海明码 循环冗余码 目的与要求：掌握帧同步的基本概念；掌握海明码编码原理；掌握循环冗余码编码原理；重点与难点：重点：循环冗余码、海明码；难点：循环冗余码。第4讲 差错检测与校正课堂讨论：海明码？循环冗余码？现代教学方法与手段：投影 PowerPoint幻灯课件复习（提问）：PCM的工作过程？常用的物理层联网设备有哪些？第4讲 差错检测与校正第第3 3章章 数据链路层数据链路层 3.1 差错检测与校正 3.2 数据链路层的功能第4讲 差错检测与校正为什么需要

2、数据链路层为什么需要数据链路层？物理层未解决的问题：物理层未解决的问题：位位流流传传输输过过程程中中不不可可避避免免会会出出现现差差错错。（电电磁磁干干扰，线路问题）扰，线路问题）数数据据收收发发之之间间的的速速率率匹匹配配问问题题(不不同同设设备备处处理理速速度不同度不同)最主要的作用是通过一最主要的作用是通过一些数据链路层协议些数据链路层协议(即即链路控制规程链路控制规程),在不太在不太可靠的物理链路上实现可靠的物理链路上实现可靠的数据传输可靠的数据传输.第4讲 差错检测与校正数据链路层的功能数据链路层的功能实现实现两个相两个相邻邻的机器的机器间间的无差的无差错错的的传传输输。利用物理利用

3、物理层层提供的提供的原始比特流传输原始比特流传输服服务务，向网，向网络层络层提供提供可靠的数据传输可靠的数据传输服服务务。第4讲 差错检测与校正数据链路层的问题数据链路层的问题如何识别相邻的机器如何识别相邻的机器 -编址与寻址编址与寻址如何实现可靠的数据传输如何实现可靠的数据传输 -差错控制和流量控制差错控制和流量控制如何识别数据流的开始与结束如何识别数据流的开始与结束 -成帧成帧第4讲 差错检测与校正成成 帧帧数据链路层所传送的不再是原始的比特流，而应数据链路层所传送的不再是原始的比特流，而应具备相应的语法和语义，以达到可靠传输的功能。具备相应的语法和语义，以达到可靠传输的功能。数据链路层将

4、从网络层接收的分组（数据链路层将从网络层接收的分组（Packet)Packet)组成组成帧后传送给物理层，通过物理层传送到对方的数帧后传送给物理层，通过物理层传送到对方的数据链路层。据链路层。帧：数据链路层规定最小的数据传送逻辑单位数据链路层规定最小的数据传送逻辑单位数据链路层协议要规定帧的类型与格式 类型包括控制信息帧与数据信息帧等，格式类型包括控制信息帧与数据信息帧等，格式则规定帧所包含的域）。则规定帧所包含的域）。第4讲 差错检测与校正帧的基本组成帧的基本组成域域帧定界帧定界（开始与结束）（开始与结束）地址字段地址字段（用于寻址）（用于寻址）帧类型帧类型（或长度（或长度/控制）控制）字段

5、字段数据数据帧校验字段帧校验字段（差错控制）（差错控制）第4讲 差错检测与校正帧的示意图帧的示意图上图只是帧的一般组成，不同的数据链路层协议所规定的帧格式可能会与其存在微小的区别。第4讲 差错检测与校正帧的地址帧的地址帧中的地址属于物理或硬件地址帧中的地址属于物理或硬件地址 网卡地址网卡地址(局域网局域网)链路标识链路标识(广域网广域网)用于设备或机器的物理寻址用于设备或机器的物理寻址第4讲 差错检测与校正帧的定界帧的定界定界就是标识帧的开始与结束定界就是标识帧的开始与结束常用的帧定界方法：常用的帧定界方法：带字符填充的首尾界符法带字符填充的首尾界符法带位填充的首尾标志法带位填充的首尾标志法字

6、符计数法字符计数法第4讲 差错检测与校正首尾界符法首尾界符法每一帧以每一帧以ASCII字符序列字符序列DLE STX开始，以开始，以DLE ETX结束。结束。DLE为为Data Link Escape 的缩写，的缩写，STX意味着意味着Start of Text，ETX代表代表 End of Text。其缺点是成帧完全依赖于其缺点是成帧完全依赖于8位字符位字符数据数据组帧组帧第4讲 差错检测与校正字符填充字符填充在首尾界符法中，由于数据中可能会出现在首尾界符法中，由于数据中可能会出现DLE STX或或DLE ETX，从而干扰帧的正常定界从而干扰帧的正常定界字符填充法可用于解决上述问题。即发送端

7、在数字符填充法可用于解决上述问题。即发送端在数据中所遇到的据中所遇到的DLE前再插入一个附加前再插入一个附加的的DLE，而而接收端则忽略两个连续接收端则忽略两个连续DLE的前一个。的前一个。网络层发出的数据网络层发出的数据经数据链路层填充后的数据经数据链路层填充后的数据第4讲 差错检测与校正首尾标记法首尾标记法每一帧使用一个特殊的位模式每一帧使用一个特殊的位模式“01111110”作作为开始和结束标记。为开始和结束标记。该位模式又称为该位模式又称为flag位模式允许数据帧包含任意个数的比特，也允位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。许每个字符采用任意比特的编码。

8、第4讲 差错检测与校正位填充位填充在首尾标记法中，由于数据中可能会出现与标记在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界相同的位串，从而干扰帧的正常定界位填充法可用于解决上述问题。即发送端在数据位填充法可用于解决上述问题。即发送端在数据中若遇到中若遇到5个连续的个连续的“1”时，则在其后自动插队时，则在其后自动插队入一个入一个“0”。该技术简称。该技术简称“逢五逢五1插插0”；接收端；接收端则忽略则忽略5个连续的个连续的“1”后面的后面的“0”，简称，简称“逢逢五五1删删0”。(a)0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

9、 0 1 0(b)(b)0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0(c)(c)0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 填充的位填充的位第4讲 差错检测与校正字符计数法字符计数法在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。如果发生传输错误，则可能更改帧长的值，从而导致帧的同步出现问题。该方法通常与上述其他方法结合使用。第4讲 差错检测与校正计数计数计数第第1帧帧5个字符个字符第第2 2帧帧5个字符个字符第第3 3帧帧8个字符个字符发送发送:接收接收:第第1

10、帧正确帧正确!第第2 帧不正确帧不正确!7出错!11个字符计数?第4讲 差错检测与校正差错检测与校正差错检测与校正基本概念基本概念常用的简单差错控制编码常用的简单差错控制编码海明码海明码循环冗余码循环冗余码第4讲 差错检测与校正基本概念基本概念差错差错：指通过通信信道后接收数据与发：指通过通信信道后接收数据与发送数据不一致的现象送数据不一致的现象产生差错原因：产生差错原因：热噪声热噪声-随机错误随机错误 冲击噪声冲击噪声-突发错误突发错误第4讲 差错检测与校正基本概念基本概念误码率误码率：纠错码：纠错码：发现并纠正错误发现并纠正错误检错码：检错码：发现错误，但不能自动纠正错发现错误，但不能自动

11、纠正错误需要通过反馈重发来纠错误需要通过反馈重发来纠错 编码效率编码效率第4讲 差错检测与校正基本概念基本概念差错控制的编码方式：差错控制的编码方式：自动请求重发自动请求重发ARQ(automatic request for repeat)向前纠错向前纠错FEC(Foeward Error Correcytion)第4讲 差错检测与校正常用的简单差错控制编码常用的简单差错控制编码水平奇偶校验：水平奇偶校验：在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的7 7 7 7位信息码位信息码位信息码位信息码

12、后附加一个校验位后附加一个校验位后附加一个校验位后附加一个校验位0 0 0 0或或或或1 1 1 1，使整个字符中，使整个字符中，使整个字符中，使整个字符中“1”1”1”1”的个数构成的个数构成的个数构成的个数构成奇数个（奇校验）或偶数个（偶校验）。奇数个（奇校验）或偶数个（偶校验）。奇数个（奇校验）或偶数个（偶校验）。奇数个（奇校验）或偶数个（偶校验）。垂直奇偶校验：垂直奇偶校验：也叫组校验，在发送字符块的末尾附加一个校验字也叫组校验，在发送字符块的末尾附加一个校验字也叫组校验，在发送字符块的末尾附加一个校验字也叫组校验，在发送字符块的末尾附加一个校验字符，且该字符中的第符，且该字符中的第符

13、，且该字符中的第符，且该字符中的第i i i i位是针对所有字符的第位是针对所有字符的第位是针对所有字符的第位是针对所有字符的第i i i i位所进行位所进行位所进行位所进行的校验。的校验。的校验。的校验。垂直水平奇偶校验垂直水平奇偶校验垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作垂直校验，对整个字符块作水平校验。字符作垂直校验，对整个字符块作水平校验。字符作垂直校验，对整个字符块作水平校验。字符作垂直校验，对整个字符块作水平校验。第4讲 差错检测与校正奇校

14、验的例子奇校验的例子10001010字符字符1b1b2b3b4b5b6b7check11001011字符字符211011010字符字符310101011字符字符410001010字符字符510001010字符字符611101010字符字符700100000校验校验字符字符第4讲 差错检测与校正海明码海明码1.海明码海明码(1)海明距离及意义海明距离及意义 两个码字中不同的位数的个数称为海明距离,简称H距离 1 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1求H距离的方法主要有:异或运算海明距离的意义是:假如两个码字具有海明距离d,则需要d 个位差错才能将其中一个码字转换成另一个.H

15、=3第4讲 差错检测与校正海明码海明码(2)海明码算法海明码算法将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号,第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m 位数据(2 r n+1).每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校验)校验位校验位第4讲 差错检测与校正海明码海明码为了知道编号为K的数据位对哪些检测位有影响,将编号K 改写成2的幂的和(如:11=1+2+8,29=1+4+8+16),1个位只由扩展式中所示编号的位检测(编号为11的位,只能由1,2,8 检测位检测)由于在每个校

16、验位的形成表达式中,除自身编号外,其余都是信息位的编号,因此只要信息位是确定的,校验位也可以唯一地确定.第4讲 差错检测与校正海明码海明码由上图可看出,海明码的信息余量很大,因而编号效率低.例:根据海明编码方法,对ASCII字符Z(二进制编码是1011010),形成11位码字,要求简单地写出编码过程.并说明在传输过程中,有一位错的情况下,如何能够检查出是哪一位是错的?解:m=7,n=11,r=4 编号:1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4,8=8,9=1+8,10=2+8,11=1+2+8 于是有:(1)(3)+(5)+(7)+(9)+(11)(2)(3)

17、+(6)+(7)+(10)+(11)(4)(5)+(6)+(7)(8)(9)+(10)+(11)被检测位：被检测位：数据位数据位检测位检测位第4讲 差错检测与校正海明码海明码编码编码码字码字最终的最终的海明码海明码为什么此为什么此处是处是1?1,2,4,8是校验位是校验位!其余位是信息位其余位是信息位.(8)(9)(10)(11)(1)(3)(5)(7)(9)(11)(9)1 0 1 0 0 1 0 1 0 0奇数个奇数个1偶数个偶数个1采用偶采用偶检验哦检验哦!第4讲 差错检测与校正循环冗余码循环冗余码循环冗余校验循环冗余校验 英文全称为英文全称为Cyclic Redundancy Chec

18、k,简称简称CRC。工作原理：工作原理：软件实现软件实现:多项式除法，将余式作为冗余信息多项式除法，将余式作为冗余信息传送。传送。硬件实现硬件实现:编码电路编码电路又称多项式校验又称多项式校验第4讲 差错检测与校正多项式除法多项式除法多项式除法：多项式除法：被除多项式被除多项式/除式除式（得出商和余式，余式作为校验码附（得出商和余式，余式作为校验码附在后面一起发送出去）在后面一起发送出去）第4讲 差错检测与校正多项式除法多项式除法多项式除法：多项式除法：被除多项式被除多项式=除式除式*商商+剩余多项式剩余多项式（换言之，被除多项式减去剩余多（换言之，被除多项式减去剩余多项式可以用除式整除）项式

19、可以用除式整除）第4讲 差错检测与校正CRC的工作原理（的工作原理（1）将要发送的二进制数序列看成是一个多项式。将要发送的二进制数序列看成是一个多项式。n位的数据序列对应位的数据序列对应n-1次多项式。次多项式。P(x)=aP(x)=an-1n-1x xn-1n-1+a+an-2n-2x xn-2n-2+a+a1 1x+ax+a0 0 选定除式，被选作除式的多项式称为生成多选定除式，被选作除式的多项式称为生成多项式，常见的生成多项式有：项式，常见的生成多项式有：CRC-12CRC-12：G(x)=xG(x)=x1212+x+x1111+x+x3 3+x+x2 2+x+1 (+x+1 (城域网城

20、域网)CRC-16CRC-16：G(x)=xG(x)=x1616+x+x1515+x+x2 2+1 +1 （广域网）（广域网）CRC-CCITTCRC-CCITT：G(x)=xG(x)=x1616+x+x1212+x+x5 5+1 +1 （广域网）（广域网）CRC-32CRC-32：G(x)=xG(x)=x3232+x+x2626+x+x2323+x+x2222+x+x1616+x+x1212+x+x1111 +x +x1010+x+x8 8+x+x7 7+x+x5 5+x+x4 4+x+x2 2+x+1+x+1（局域网）（局域网）第4讲 差错检测与校正CRC的工作原理（的工作原理（2）被除多

21、项式P(x)除式G(x)剩余多项式R(x)被除多项式=除式*商+剩余多项式P(x)=G(x)*商+R(x)发送方发送的数据：P(x)+R(x)接收方接收的数据为T(x)如果正确传输，则T(x)=G(x)*商+R(x)+R(x)第4讲 差错检测与校正CRC的工作原理（的工作原理（2）将将P(x)乘以乘以 G(x)的最高幂次作为被除式，作的最高幂次作为被除式，作多项式除式。除法采用多项式除式。除法采用“加法不进位，减加法不进位，减法不借位法不借位”的规则，即相当于异或操作的规则，即相当于异或操作将所得到的余式多项式将所得到的余式多项式R(x)重新转换为二进重新转换为二进制数，作为冗余码。制数，作为

22、冗余码。将冗余码加在原传送数据后面，构成发送将冗余码加在原传送数据后面，构成发送序列。序列。接收方收到后，将接收序列用同样的生成接收方收到后，将接收序列用同样的生成多项式去除。若余式为零，则表示无差错；多项式去除。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。否则，说明传输过程中出现了错误。第4讲 差错检测与校正CRC的例子（的例子（1）要发送的二进制数序列为要发送的二进制数序列为“1010001”，7位的数据序列对应位的数据序列对应5次多项式：次多项式：P(x)=xP(x)=x6 6+x+x4 4+1+1 选定的生成多项式为：选定的生成多项式为：G(x)=xG(x)=x4 4+x

23、+x2 2+x+1+x+1（最高次数为最高次数为4 4，相当于，相当于1011110111）被除多项式为：被除多项式为：P(x)xP(x)x4 4 x x1010+x+x8 8+x+x4 4 （相当于相当于101000100000000）第4讲 差错检测与校正CRC的例子（的例子（2）多项式除法后得到冗余码为多项式除法后得到冗余码为11011101，所以相，所以相应的数据发送序列为应的数据发送序列为1010001 11011101101000100000000101111011111011111010 0 00111111010101111011111010101111011110111101

24、1111010101111011111011101第4讲 差错检测与校正CRC硬件实现硬件实现R0R1Rr-1信息输入端g1g2gr-1CRC校验可以由软件或硬件来实现，现多采用超大规模校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。集成电路芯片以硬件方式实现。第4讲 差错检测与校正CRC硬件实现硬件实现R0R1R3信息输入端R21000101R0R1R2R3输入输出:110100001GG11101001110101100011111011001010101111101101010100100001000100000111101第4讲 差错检测与校正CRC的检错能力全部单个错全部单个错 全部离散的二位错全部离散的二位错 全部奇数个错全部奇数个错全部长度小于或等于全部长度小于或等于K K的突发错的突发错（K K为生为生成多项式的最高幂次）成多项式的最高幂次）以以1-1-（1/21/2）K-1K-1的概率检出长度为的概率检出长度为K+1K+1位位的突发错的突发错 第4讲 差错检测与校正课堂小结课堂小结理解循环冗余码理解帧的构成第4讲 差错检测与校正HomeworkHomework预习第三章中的数据链路协议