《数据传输过程中差错产生的原因与性质》由会员分享，可在线阅读，更多相关《数据传输过程中差错产生的原因与性质（74页珍藏版）》请在金锄头文库上搜索。
1、第4章 数据 链路层本章学习要求 了解：数据传输过程中差错产生的原因与性质。掌握：数据链路层差错控制方法、循环冗余码编码原理。掌握：数据链路层的功能。掌握：停等协议、滑动窗口协议的工作原理。掌握：面向比特型数据链路层协议实例 HDLC。了解：Internet中的数据链路层协议。第4章 数据 链路层为什么需要数据链路层？物理层未解决的问题： 位流传输过程中不可避免会出现差错（电磁干扰，线路问题） 数据收发之间的速率匹配问题(不同设备处理速度不同)最主要的作用是通过一 些数据链路层协议(即 链路控制规程),在不太 可靠的物理链路上实现 可靠的数据传输.第4章 数据 链路层差错检测与校正：基本概念什
2、么是差错？ 在通信中接收端收到的二进制数位（码元）和发送 端实际发送的数据不一致。差错检测与校正：把差错控制在允许的范围内 。第4章 数据 链路层差错检测与校正：基本概念有两种不同的差错： 随机差错：随机热噪声 随机热噪声是信道固有的、持续存在的 码元的差错是独立的，和前后的码元无关 信噪比 突发差错：冲击噪声 外界的因素，持续时间短，突发性 传输中产生差错的主要原因 突发长度：突发差错发生的第一个码元到有错的最后一个 码元间所有码元的个数。比如4800bps信道上的10ms的冲击 噪声的突发长度为48比特第4章 数据 链路层误码率：衡量物理信道的质量差错控制编码：信息位(k)冗余位(r) 检
3、错码和纠错码检错码：自动发现差错纠错码：不仅能发现差错而且能够自动纠正 编码效率R：码字中信息位所占的比例 R=k/(k+r) 漏检率：信息位出错但是接收者无法了解到的概率差错检测与校正：基本概念第4章 数据 链路层差错检测与校正：基本概念差错控制：ARQ和FEC ARQ：Automatic Request for Repeat 接收方检测错误，通知发送方重传 双向信道，发送方缓存发送的数据 FEC：Forward Error Correction 接收方不仅可以检测错误，而且知道错误的位置 ，从而改正错误 采用纠错码，无需反向信道，无需重发，但编码 效率低,纠错设备复杂第4章 数据 链路层常
4、用的简单差错控制编码奇偶校验码：增加冗余位使得码字中1的个数为 奇数或者偶数，检错码 垂直奇偶校验 水平奇偶校验 水平垂直奇偶校验 垂直奇偶校验：发送的信息块分成定长为p位的若干段（一列）。每段增加一个（奇偶校验）冗余位ri ：第4章 数据 链路层垂直奇偶校验 编码效率： 能力：检测出每列（段）中所有奇数（1、3）个错突发错误的漏检率为50%!在发送和接收的过程中进行编解码 水平奇偶校验：降低突发错误的漏检率 对各个信息段的相应位横向进行编码第4章 数据 链路层水平奇偶校验 编码效率： 能力：各段同一位上的奇数个错长度小于等于p的突发差错编码和检测相比垂直校验而言实现要复杂一些第4章 数据 链
5、路层水平垂直奇偶校验 编码效率第4章 数据 链路层水平垂直奇偶校验能力 检测出： 所有3位或3位以下的错误、奇数位错 突发长度小于等于p+1的突发差错 很大一部分偶数位错：差错分布以致于某一行或 者某一列有奇数个差错 部分纠错功能： 可以纠正1比特错 信息块中恰好只有某一行和某一列有奇数位错时，可确 定为该行和该列的交叉处第4章 数据 链路层水平垂直奇校验的例子水平垂直奇校验的例子10001010字符1b1b2b3b4b5b6b7check11001011字符211011010字符310101011字符410001010字符510001010字符611101010字符700100001校验 字
6、符第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). 每个校验位的取值应使得包括自己在内的一些位的
7、集 合符合规定的奇偶性.(主要用于奇偶性校验)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(二进制编码是
8、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
9、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章 数据 链路层循环冗余码纠错码的编码效率较低，差错控制经 常采用检错码ARQ。循环冗余码CRC （Cyclic Redundancy Code ）是计 算机网络中使用最为广泛的检错码， 又称为多项式码。第4章 数据 链路层CRCCRC的工作原理（的工作原理（1 1）将要发送的二进制数序列看成是只有0和1两个系数的一个 多项式。n位的数据序列对应n-1
10、次多项式。如：二进制数 序列为“1010001”，7位的数据序列对应6次多项式：K(x)=x6+x4+1 选定除式G(x) ， 被选作除式的多项式称为生成多项式， 以下三个多项式已成为国际标准 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章 数据 链路层CRCCRC的工作原理（的工作原理（2 2）将
11、K(x)乘以 G(x)的最高幂次作为被除式， G(x)作多项式除式 XrK(x)=G(x)*商+R(x)（相应系数相除） 。除法采用“加法不进位， 减法不借位”的规则，即相当于异或操作R(x)作为冗余码，加在原传送数据后面:T(x)= XrK(x) +R(x)= G(x) *商+R(x) + R(x)= G(x) *商，构成发送 序列。 接收方收到后，将接收序列用同样的生成多项式去除T(x)/G(x)。若余式为零，则表示无差错；否则，说明传输过程中 出现了错误。第4章 数据 链路层CRCCRC的例子（的例子（1 1）要发送的二进制数序列为“1010001”，7 位的数据序列对应6次多项式：K(
12、x)=x6+x4+1 选定的生成多项式为：G(x)=x4 +x2 +x+ 1（最高次数为4，相当于10111） 被除多项式为：K(x)x4 x10+x8+x4 （相当于10100010000）第4章 数据 链路层CRCCRC的例子（的例子（2 2）多项式除法后得到冗余码为1101，所以相应的数 据发送序列为1010001 11011010001000010111110111 11010 0011111101010111110101011110111 11010 10111 1101第4章 数据 链路层CRCCRC硬件实现硬件实现R0R1Rr-1信息输入端g1g2gr-1CRC校验可以由软件或硬
13、件来实现，现多采用超大规模 集成电路芯片以硬件方式实现。第4章 数据 链路层CRCCRC硬件实现硬件实现R0R1R3信息输入端R21000101R0R1R2R3输入输出:11010000 1GG11101 001110 101100 011111 011001 010101 111101101010 100100 001000 100000111101第4章 数据 链路层CRC的检错能力（1）如果传输过程中出现差错：差错模式E(x)发送码 字和接收码字的半加，其中1的位置对应变化了信 息位的位置。若E(x)能被G(x)整除，则不能检测这样的错误第4章 数据 链路层CRC的检错能力（2）全部单个
14、错 全部离散的二位错 全部奇数个错 全部长度小于或等于r的突发错（ r为生成多 项式的最高幂次） 以1-（1/2）r-1的概率检出长度为r+1位的突发 错 以1-2-r的概率检出长度大于r+1位的突发错第4章 数据 链路层数据链路层的功能数据链路层的功能 链路管理 帧同步（帧定界） 流量控制 差错控制 帧的透明传输 寻址数据链路层协议 为实现数据链路控制功能而制定 的规程或协议。第4章 数据 链路层成成 帧帧数据链路层所传送的不再是原始的比特流，而应 具备相应的语法和语义，以达到可靠传输的功能 。 数据链路层将从网络层接收的分组（Packet)组成 帧后传送给物理层，通过物理层传送到对方的数
15、据链路层。 帧：数据链路层规定最小的数据传送逻辑单位 数据链路层协议要规定帧的类型与格式类型包括控制信息帧与数据信息帧等，格式 则规定帧所包含的域）。第4章 数据 链路层帧的基本组成帧的基本组成帧定界（开始与结束） 地址字段（用于寻址） 帧类型（或长度/控制）字段 数据 帧校验字段（差错控制）帧的开始地址帧类型或长度数据帧校验帧的结束上图只是帧的一般组成，不同的数据链路层协 议所规定的帧格式可能会与其存在微小的区 别。第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
