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

第4讲差错检测与校正第4讲差错检测与校正课时授课计划课程内容第4讲差错检测与校正内容：同步的基本概念海明码循环冗余码目的与要求：掌握帧同步的基本概念；掌握海明码编码原理；掌握循环冗余码编码原理；重点与难点：重点：循环冗余码、海明码；难点：循环冗余码。第4讲差错检测与校正课堂讨论：海明码？循环冗余码？现代教学方法与手段：投影PowerPoint幻灯课件复习（提问）：PCM的工作过程？常用的物理层联网设备有哪些？第4讲差错检测与校正第3章数据链路层3.1差错检测与校正3.2数据链路层的功能第4讲差错检测与校正为什么需要数据链路层？物理层未解决的问题：位流传输过程中不可避免会出现差错。（电磁干扰，线路问题）数据收发之间的速率匹配问题(不同设备处理速度不同)最主要的作用是通过一些数据链路层协议(即链路控制规程),在不太可靠的物理链路上实现可靠的数据传输.第4讲差错检测与校正数据链路层的功能实现两个相邻的机器间的无差错的传输。利用物理层提供的原始比特流传输服务，向网络层提供可靠的数据传输服务。第4讲差错检测与校正数据链路层的问题如何识别相邻的机器--编址与寻址如何实现可靠的数据传输--差错控制和流量控制如何识别数据流的开始与结束--成帧第4讲差错检测与校正成帧数据链路层所传送的不再是原始的比特流，而应具备相应的语法和语义，以达到可靠传输的功能。数据链路层将从网络层接收的分组（Packet)组成帧后传送给物理层，通过物理层传送到对方的数据链路层。帧：数据链路层规定最小的数据传送逻辑单位数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式则规定帧所包含的域）。第4讲差错检测与校正帧的基本组成—域帧定界（开始与结束）地址字段（用于寻址）帧类型（或长度/控制）字段数据帧校验字段（差错控制）第4讲差错检测与校正帧的示意图上图只是帧的一般组成，不同的数据链路层协议所规定的帧格式可能会与其存在微小的区别。帧的开始地址帧类型或长度数据帧校验帧的结束第4讲差错检测与校正帧的地址帧中的地址属于物理或硬件地址网卡地址(局域网)链路标识(广域网)用于设备或机器的物理寻址第4讲差错检测与校正帧的定界定界就是标识帧的开始与结束常用的帧定界方法：带字符填充的首尾界符法带位填充的首尾标志法字符计数法第4讲差错检测与校正首尾界符法每一帧以ASCII字符序列DLESTX开始，以DLEETX结束。DLE为DataLinkEscape的缩写，STX意味着StartofText，ETX代表EndofText。其缺点是成帧完全依赖于8位字符STX,A,B,GOOD,BYE,ETXA,B,GOOD,BYE数据组帧第4讲差错检测与校正字符填充在首尾界符法中，由于数据中可能会出现DLESTX或DLEETX，从而干扰帧的正常定界字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。DLE,STX,A,DLE,B,DLE,ETXDLE,STX,A,DLE,DLE,B,DLE,ETX网络层发出的数据经数据链路层填充后的数据第4讲差错检测与校正首尾标记法每一帧使用一个特殊的位模式“01111110”作为开始和结束标记。该位模式又称为flag位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。…Data…0111111001111110第4讲差错检测与校正位填充在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0”。(a)011011111111111111110010(b)011011111011111011111010010(c)011011111111111111110010填充的位第4讲差错检测与校正字符计数法在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。如果发生传输错误，则可能更改帧长的值，从而导致帧的同步出现问题。该方法通常与上述其他方法结合使用。第4讲差错检测与校正512345678980123456512347678980123456计数计数计数第1帧5个字符第2帧5个字符第3帧8个字符发送:接收:第1帧正确!第2帧不正确!问题:出错之后,接收方与发送方不同步!无法确定下一帧的开始位置.请求重传也没有用处,因为发送方不知道应该回跳多少字符开始重传.7出错!11个字符计数??一般地,在数据链路协议中使用字符计数与其它方法相结合来提高可靠性.第4讲差错检测与校正差错检测与校正基本概念常用的简单差错控制编码海明码循环冗余码第4讲差错检测与校正基本概念差错：指通过通信信道后接收数据与发送数据不一致的现象产生差错原因：热噪声----〉随机错误冲击噪声--〉突发错误第4讲差错检测与校正基本概念误码率：纠错码：发现并纠正错误检错码：发现错误，但不能自动纠正错误需要通过反馈重发来纠错编码效率接收的总码元数发生差错的码元数ePrkknkR第4讲差错检测与校正基本概念差错控制的编码方式：自动请求重发ARQ(automaticrequestforrepeat)向前纠错FEC(FoewardErrorCorrecytion)第4讲差错检测与校正常用的简单差错控制编码水平奇偶校验：在面向字符的数据传输中，在每个字符的7位信息码后附加一个校验位0或1，使整个字符中“1”的个数构成奇数个（奇校验）或偶数个（偶校验）。垂直奇偶校验：也叫组校验，在发送字符块的末尾附加一个校验字符，且该字符中的第i位是针对所有字符的第i位所进行的校验。垂直水平奇偶校验垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作垂直校验，对整个字符块作水平校验。第4讲差错检测与校正奇校验的例子10001010字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100000校验字符第4讲差错检测与校正海明码1.海明码(1)海明距离及意义※两个码字中不同的位数的个数称为海明距离,简称H距离1000100110110001※求H距离的方法主要有:异或运算※海明距离的意义是:假如两个码字具有海明距离d,则需要d个位差错才能将其中一个码字转换成另一个.H=3第4讲差错检测与校正海明码(2)海明码算法①将码字数内的位从最左边开始按顺序依次编号,第1位是1号,第2位是2号,……第n位是n号.编号为2的幂的位(1号位,2号位,4号位,8号位等)是校验位,其余的位填入m位数据(2r≧n+1).②每个校验位的取值应使得包括自己在内的一些位的集合符合规定的奇偶性.(主要用于奇偶性校验)123456789101112校验位第4讲差错检测与校正海明码③为了知道编号为K的数据位对哪些检测位有影响,将编号K改写成2的幂的和(如:11=1+2+8,29=1+4+8+16),1个位只由扩展式中所示编号的位检测(编号为11的位,只能由1,2,8检测位检测)④由于在每个校验位的形成表达式中,除自身编号外,其余都是信息位的编号,因此只要信息位是确定的,校验位也可以唯一地确定.第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)+(6)+(7)+(10)+(11)(4)(5)+(6)+(7)(8)(9)+(10)+(11)被检测位：数据位检测位第4讲差错检测与校正海明码123456789101100100111010编码码字最终的海明码为什么此处是1?1,2,4,8是校验位!其余位是信息位.(8)(9)(10)(11)(1)(3)(5)(7)(9)(11)1010010100奇数个1偶数个1采用偶检验哦!第4讲差错检测与校正循环冗余码循环冗余校验英文全称为CyclicRedundancyCheck,简称CRC。工作原理：软件实现:多项式除法，将余式作为冗余信息传送。硬件实现:编码电路又称多项式校验第4讲差错检测与校正多项式除法多项式除法：被除多项式/除式（得出商和余式，余式作为校验码附在后面一起发送出去）第4讲差错检测与校正多项式除法多项式除法：被除多项式=除式*商+剩余多项式（换言之，被除多项式减去剩余多项式可以用除式整除）第4讲差错检测与校正CRC的工作原理（1）将要发送的二进制数序列看成是一个多项式。n位的数据序列对应n-1次多项式。P(x)=an-1xn-1+an-2xn-2+a1x+a0选定除式，被选作除式的多项式称为生成多项式，常见的生成多项式有：CRC-12：G(x)=x12+x11+x3+x2+x+1(城域网)CRC-16：G(x)=x16+x15+x2+1（广域网）CRC-CCITT：G(x)=x16+x12+x5+1（广域网）CRC-32：G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+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的工作原理（2）将P(x)乘以G(x)的最高幂次作为被除式，作多项式除式。除法采用“加法不进位，减法不借位”的规则，即相当于异或操作将所得到的余式多项式R(x)重新转换为二进制数，作为冗余码。将冗余码加在原传送数据后面，构成发送序列。接收方收到后，将接收序列用同样的生成多项式去除。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。第4讲差错检测与校正CRC的例子（1）要发送的二进制数序列为“1010001”，7位的数据序列对应5次多项式：P(x)=x6+x4+1选定的生成多项式为：G(x)=x4+x2+x+1（最高次数为4，相当于10111）•被除多项式为：P(x)x4＝x10+x8+x4（相当于10100010000）第4讲差错检测与校正CRC的例子（2）多项式除法后得到冗余码为1101，所以相应的数据发送序列为10100011101101000100001011111011111010001111110101011111010101111011111010101111101第4讲差错检测与校正CRC硬件实现R0R1Rr-1信息输入端g1g2gr-11...)(12211xgxgxgxxGrrrCRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。第4讲差错检测与校正CRC硬件实现R0R1R3信息输入端1)(24xxxxGR21000101R0R1R2R3输入输出:110100001GG11101001110101100011111011001010101111101101010100100001000100000111101第4讲差错检测与校正CRC的检错能力全部单个错全部离散的二位错全部奇数个错全部长度小于或等于K的突发错（K为生成多项式的最高幂次）以1-（1/2）K-1的概率检出长度为K+1位的突发错第4讲差错检测与校正课堂小结理解循环冗余码理解帧的构成第4讲差错检测与校正Homework预习第三章中的数据链路协议