第3章数据链路层-1..ppt

《第3章数据链路层-1..ppt》由会员分享，可在线阅读，更多相关《第3章数据链路层-1..ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、计算机网络教程电子教案 笫五讲笫五讲 差错检测与校正差错检测与校正本讲内容第三章 数据链路层 3.1 3.1 数据链路层的功能数据链路层的功能 3.1.1 帧同步*3.1.2 差错控制 3.1.3 流量控制*3.1.4 链路管理*3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的检错码-循环冗余码3.2.3 常用的纠错码-海明码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。3.1 数据链路层的功能基本功能：将物理层提供的原始的传送比特流的可能出错的物理连接改造成为逻辑上无差错的数据链路最基本的服务就是将源机器网络层来的数据可靠地传输到相邻节点的

2、目标机网络层 要完成许多特定的功能主要有如何将比特组合成帧（frame）；处理传输中出现的差错；调节发送方的发送速率不至于使较慢的接收方不能承受，以及数据链路层连接的建立、维持和释放，称之为链路管理。3.1 数据链路层的功能差错控制由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。实现复杂一点的机制，要用：保留己发的帧：以便出错后重发 计时器(timer)：避免无限等待帧编号：保证每帧最终都能正确地交付给接收方网络层一次 本讲内容第三章 数据链路层 3.1 数据链路层的功能 3.1.1 帧同步*3.1.2 差错控制 3.1.3 流

3、量控制*3.1.4 链路管理*3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的检错码-循环冗余码3.2.3 常用的纠错码-海明码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。3.2 差错检测与校正传输差错的特性 为什么需要差错检测？有如下原因造成信号幅度、频率和相位的衰减或畸变（又称为失真）线路本身电气特性造成的随机噪声（又称热噪声）的影响电信号在线路上产生反射造成的回音效应相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等）3.2 差错检测与校正（续）传输差错的特性 l差错数据通信中，前面的原因就

4、会造成接收端收到的二进制数位（或称为码元）和发送端实际发送的二进制数位不一致由“1”变为“0”，或由“0”变为“1”l什么是差错检测与校正在一个实用的通信系统中一定要能发现（检测）这种差错 并采用措施纠正（校正），把差错控制在所能允许的尽可能小的范围内 3.2 差错检测与校正（续）传输差错的特性噪声分类：信道所固有的，持续存在的随机热噪声 由于外界特定的短暂原因所造成的冲击噪声噪声比较：随机错通常较少冲击噪声的幅度可以相当大，它是传输中产生差错的重要原因 3.2 差错检测与校正（续）传输差错的特性衡量一个信道质量的重要参数是误码率：通常用10的负若干次方来标志信道的误码率Pe。例子：在一条话频

5、线路中，误码率若为 ，则意味着平均十万位中有一位出错。差错控制最常用的方法是差错控制编码。3.2 差错检测与校正（续）传输差错的特性差错控制编码的原理：信息位：要发送的数据 冗余位：在向信道发送之前，先按照某种关系加上一定 发送与接收的过程：*发送时：信息位+冗余位构成码字发送；*接收时：收到码字后查看信息位和冗余位，并检查它们之间的关系（校验过程），以发现传输过程中是否有差错发生。3.2 差错检测与校正（续）传输差错的特性差错控制编码分类：检错码*指能自动发现差错的编码 纠错码*指不仅能发现差错而且能自动纠正差错的编码 3.2 差错检测与校正（续）传输差错的特性衡量编码性能的参数编码效率R*

6、意思是码字中信息位所占的比例*若码字中信息位为k位，编码时外加冗余位为r位，则编码后得到的码字长为n=k+r位。判定规律*编码效率越高，即R越大，则信道中用来传送信息码元的有效利用率就越高。3.2 差错检测与校正（续）传输差错的特性数据通信中，利用编码方法来进行差错控制的方式，基本上有两类：自动请求重发ARQ（Automatic ReQuest for repeat）*接收端检测出有差错时，就设法通知发送端重发，直到正确的码字收到为止。前向纠错FEC（Forward Error Correction）*接收端不但能发现差错，而且能确定二进制错码元的位置，从而就可以加以纠正。比较ARQ与FECA

7、RQFEC使用编码种类只要用检错码 必须用纠错码 是否需要双向信道 必须不需发送方是否需要缓冲区需要不需其他冗余位多（编码效率低）设备复杂3.2 差错检测与校正常用的检错码-循环冗余码将首先介绍最简单的检错码-奇偶校验码奇偶校验码奇偶校验码是通过增加冗余位来使得码字中“1”的个数保持奇或偶数的编码方法，是一种检错码 分类：*垂直奇偶校验*水平奇偶校验*水平垂直奇偶校验 3.2 差错检测与校正（续）常用的检错码-循环冗余码奇偶校验码奇偶校验码垂直奇偶校验垂直奇偶校验垂直奇偶校验是将整个发送的信息块分为定长p位的若干段（比如说q段），每段后面按“1”的个数为奇或偶数的规律加上一位奇偶位图3.1 垂

8、直奇偶校验3.2 差错检测与校正（续）常用的检错码-循环冗余码垂直奇偶校验垂直奇偶校验图中，pq位信息位（I11，I21，IP1，I12，Ipq）中，p位构成一段（即图中一列），共q段（即共有q列）。每段加上一位奇偶校验冗余位，即图中的ri(i=1,2,q)。若用偶校验，则若用奇校验，则编码效率：3.2 差错检测与校正（续）常用的检错码-循环冗余码垂直奇偶校验的例子垂直奇偶校验的例子通常，我们取一个字符的代码为一个信息位段，这种垂直奇偶校验有时也称为字符奇偶校验。在7位字符代码（即用7位二进制数位表示一个字符）中，p=7，编码效率为7/8。这种奇偶校验方法能检测出每列中的所有奇数位的错，但检测

9、不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于1/2。为了降低对突发错误的漏检率，人们又引进了水平奇偶检验。3.2 差错检测与校正（续）常用的检错码-循环冗余码奇偶校验码奇偶校验码水平奇偶校验水平奇偶校验水平奇偶检验。它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。（i=1,2,p）（i=1,2,p）编码效率为 图3.2 水平奇偶校验 3.2 差错检测与校正（续）常用的检错码-循环冗余码奇偶校验码奇偶校验码水平垂直水平垂直奇偶校验奇偶校验同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直水平垂直奇偶校验奇偶校验 图3.3 水平垂直奇偶

10、校验3.2 差错检测与校正（续）常用的检错码-循环冗余码水平垂直奇偶校验的编码效率为它能检测出所有3位或3位以下的错误（因为此时至少在某一行或某一列上为一位错）、奇数位错、突发长度p+1的突发错以及很大一部分偶数位错。3.2 差错检测与校正（续）常用的检错码-循环冗余码例子例子图中 、和 四位错，就可在第2行、第p行、第1列与第2列检测出来。自然，仍然会有一些偶数位错检测不出。例如，图中 、和 4位错，它们正好在一个矩阵的四角，对第2行、第p+1行、第1列和第q列来说都是两位错，因而检测不出来。3.2 差错检测与校正（续）常用的检错码-循环冗余码在计算机网络和数据通信中用得最广泛的检错码是一种

11、漏检率低得多也便于实现的循环冗余码CRC（Cyclic Redundancy Code）CRC码又称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。3.2 差错检测与校正（续）常用的检错码-循环冗余码例子例子代码1011011对应的多项式为 而多项式 对应的代码为110110 3.2 差错检测与校正（续）常用的检错码-循环冗余码k位要发送的信息位可对应于一个（k-1）次多项式K（x），r位冗余位对应于一个（r-1）次多项式R（x）。由k位信息位后面加上r位冗余位组成的n=k+r位码字则对应于一个（n-1）次多项式编码过程：已知K（

12、x）求R（x）的过程，在CRC码中可以通过找到一个特定的r次多项式G（x）（最高项 的系数为1）来实现用G（x）去除 K（x）得到的余式就是R（x）3.2 差错检测与校正（续）常用的检错码-循环冗余码例子例子信息位1010001 K(x)=冗余位1101 R(x)=码字10100011101 T(x)=使用模二除法模二除法：进行多项式除法时，只要对其相应系数相除就可以了。仍以上例中的K（x）=x6+x4+1为例（即信息位为1010001），若取r=4，G（x）=x4+x2+x+1（对应的代码为10111），则x4 K（x）=x10+x8+x4（对应的代码为10100010000），那末由除法来

13、求余式R（X）可这样做。（如右图所示）3.2 差错检测与校正（续）常用的检错码-循环冗余码这里，最后的余数1101就是冗余位，而R（x）=x3+x2+1。3.2 差错检测与校正（续）常用的检错码-循环冗余码按上述方法产生的循环码的性质：若G（x）含有（x+1）的因子，则能检测出所有奇数位错。若G（x）中不含有x的因子，或者换句话说，G（x）中含有常数项1，那末能检测出所有突发长度r的突发错 若G（x）中不含有x的因子，而且对任何0 e n1的e，除不尽xe+1，则能检测出所有的双错 若G（x）中不含有x的因子，则对突发长度为r+1的突发错误的漏检率为2-(r-1)若G（x）中不含有x的因子，则

14、对突发长度b大于r+1的突发错误的漏检率为2-r3.2 差错检测与校正（续）常用的检错码-循环冗余码由以上性质，推出结论：若适当选取G（x），使其含有（x+1）因子、常数项不为0、且周期大于等于n，那末，由此G（x）作为生成多项式产生的CRC码可检测出所有的双错、奇数位错和突发长度小于等于r的突发错以及（12-(r-1)）的突发长度为r+1的突发错和（12-r）的突发长度大于r+1的突发错误 若具体取r=16，则能检测出所有双错、奇数位错、突发长度小于等于16的突发错以及1-2-15（约为99.997%）的突发长度为17的突发错和1-2-16（约为99.998%）的突发长度大于等于18的突发错

15、 3.2 差错检测与校正（续）常用的检错码-循环冗余码除以G（x）的运算易于用移位寄存器和半加器来实现 R0R1Rr-1g1g2gr-1码字输出端信息输入端输出开关图3.5 CRC码的编码电路3.2 差错检测与校正（续）常用的检错码-循环冗余码取G（x）=x4+x2+x+1时的编码电路，图中信息位为7位（k=7），经过7次移位后在R3、R2、R1 和R0中就产生了冗余位1、1、0和1。输出开关朝上拨后再经过4次移位，该冗余位就紧接在信息位后面作为码字的一部分输出了。接收端校验的过程，也是除以G（x）的过程，实现的电路是类似的。不过要多加一个与门来判别余式是否为全零，从而决定是否有差错 图3.6 G（x）=x4+x2+x+1的编码电路练习题3.3 某信道误码率为10-5，每帧长度为10kbits，那末 (1)若差错都是单个错，则在该信道上传送的帧的平均出错率是多少？(2)若差错大多为突发错，平均突发长度为100bits，则在该信道上传送的帧的平均出错率是多少？3.14 已知循环冗余码的生成多项式G（X）=x5+x4+x+1，若 接 收 方 收 到 的 码 字 为1010110001101，问传输中是否有差错？