笫五讲差错检测与校正ppt课件

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.2.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.1 数据链路层的功能根本功能：将物理层提供的原始的传送比特流的能够出错的物理衔接改呵斥为逻辑上无过失的数据链路最根本的效力就是将源机器网络层来的数据可靠地传输到相邻节点的目的机网络层 要完成许多特定的功能主要有如

2、何将比特组合成帧frame；处置传输中出现的过失；调理发送方的发送速率不至于使较慢的接纳方不能接受，以及数据链路层衔接的建立、维持和释放，称之为链路管理。 本讲内容第三章 数据链路层 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.2.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.1.2 过失控制由过失控制码产生的校验和可以检查出一帧在传输中能否发生了错误。一旦检查出

3、错误后，通常采用反响重发的方法来纠正错误。 实现复杂一点的机制，要用：保管己发的帧：以便出错后重发 计时器 (timer)：防止无限等待帧编号 ：保证每帧最终都能正确地交付给接纳方网络层一次 本讲内容第三章 数据链路层 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.2.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.2 过失检测与校正 为什么需求过失检测？ 有如下缘由

4、呵斥信号幅度、频率和相位的衰减或畸变又称为失真 线路本身电气特性呵斥的随机噪声又称热噪声的影响 电信号在线路上产生反射呵斥的回音效应 相邻线路间的串扰以及各种外界要素如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的动摇等 3.2 过失检测与校正续 过失： 数据通讯中，前面的缘由就会呵斥接纳端收到的二进制数位或称为码元和发送端实践发送的二进制数位不一致 由“1变为“0，或由“0变为“1 什么是过失检测与校正 在一个适用的通讯系统中一定要能发现检测这种过失 并采用措施纠正校正，把过失控制在所能允许的尽能够小的范围内 本讲内容第三章 数据链路层 3.1 数据链路层的功能 3.1.1 帧同步*

5、3.1.2 过失控制 3.1.3 流量控制* 3.1.4 链路管理* 3.2 过失检测与校正 3.2.1 传输过失的特性 3.2.2 常用的简单过失控制编码 3.2.3海明码 3.2.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.2.1 传输过失的特性噪声分类：信道所固有的，继续存在的随机热噪声 由于外界特定的短暂缘由所呵斥的冲击噪声噪声比较：随机错通常较少冲击噪声的幅度可以相当大 ，它是传输中产生过失的重要缘由 3.2.1 传输过失的特性续衡量一个信道质量的重要参数是误码率：通常用10的负假设干次方来标志信道的误码率Pe。 例子：在一条话频线

6、路中，误码率假设为 ，那么意味着平均十万位中有一位出错。 过失控制最常用的方法是过失控制编码。 Pe =发生差错的码元数接收的总码元数510过失控制编码的原理：信息位：要发送的数据 冗余位：在向信道发送之前，先按照某种关系加上一定 发送与接纳的过程：发送时：信息位+冗余位构成码字发送；接纳时：收到码字后查看信息位和冗余位，并检查它们之间的关系校验过程，以发现传输过程中能否有过失发生。 过失控制编码分类：检错码指能自动发现过失的编码 纠错码指不仅能发现过失而且能自动纠正过失的编码 衡量编码性能的参数编码效率R 意思是码字中信息位所占的比例 假设码字中信息位为k位，编码时外加冗余位为r位，那么编码

7、后得到的码字长为n = k + r位。 断定规律编码效率越高，即R越大，那么信道中用来传送信息码元的有效利用率就越高。 rkknkR3.2.1 传输过失的特性续数据通讯中，利用编码方法来进展过失控制的方式，根本上有两类：自动恳求重发ARQAutomatic ReQuest for repeat接纳端检测出有过失时，就设法通知发送端重发，直到正确的码字收到为止。 前向纠错FECForward Error Correction接纳端不但能发现过失，而且能确定二进制错码元的位置，从而就可以加以纠正。 比较ARQ与FECARQFEC运用编码种类只需用检错码 必需用纠错码 能否需求双向信道 必需不需发送

8、方能否需求缓冲区需求不需其他冗余位多编码效率低设备复杂小结两种编码方式 除非在单向传输或实时要求特别高FEC由于不需求重发，实时性较好等场所外，数据通讯中运用更多的还是ARQ过失控制方式。 自然，也可以将上述两者混合运用，即当码字中的过失个数在纠正才干以内时，直接进展纠正；当码字中的过失个数超出纠正才干时，那么检出过失令其重发来纠正过失。 本讲内容第三章 数据链路层 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.2

9、.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.2.2 常用的简单过失控制编码将引见奇偶校验码、定比码和正反码等三种较为适用的简单编码 奇偶校验码奇偶校验码是经过添加冗余位来使得码字中“1的个数坚持奇或偶数的编码方法，是一种检错码 分类：垂直奇偶校验程度奇偶校验程度垂直奇偶校验 奇偶校验码垂直奇偶校验 垂直奇偶校验是将整个发送的信息块分为定长p位的假设干段比如说q段，每段后面按“1的个数为奇或偶数的规律加上一位奇偶位图3.1 垂直奇偶校验垂直奇偶校验 图中，pq位信息位I11，I21，IP1，I12，Ipq中，p位构成一段即图中一列，共q段即共

10、有q列。每段加上一位奇偶校验冗余位，即图中的ri(i= 1,2,q)。假设用偶校验，那么 假设用奇校验，那么 编码效率：1ppRpiiiiIIIr21121piiiiIIIr例子 通常，我们取一个字符的代码为一个信息位段，这种垂直奇偶校验有时也称为字符奇偶校验。 在7位字符代码即用7位二进制数位表示一个字符中，p = 7，编码效率为7 / 8 。这种奇偶校验方法能检测出每列中的一切奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因此对过失的漏检率接近于1 / 2 。 为了降低对突发错误的漏检率，人们又引进了程度奇偶检验。 垂直奇偶校验垂直奇偶校验 字母前

11、7行为对应字母的ASCII码，最后一行是垂直奇校验编码粗体abcdefg校验位1 1 0 0 0 0 11 1 0 0 0 1 01 1 0 0 0 1 11 1 0 0 1 0 01 1 0 0 1 0 11 1 0 0 1 1 01 1 0 0 1 1 10 0 1 1 1 1 1程度垂直奇偶校验程度垂直奇偶校验 字母最后一行是垂直奇校验编码，最后一列是程度奇校验编码均为粗体abcdefg校验位1 1 0 0 0 0 1 01 1 0 0 0 1 0 01 1 0 0 0 1 1 11 1 0 0 1 0 0 01 1 0 0 1 0 1 11 1 0 0 1 1 0 11 1 0 0 1

12、 1 1 00 0 1 1 1 1 1 0奇偶校验码程度奇偶校验 程度奇偶检验。它是对各个信息段的相应位横向进展编码，产生一个奇偶校验冗余位。 i=1,2,p i=1,2,p 编码效率为 iqi2i1iIIIr1iqi2i1iIIIr图3.2 程度奇偶校验 1qqR奇偶校验码程度垂直奇偶校验 同时进展程度奇偶校验和垂直奇偶校验就构成程度垂直奇偶校验 1qp,1q2,1q1,q1,p1,2p1,1p1q1,ppj2j1jj1,piqi2i11i,qrrrrrrrq1jIIIrp1,2,iIIIr ),2,( ), ( 图3.3 程度垂直奇偶校验奇偶校验码程度垂直奇偶校验续 程度垂直奇偶校验的编码

13、效率为 它能检测出一切3位或3位以下的错误由于此时至少在某一行或某一列上为一位错、奇数位错、突发长度p+1的突发错以及很大一部分偶数位错。 ) 1)(1(qppqR例子 图中 、 、 和 四位错，就可在第2行、第p行、第1列与第2列检测出来。自然，依然会有一些偶数位错检测不出。例如，图中 、 、 和 4位错，它们正好在一个矩阵的四角，对第2行、第p+1行、第1列和第q列来说都是两位错，因此检测不出来。 11IqI122IpqI21IqI21 , 1pIqpI, 1奇偶校验码小结 程度垂直奇偶校验不仅可检错，还可用来纠正部分过失。 垂直奇偶校验有时又称为纵向奇偶校验 程度奇偶校验有时又称为横向奇

14、偶校验 程度垂直奇偶校验那么又称为纵横奇偶校验 定比码 每个码字中均含有一样数目的“1码字长一定，“1的数目一定后，所含“0的数目也就必然一样。正由于每个码字中“1的个数与“0的个数之比坚持恒定，故得此名，有时也称为恒比码 假设n位码字中“1的个数恒定为m，还可称为“n中取m码。这种码在检测时，只需计算接纳码字中“1的数目，就能知道能否有过失 在国际无线电报通讯中广泛采用的就是7中取3定比码。这种码字长为7位，规定总有3个“1 。共有 种码字，可用来分别代表性26个英文字母和其它符号 NoImage3512356737）（）（C定比码续 定比码n中取m的编码效率为 对于7中取3码来说， 其编码

15、效率是不高的。但是，定比码能检测出全部奇数位错以及部分偶数位错。实践上，除了码字中“1变成“0和“0变成“1成对出现的过失外，一切其它过失都能被检测出来，检错才干还是很强的 假设信源产生的是随机的二进制数字序列，就不能采用定比码了。 73. 0712. 5735log2R正反码 一种简单的可以纠正过失的编码，其中冗余位的个数与信息位个数一样。冗余位与信息位或者完全一样或者完全相反，由信息位中“1的个数来决议。 例如电报通讯中常用五单位电码编成正反码的规那么如下：k=5,r=k=5,n=k+r=10；当信息位中有奇数个“1时，冗余位就是信息位的简单反复；当信息位中有偶数个“1时，冗余位是信息位的

16、反码。详细说来，假设信息位为01011，那么码字为0101101011；假设信息位为10010，那么码字为1001001101。 接纳端的校验方法为：先将接纳码字中信息位和冗余位按位半加，得到一个k位的合成码组对上述详细的码长为10的正反码来说，就是得到一个5位的合成码组。 假设接纳码字中的信息位中有奇数个“1，那么就取合成码组为校验码组；假设接纳码字中信息位中有偶数个“1，那么取合成码组的反码作为校验码组。 正反码续校验码组过失情况全“0无过失4个“1、1个“0信息位中有一位过失，其位置对应于校验码组中“0的位置 4个“0、1个“1 冗余位中有一位过失，其位置对应于校验码组中“1的位置 其它

17、情况 过失在两位或两位以上 例子 发送码字为0101101011，传输中无过失，那么合成码组为01011 01011=00000，由于接纳码字的信息位中有3个“1，故00000就是校验码组，查前表知无过失。 假设传输中发生了一位过失，接纳端收到1101101011，那么合成码组为11011 01011=10000，由于接纳的码字中信息位中有4个“1，故校验码组为01111。查前表知，信息位的第1位错，故可将接纳到的1101101011纠正为0101101011。 假设传输中发生了两位错，接纳端收到1101111011，那么合成码组为11011 11011=00000，而此时校验码组为11111

18、，查前表可判别出为两位或两位以上的过失。例子续 又如，假设传输中发生了四位错，接纳端收到1101011010，那么合成码组为11010 11010=00000，而此时校验码组也为00000，查表会以为是无过失，也就是说对这种过失是漏捡了。 再如，假设传输中发生了三位错，接纳端收到1101011011，那么合成码组为11010 11011=00001，此时校验码组也为00001，查表会以为是冗余位中有一位过失，其位置对应于校验码组中“1的位置，从而将其误纠为1101011010。 实践上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是过失控制编码的

19、重要技术目的，当然是越小过失控制才干越强。 正反码的编码效率较低，只需1/2。但其过失控制才干还是较强，如上述长度为10的正反码，能检测出全部两位过失和大部分两位以上的过失，并且还具有纠正一位过失的才干。由于正反码的编码效率较低，只能用于信息位较短的场所。 下面将引见两种编码效率较高的，且过失控制才干较强的纠错和检错码。 本讲内容第三章 数据链路层 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.2.4 循环冗余码*

20、是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.2.3海明码 引见 由R. Hamming在1950年初次提出 也是一种可以纠正一位过失的编码，但当信息位足够长时，它的编码效率要比正反码高得多 回想奇偶校验，假设信息位为k=n-1位 ，加上一位偶校验位a0，构成一个n位的码字 。在接纳端校验时，可按关系式假设S=0，那么无错；假设S=1，那么有错。上式可称为监视关系式，S称为校正因子121aaann0121aaaann12rkr0121aaaaSnn海明码续 在奇偶校验情况下，只需一个监视关系式，一个校正因子，其取值只需两种0或1，分别代表了无错和有错两种情况，

21、而不能指出过失所在的位置 假设添加冗余位，也相应地添加监视关系式和校正因子，就能区分更多的情况。 信息位为k位，添加r位冗余位，构成n=k+r位码字 。假设希望用r个监视关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错，那么要求 或 12 nr12rkr例子 以k = 4为例来阐明，要满足前述不等式，那么r3。现取r = 3，那么n = k + r = 7。 在4位信息位 后面加上3位冗余位 ，构成7位码字 。其a2、a1和a0分别由4位信息位中某几位半加得到。那么在校验时，a2、a1和a0就分别和这些位半加构成三个不同的监视关系式。在无错时，这三个关系式的值S2、S 1和S0

22、全为“0。假设a2错，那么S2 = 1，而S1=S0=0；假设a1错，那么S1=1,而S2=S0=0；假设a0错，那么S0=1，而S2=S1=0。S2 S1 S0这三个校正因子其它4种编码的值可用来区分a3、a4、a5或a6一位错。 3456aaaa012aaa0123456aaaaaaa例子续012SSS a2、a4、a5或a6的一位错都应使S2 = 1,由此可以得到监视关系式 000001010100011101110111错码位置无错2a1a0a3a4a5a6a65422aaaaS65311aaaaS64300aaaaS例子续 在发送端编码时，信息位a6、a5、a4和a3的值取决于输入信

23、号，是随机的。冗余位a2、a1和a0的值应根据信息位的取值按监视关系式来决议，使上述三式中的S2、S1和S0取值为零 由此可求得 知信息位后，按此三式即可算出各冗余位。对于各种信息位算出的冗余位如后表 6542aaaa6531aaaa6430aaaa信息位冗余位信息位冗余位00000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111113456aaaa012aaa3456aaaa012aaa例子续在接纳端收到每个码字后，按监视关系式算出

24、S2、S1和S0，假设为全“0那么以为无错。假设不全为“0，在一位错的情况下，可查表来断定是哪一位错，从而纠正之。例如码字0010101传输中发生一位错，在接纳端收到的为0011101，代入监视关系式可算得S2=0、S1=1和S0=1，由查表得S2 S1 S0=011对应于a3错，因此可将0011101纠正为0010101。但是，假设码字0010101传输中发生两位错，在接纳端收到的为0011111，代入监视关系式可算得S2=0、S1=0和S0=1，查表得S2 S1 S0=001对应于a0错，从而会将0011111纠正为0011110，这就是误纠的情况。=167+4+1=1242r2r2再如，

25、假设码字0010101传输中发生三位错，在接纳端收到的为0101101，代入监视关系式可算得S2=0、S1=0和S0=0，查表可得S2 S1 S0=000对应于无错，从而以为传输中无过失，这就是漏检的情况。我们这个例子中正好 =k+r+1，假设 k+r+1那么在查表中还有多余的位置可用来表示两位以上的错误，就可降低漏检率了。比如，假设k=7，那么满足 k+r+1的最小r为4。此时 r2海明码续上述例子中，k=4的海明码的编码效率为4/7；假设k=7，那么编码效率为7/11。由此可见，信息位长度越长时编码效率越高。只能纠正一位错，假设用在纠正传输中出现突发性过失时可以采用下述方法：将延续P个码字

26、排成一个矩阵，每行一个码字图3.4 海明码用于纠正突发错误的情况本讲内容第三章 数据链路层 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.2.4 循环冗余码*是要求同窗了解的，这些内容在本电子教案中并未讲解而是要求同窗本人阅读教材。 3.2.4 循环冗余码 在计算机网络和数据通讯中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码CRCCyclic Redundancy Code CRC码又称为多项式码。这

27、是由于任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。2循环冗余码循环冗余码CRC CRCCyclic Redundancy Check是在所传送的k位信息后面附加一 个r位检验序列。 任务原理： 设f(x)为一个k阶多项式, 其系数是待发送信息的比特序列； 例如，待发送的信息序列是1010001101，那么对应f(x)=x9+x7+x3+x2+1 k=9)。 G(x)为一个r 阶的生成多项式，由发收双方预先商定。Gx)有国际规范。 CRC码的产生：码的产生： 检验序列的生成：检验序列的生成： 用用xr f(x)除以除以G(x), 得余式得余式R(x)，其系数序列即，其系数序列即是检验序列。是检验序列。 进展除法运算时，采用模进展除法运算时，采用模2算术，即加法不进位，算术，即加法不进位，减法不借位异或运算。减法不借位异或运算。 例如，生成多项式G(x)= x5+x4+x2+1, 即110101 r=5) x5 f(x)=x14+x12+x8+