第4讲 差错 检测与校正第第4 4讲讲 差错检测与校正差错检测与校正课时授课计划课 程 内 容第4讲 差错 检测与校正内容：同步的基本概念海明码循环冗余码目的与要求：掌握帧同步的基本概念；掌握海明码编码原理；掌握循环冗余码编码原理；重点与难点：重点：循环冗余码、海明码；难点：循环冗余码。第4讲 差错 检测与校正课堂讨论： 海明码？循环冗余码？ 现代教学方法与手段：投影PowerPoint幻灯课件 复习（提问）：PCM的工作过程？常用的物理层联网设备有哪些？第4讲 差错 检测与校正第第3 3章章 数据链路层数据链路层 3.1 差错检测与校正 3.2 数据链路层的功能第4讲 差错 检测与校正 为什么需要数据链路层？物理层未解决的问题： 位流传输过程中不可避免会出现差错。（电磁干扰，线路问题） 数据收发之间的速率匹配问题(不同设备处理速度不同)最主要的作用是通过一 些数据链路层协议(即 链路控制规程),在不太 可靠的物理链路上实现 可靠的数据传输.第4讲 差错 检测与校正数据链路层的功能数据链路层的功能 实现实现实现实现 两个相两个相邻邻邻邻的机器的机器间间间间的无差的无差错错错错的的 传输传输传输传输 。 利用物理利用物理层层层层提供的提供的原始比特流传输原始比特流传输服服 务务务务，向网，向网络层络层络层络层 提供提供可靠的数据传输可靠的数据传输 服服务务务务。第4讲 差错 检测与校正数据链路层的问题数据链路层的问题 如何识别相邻的机器如何识别相邻的机器-编址与寻址编址与寻址 如何实现可靠的数据传输如何实现可靠的数据传输-差错控制和流量控制差错控制和流量控制 如何识别数据流的开始与结束如何识别数据流的开始与结束-成帧成帧第4讲 差错 检测与校正成成 帧帧 数据链路层所传送的不再是原始的比特流，而应 具备相应的语法和语义，以达到可靠传输的功能 。 数据链路层将从网络层接收的分组（Packet)组成 帧后传送给物理层，通过物理层传送到对方的数 据链路层。 帧：数据链路层规定最小的数据传送逻辑单位 数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式 则规定帧所包含的域）。第4讲 差错 检测与校正帧的基本组成帧的基本组成域域 帧定界（开始与结束） 地址字段（用于寻址） 帧类型（或长度/控制）字段 数据 帧校验字段（差错控制）第4讲 差错 检测与校正帧的示意图帧的示意图上图只是帧的一般组成，不同的数据链 路层协议所规定的帧格式可能会与其存 在微小的区别。帧的开始地址帧类型或长度数据帧校验帧的结束第4讲 差错 检测与校正帧的地址帧的地址帧中的地址属于物理或硬件地址帧中的地址属于物理或硬件地址 网卡地址网卡地址( (局域网局域网) ) 链路标识链路标识( (广域网广域网) ) 用于设备或机器的物理寻址用于设备或机器的物理寻址第4讲 差错 检测与校正帧的定界帧的定界定界就是标识帧的开始与结束 常用的帧定界方法：带字符填充的首尾界符法 带位填充的首尾标志法 字符计数法第4讲 差错 检测与校正首尾界符法首尾界符法 每一帧以ASCII字符序列DLE STX开始，以 DLE ETX结束。 DLE为Data Link Escape 的缩写，STX意味着 Start of Text， ETX代表 End of Text。 其缺点是成帧完全依赖于8位字符STX,A,B,GOOD,BYE,ETX A,B,GOOD,BYE 数据组帧第4讲 差错 检测与校正字符填充字符填充 在首尾界符法中，由于数据中可能会出现DLE STX或DLE ETX，从而干扰帧的正常定界 字符填充法可用于解决上述问题。即发送端在数 据中所遇到的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) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (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(a) (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讲 差错 检测与校正5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 65 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6计数计数计数第1帧 5个字符第2帧 5个字符第3帧 8个字符发送:接收:第1 帧正确!第2 帧不正确!问题: 出错之后,接收方 与发送方不同步! 无法确定下一帧 的开始位置.请求 重传也没有用处, 因为发送方不知 道应该回跳多少 字符开始重传.7出错!11个字符计数?一般地,在数据链路协议中使用字符计数与其它方法相结合来 提高可靠性.第4讲 差错 检测与校正差错检测与校正n基本概念 n常用的简单差错控制编码 n海明码 n循环冗余码第4讲 差错 检测与校正基本概念 差错：指通过通信信道后接收数据与发 送数据不一致的现象 产生差错原因： 热噪声- 随机错误 冲击噪声- 突发错误第4讲 差错 检测与校正基本概念 误码率： 纠错码：发现并纠正错误 检错码：发现错误，但不能自动纠正错 误需要通过反馈重发来纠错 编码效率第4讲 差错 检测与校正基本概念 差错控制的编码方式： 自动请求重发ARQ(automatic request for repeat) 向前纠错FEC(Foeward Error Correcytion)第4讲 差错 检测与校正常用的简单差错控制编码 水平奇偶校验：在面向字符的数据传输中，在每个字符的在面向字符的数据传输中，在每个字符的7 7位信息码位信息码 后附加一个校验位后附加一个校验位0 0或或1 1，使整个字符中，使整个字符中“1”1”的个数构成的个数构成 奇数个（奇校验）或偶数个（偶校验）。奇数个（奇校验）或偶数个（偶校验）。 垂直奇偶校验：也叫组校验，在发送字符块的末尾附加一个校验字 也叫组校验，在发送字符块的末尾附加一个校验字 符，且该字符中的第符，且该字符中的第i i位是针对所有字符的第位是针对所有字符的第i i位所进行位所进行 的校验。的校验。 垂直水平奇偶校验垂直奇偶校验和水平奇偶校验技术的综合。对每个 垂直奇偶校验和水平奇偶校验技术的综合。对每个 字符作垂直校验，对整个字符块作水平校验。字符作垂直校验，对整个字符块作水平校验。第4讲 差错 检测与校正奇校验的例子奇校验的例子10001010字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100000校验 字符第4讲 差错 检测与校正海明码1. 海明码 (1)海明距离及意义 两个码字中不同的位数的个数称为海明距离,简 称H距离1 0 0 0 1 0 0 11 0 1 1 0 0 0 1求H距离的方法主要有:异或运算 海明距离的意义是:假如两个码字具有海明距离d , 则需要d 个 位差错才能将其中一个码字转换成另一个.H=3第4讲 差错 检测与校正海明码(2)海明码算法 将码字数内的位从最左边开始按顺序依次编号,第1位 是1号,第2位是2号, 第n位是n号.编号为2的幂的位 (1号位,2号位,4号位,8号位等)是校验位,其余的位填入 m 位数据(2 r n+1). 每个校验位的取值应使得包括自己在内的一些位的集 合符合规定的奇偶性.(主要用于奇偶性校验)1 2 3 4 5 6 7 8 9 10 11 12校验位第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讲 差错 检测与校正海明码1 2 3 4 5 6 7 8 9 10 11 0 0 1 0 0 1 1 1 0 1 0 编码码字最终的 海明码为什么此 处是1?1,2,4,8是校验位! 其余位是信息位.(8) (9)(10)(11) (1) (3)(5)(7)(9)(11)1 0 1 0 0 1 0 1 0 0奇数个1偶数个1采用偶 检验哦 !第4讲 差错 检测与校正循环冗余码 循环冗余校验英文全称为Cyclic Redundancy Check , 简称CRC。 工作原理： 软件实现:多项式除法，将余式作为冗余信息 传送。 硬件实现: 编码电路 又称多项式校验第4讲 差错 检测与校正多项式除法多项式除法多项式除法：被除多项式/除式（得出商和余式，余式作为校验码附 在后面一起发送出去）第4讲 差错 检测与校正多项式除法多项式除法多项式除法：被除多项式=除式*商+剩余多项式（换言之，被除多项式减去剩余多 项式可以用除式整除）第4讲 差错 检测与校正CRCCRC的工作原理（的工作原理（1 1） 将要发送的二进制数序列看成是一个多项式 。n位的数据序列对应n-1次多项式。P(x)=an-1xn-1 +an-2xn-2 +