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

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