《数据通信与计算机网络-04差错控制.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据通信与计算机网络-04差错控制.优秀PPT.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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
9、 1 1 1 1 1 1 1 1 1 1 1 0 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
10、3帧帧8个字符个字符发送发送:接收接收:第第1 帧正确帧正确!第第2 帧不正确帧不正确!7出错!11个字符计数?第4讲 差错检测与校正差错检测与校正差错检测与校正基本概念基本概念常用的简洁差错限制编码常用的简洁差错限制编码海明码海明码循环冗余码循环冗余码第4讲 差错检测与校正基本概念基本概念差错：指通过通信信道后接收数差错：指通过通信信道后接收数据与发送数据不一样的现象据与发送数据不一样的现象产生差错缘由：产生差错缘由：热噪声热噪声-随机错误随机错误 冲击噪声冲击噪声-突发错误突发错误第4讲 差错检测与校正基本概念基本概念误码率：误码率：纠错码：发觉并订正错误纠错码：发觉并订正错误检错码：发觉
11、错误，但不能自动检错码：发觉错误，但不能自动订正错误须要通过反馈重发来纠订正错误须要通过反馈重发来纠错错 编码效率编码效率第4讲 差错检测与校正基本概念基本概念差错限制的编码方式：差错限制的编码方式：自动恳求重发自动恳求重发ARQ(automatic request for repeat)向前纠错向前纠错FEC(Foeward Error Correcytion)第4讲 差错检测与校正常用的简洁差错限制编码常用的简洁差错限制编码水平奇偶校验：水平奇偶校验：在面对字符的数据传输中，在每个字在面对字符的数据传输中，在每个字符的符的7位信息码后附加一个校验位位信息码后附加一个校验位0或或1，使，使整
12、个字符中整个字符中“1”的个数构成奇数个（奇校的个数构成奇数个（奇校验）或偶数个（偶校验）。验）或偶数个（偶校验）。垂直奇偶校验：垂直奇偶校验：也叫组校验，在发送字符块的末尾也叫组校验，在发送字符块的末尾附加一个校验字符，且该字符中的第附加一个校验字符，且该字符中的第i位是位是针对全部字符的第针对全部字符的第i位所进行的校验。位所进行的校验。垂直水平奇偶校验垂直水平奇偶校验垂直奇偶校验和水平奇偶校验技术垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作垂直校验，对整个的综合。对每个字符作垂直校验，对整个字符块作水平校验。字符块作水平校验。第4讲 差错检测与校正奇校验的例子奇校验的例子10001
13、010字符字符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距离的方法主要有距离的方法主要有:异或运算异或运算海明距离的意义是海明距离的意义是:假如两个码字具有海假如
14、两个码字具有海明距离明距离d,则须要则须要d 个个位差错才能将其中一个码字转换成另一个位差错才能将其中一个码字转换成另一个.H=3第4讲 差错检测与校正海明码海明码(2)海明码算法海明码算法将码字数内的位从最左边起先按依次依次将码字数内的位从最左边起先按依次依次编号编号,第第1位是位是1号号,第第2位是位是2号号,第第n位是位是n号号.编号为编号为2的幂的位的幂的位(1号位号位,2号位号位,4号位号位,8号位等号位等)是校验位是校验位,其余的位填入其余的位填入m 位数据位数据(2 r n+1).每个校验位的取值应使得包括自己在内的每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性
15、一些位的集合符合规定的奇偶性.(主要用于主要用于奇偶性校验奇偶性校验)校验位校验位第4讲 差错检测与校正海明码海明码为了知道编号为K的数据位对哪些检测位有影响,将编号K 改写成2的幂的和(如:11=1+2+8,29=1+4+8+16),1个位只由扩展式中所示编号的位检测(编号为11的位,只能由1,2,8 检测位检测)由于在每个校验位的形成表达式中,除自身编号外,其余都是信息位的编号,因此只要信息位是确定的,校验位也可以唯一地确定.第4讲 差错检测与校正海明码海明码由上图可看出,海明码的信息余量很大,因而编号效率低.例:依据海明编码方法,对ASCII字符Z(二进制编码是1011010),形成11
16、位码字,要求简洁地写出编码过程.并说明在传输过程中,有一位错的状况下,如何能够检查出是哪一位是错的?解: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)+(6)+(7)+(10)+(11)(4)(5)+(6)+(7)(8)(9)+(10)+(11)被检测位：被检测位：数据位数据位检测位检测位第4讲 差错检测与校正海明码海明码编码编码码字码字最终的最终的海明码海明码为什么此为什么此处是处是1?1,2,4,8是校验位是校验
17、位!其余位是信息位其余位是信息位.(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 Check,简称简称CRC。工作原理：工作原理：软件实现软件实现:多项式除法，将余式作为冗余信息多项式除法，将余式作为冗余信息传送。传送。硬件实现硬件实现:编码电路编码电路又称多项式校验又称多项式校验第4讲 差错检测与校正多项式除法多项式除法多项式除法：多项式除法：被除多项式被
18、除多项式/除式除式（得出商和余式，余式作为校验码附（得出商和余式，余式作为校验码附在后面一起发送出去）在后面一起发送出去）第4讲 差错检测与校正多项式除法多项式除法多项式除法：多项式除法：被除多项式被除多项式=除式除式*商商+剩余多项式剩余多项式（换言之，被除多项式减去剩余多（换言之，被除多项式减去剩余多项式可以用除式整除）项式可以用除式整除）第4讲 差错检测与校正CRC的工作原理（的工作原理（1）将要发送的二进制数序列看成是一个多项式。将要发送的二进制数序列看成是一个多项式。n位的数据序列对应位的数据序列对应n-1次多项式。次多项式。P(x)=aP(x)=an-1n-1x xn-1n-1+a
19、+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 (城域网城域网)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-32
20、CRC-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）被除多项式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的工作原理（的工
21、作原理（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+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的例
23、子（的例子（2）多项式除法后得到冗余码为多项式除法后得到冗余码为11011101，所以相，所以相应的数据发送序列为应的数据发送序列为1010001 11011101101000100000000101111011111011111010 0 001111110101011110111110101011110111101111011111010101111011111011101第4讲 差错检测与校正CRC硬件实现硬件实现R0R1Rr-1信息输入端g1g2gr-1CRC校验可以由软件或硬件来实现，现多接受超大规模集校验可以由软件或硬件来实现，现多接受超大规模集成电路芯片以硬件方式实现。成电路芯片
24、以硬件方式实现。第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预习第三章中的数据链路协议