笫五讲差错检测与校正new

《笫五讲差错检测与校正new》由会员分享，可在线阅读，更多相关《笫五讲差错检测与校正new（53页珍藏版）》请在金锄头文库上搜索。

1、数据通信与计算机网络（第二版）电子教案 笫五讲笫五讲 差错检测与校正差错检测与校正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 循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。 23.1 数据链路层的功能基本功能：将物理层提供的原始的传送比特流的可能出错的物理连接改造成为逻辑上无差错的数据链路最基本的服务就是将源机器网络层来

2、的数据可靠地传输到相邻节点的目标机网络层 要完成许多特定的功能主要有如何将比特组合成帧（frame）；处理传输中出现的差错；调节发送方的发送速率不至于使较慢的接收方不能承受，以及数据链路层连接的建立、维持和释放，称之为链路管理。 3本讲内容第三章 数据链路层 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 循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。 43.1

3、.2 差错控制由差错控制码产生的校验和可以检查出一帧在传输中是否发生了错误。一旦检查出错误后，通常采用反馈重发的方法来纠正错误。 实现复杂一点的机制，要用：保留己发的帧：以便出错后重发 计时器 (timer)：避免无限等待帧编号 ：保证每帧最终都能正确地交付给接收方网络层一次 5本讲内容第三章 数据链路层 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 循环冗余码*是要求同学了解的，这些内容在本

4、电子教案中并未讲解而是要求同学自己阅读教材。 63.2 差错检测与校正 为什么需要差错检测？有如下原因造成信号幅度、频率和相位的衰减或畸变（又称为失真）线路本身电气特性造成的随机噪声（又称热噪声）的影响电信号在线路上产生反射造成的回音效应相邻线路间的串扰以及各种外界因素（如大气中闪电、开关的跳火、外界强电流磁场的变化和电源的波动等） 73.2 差错检测与校正（续）差错：数据通信中，前面的原因就会造成接收端收到的二进制数位（或称为码元）和发送端实际发送的二进制数位不一致由“1”变为“0”，或由“0”变为“1” 什么是差错检测与校正在一个实用的通信系统中一定要能发现（检测）这种差错 并采用措施纠正

5、（校正），把差错控制在所能允许的尽可能小的范围内 8本讲内容第三章 数据链路层 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 循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。 93.2.1 传输差错的特性噪声分类：信道所固有的，持续存在的随机热噪声 由于外界特定的短暂原因所造成的冲击噪声噪声比较：随机错通常较少冲击噪声的幅度可以相当大 ，它是传输中产生差错

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

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

8、码元的位置，从而就可以加以纠正。 15比较ARQ与FEC16小结两种编码方式除非在单向传输或实时要求特别高（FEC由于不需要重发，实时性较好）等场合外，数据通信中使用更多的还是ARQ差错控制方式。 自然，也可以将上述两者混合使用，即当码字中的差错个数在纠正能力以内时，直接进行纠正；当码字中的差错个数超出纠正能力时，则检出差错令其重发来纠正差错。 17本讲内容第三章 数据链路层 3.1 数据链路层的功能 3.1.1 帧同步* 3.1.2 差错控制 3.1.3 流量控制* 3.1.4 链路管理* 3.2 差错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的简单差错控制编码常用的简单差错控

9、制编码 3.2.3海明码 3.2.4 循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。 183.2.2 常用的简单差错控制编码将介绍奇偶校验码、定比码和正反码等三种较为实用的简单编码 奇偶校验码奇偶校验码是通过增加冗余位来使得码字中“1”的个数保持奇或偶数的编码方法，是一种检错码 分类：*垂直奇偶校验*水平奇偶校验*水平垂直奇偶校验 19奇偶校验码垂直奇偶校验垂直奇偶校验是将整个发送的信息块分为定长p位的若干段（比如说q段），每段后面按“1”的个数为奇或偶数的规律加上一位奇偶位图3.1垂直奇偶校验20垂直奇偶校验图中，pq位信息位（I11，I21，IP1，

10、I12，Ipq）中，p位构成一段（即图中一列），共q段（即共有q列）。每段加上一位奇偶校验冗余位，即图中的ri(i= 1,2,q)。若用偶校验，则若用奇校验，则编码效率：21例子通常，我们取一个字符的代码为一个信息位段，这种垂直奇偶校验有时也称为字符奇偶校验。 在7位字符代码（即用7位二进制数位表示一个字符）中，p = 7，编码效率为7 / 8 。这种奇偶校验方法能检测出每列中的所有奇数位的错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的概率接近于相等，因而对差错的漏检率接近于1 / 2 。为了降低对突发错误的漏检率，人们又引进了水平奇偶检验。 22垂直奇偶校验垂直奇偶校验字母

11、前7行为对应字母的ASCII码，最后一行是垂直奇校验编码（粗体）abcdefg校验位11000011100010110001111001001100101110011011001110 0 1 1 1 1 123水平垂直奇偶校验水平垂直奇偶校验字母最后一行是垂直奇校验编码，最后一列是水平奇校验编码（均为粗体）abcdefg校验位1100001 01100010 01100011 11100100 01100101 11100110 11100111 00 0 1 1 1 1 1 024奇偶校验码水平奇偶校验水平奇偶检验。它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。 （i=1,

12、2,p） （i=1,2,p）编码效率为 图3.2水平奇偶校验25奇偶校验码水平垂直奇偶校验同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直水平垂直奇偶校验奇偶校验 图3.3水平垂直奇偶校验26奇偶校验码水平垂直奇偶校验（续）水平垂直奇偶校验的编码效率为它能检测出所有3位或3位以下的错误（因为此时至少在某一行或某一列上为一位错）、奇数位错、突发长度p+1的突发错以及很大一部分偶数位错。 27例子图中 、 、 和 四位错，就可在第2行、第p行、第1列与第2列检测出来。自然，仍然会有一些偶数位错检测不出。例如，图中 、 、 和 4位错，它们正好在一个矩阵的四角，对第2行、第p+1行、第1列和第q列来

13、说都是两位错，因而检测不出来。 28奇偶校验码小结水平垂直奇偶校验不仅可检错，还可用来纠正部分差错。 垂直奇偶校验有时又称为纵向奇偶校验 水平奇偶校验有时又称为横向奇偶校验 水平垂直奇偶校验则又称为纵横奇偶校验 29定比码每个码字中均含有相同数目的“1”（码字长一定，“1”的数目一定后，所含“0”的数目也就必然相同）。正由于每个码字中“1”的个数与“0”的个数之比保持恒定，故得此名，有时也称为恒比码 若n位码字中“1”的个数恒定为m，还可称为“n中取m”码。这种码在检测时，只要计算接收码字中“1”的数目，就能知道是否有差错 在国际无线电报通信中广泛采用的就是7中取3定比码。这种码字长为7位，规

14、定总有3个“1” 。共有 种码字，可用来分别代表性26个英文字母和其它符号 30定比码（续）定比码（n中取m）的编码效率为 对于7中取3码来说，其编码效率是不高的。但是，定比码能检测出全部奇数位错以及部分偶数位错。实际上，除了码字中“1”变成“0”和“0”变成“1”成对出现的差错外，所有其它差错都能被检测出来，检错能力还是很强的 若信源产生的是随机的二进制数字序列，就不能采用定比码了。 31正反码一种简单的能够纠正差错的编码，其中冗余位的个数与信息位个数相同。冗余位与信息位或者完全相同或者完全相反，由信息位中“1”的个数来决定。例如电报通信中常用五单位电码编成正反码的规则如下：k=5,r=k=

15、5,n=k+r=10；当信息位中有奇数个“1”时，冗余位就是信息位的简单重复；当信息位中有偶数个“1”时，冗余位是信息位的反码。具体说来，若信息位为01011，则码字为0101101011；若信息位为10010，则码字为1001001101。 接收端的校验方法为：先将接收码字中信息位和冗余位按位半加，得到一个k位的合成码组（对上述具体的码长为10的正反码来说，就是得到一个5位的合成码组）。 若接收码字中的信息位中有奇数个“1”，则就取合成码组为校验码组；若接收码字中信息位中有偶数个“1”，则取合成码组的反码作为校验码组。 32正反码（续）校验码组差错情况全“0”无差错4个“1”、1个“0”信息

16、位中有一位差错，其位置对应于校验码组中“0”的位置 4个“0”、1个“1” 冗余位中有一位差错，其位置对应于校验码组中“1”的位置 其它情况 差错在两位或两位以上 33例子发送码字为0101101011，传输中无差错，则合成码组为0101101011=00000，由于接收码字的信息位中有3个“1”，故00000就是校验码组，查前表知无差错。若传输中发生了一位差错，接收端收到1101101011，则合成码组为1101101011=10000，由于接收的码字中信息位中有4个“1”，故校验码组为01111。查前表知，信息位的第1位错，故可将接收到的1101101011纠正为0101101011。若传

17、输中发生了两位错，接收端收到1101111011，则合成码组为1101111011=00000，而此时校验码组为11111，查前表可判断出为两位或两位以上的差错。34例子（续）又如，若传输中发生了四位错，接收端收到1101011010，则合成码组为1101011010=00000，而此时校验码组也为00000，查表会认为是无差错，也就是说对这种差错是漏捡了。再如，若传输中发生了三位错，接收端收到1101011011，则合成码组为1101011011=00001，此时校验码组也为00001，查表会认为是冗余位中有一位差错，其位置对应于校验码组中“1”的位置，从而将其误纠为1101011010。实

18、际上，任何一种检错码，都会发生漏检的情况；而任何一种纠错码，也都会发生误纠的情况。漏检率和误纠率都是差错控制编码的重要技术指标，当然是越小差错控制能力越强。 35正反码的编码效率较低，只有1/2。但其差错控制能力还是较强，如上述长度为10的正反码，能检测出全部两位差错和大部分两位以上的差错，并且还具有纠正一位差错的能力。由于正反码的编码效率较低，只能用于信息位较短的场合。下面将介绍两种编码效率较高的，且差错控制能力较强的纠错和检错码。 36本讲内容第三章 数据链路层 3.1 数据链路层的功能 3.1.1 帧同步* 3.1.2 差错控制 3.1.3 流量控制* 3.1.4 链路管理* 3.2 差

19、错检测与校正 3.2.1 传输差错的特性 3.2.2 常用的简单差错控制编码 3.2.3海明码海明码 3.2.4 循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。 373.2.3海明码介绍由R. Hamming在1950年首次提出 也是一种可以纠正一位差错的编码，但当信息位足够长时，它的编码效率要比正反码高得多 回顾奇偶校验，若信息位为k=n-1位 ，加上一位偶校验位a0，构成一个n位的码字 。在接收端校验时，可按关系式若S=0，则无错；若S=1，则有错。上式可称为监督关系式，S称为校正因子38海明码（续）在奇偶校验情况下，只有一个监督关系式，一个校正因子

20、，其取值只有两种（0或1），分别代表了无错和有错两种情况，而不能指出差错所在的位置 若增加冗余位，也相应地增加监督关系式和校正因子，就能区分更多的情况。信息位为k位，增加r位冗余位，构成n=k+r位码字 。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错，则要求 或 39例子以k = 4为例来说明，要满足前述不等式，则r3。现取r = 3，则n = k + r = 7。 在4位信息位 后面加上3位冗余位 ，构成7位码字 。其a2、a1和a0分别由4位信息位中某几位半加得到。那么在校验时，a2、a1和a0就分别和这些位半加构成三个不同的监督关系式。在无错时，这三个

21、关系式的值S2、S 1和S0全为“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一位错。 40例子（续）a2、a4、a5或a6的一位错都应使S2 = 1,由此可以得到监督关系式 41例子（续）在发送端编码时，信息位a6、a5、a4和a3的值取决于输入信号，是随机的。冗余位a2、a1和a0的值应根据信息位的取值按监督关系式来决定，使上述三式中的S2、S1和S0取值为零 由此可求得已知信息位后，按此三式即可算出各冗余位。对于各种信息位算出

22、的冗余位如后表 42信息位冗余位信息位冗余位000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111143例子（续）在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若为全“0”则认为无错。若不全为“0”，在一位错的情况下，可查表来判定是哪一位错，从而纠正之。例如码字传输中发生一位错，在接收端收到的为0011101，代入监督关系式可算得S2=0、S1=1和S0=1，由查表得S2 S1 S0=011对应于a3错，因而可将纠正

23、为。但是，若码字传输中发生两位错，在接收端收到的为，代入监督关系式可算得S2=0、S1=0和S0=1，查表得S2 S1 S0=001对应于a0错，从而会将纠正为，这就是误纠的情况。=167+4+1=12再如，若码字传输中发生三位错，在接收端收到的为，代入监督关系式可算得S2=0、S1=0和S0=0，查表可得S2 S1 S0=000对应于无错，从而认为传输中无差错，这就是漏检的情况。我们这个例子中正好 =k+r+1，若 k+r+1则在查表中还有多余的位置可用来表示两位以上的错误，就可降低漏检率了。比如，若k=7，则满足 k+r+1的最小r为4。此时 r244海明码（续）上述例子中，k=4的海明码

24、的编码效率为4/7；若k=7，则编码效率为7/11。由此可见，信息位长度越长时编码效率越高。只能纠正一位错，若用在纠正传输中出现突发性差错时可以采用下述方法：将连续P个码字排成一个矩阵，每行一个码字图3.4海明码用于纠正突发错误的情况45本讲内容第三章 数据链路层 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 循环冗余码循环冗余码*是要求同学了解的，这些内容在本电子教案中并未讲解而是要求同学自己阅读教材。

25、463.2.4 循环冗余码在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码CRC（Cyclic Redundancy Code） CRC码又称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。47（2）循环冗余码（）循环冗余码（CRC）CRC（Cyclic Redundancy Check）是在所传送的k位信息后面附加一 个r位检验序列。工作原理：设f(x)为一个k阶多项式, 其系数是待发送信息的比特序列；例如，待发送的信息序列是1010001101，则对应f(x)=x9+x7+x3+x2+1 （k

26、=9)。G(x)为一个r 阶的生成多项式，由发收双方预先约定。G（x)有国际标准。48 CRC码的产生：码的产生： 检验序列的生成：检验序列的生成： 用用xr f(x)除以除以G(x), 得余式得余式R(x)，其系数序列即，其系数序列即是检验序列。是检验序列。 进行除法运算时，采用模进行除法运算时，采用模2算术，即加法不进位，算术，即加法不进位，减法不借位（异或运算）。减法不借位（异或运算）。 49例如，生成多项式G(x)=x5+x4+x2+1,即110101（r=5)x5f(x)=x14+x12+x8+x7+x5，即1000，也就是f(x)信息序列向左移动r=5位。x5f(x)/G(x)=（

27、1000）/（110101），得余数为01110，对应的余式R(x)=0x4+x3+x2+x+0x0(注意：若G(x)为r阶，则余数序列有r位）。501101010110110101）1010001101000001101010111011110101001110101101010011111011010100101100110101011001011010101110余数，也余数，也就是检验序列（就是检验序列（r位，这里位，这里 r=5，r也是也是G(x)的的阶阶 ）51 编码：在原信息序列后面附加上检验序列（r位），得到CRC编码（发送序列）。 例如， x5 f(x)-R(x) =1010

28、001101 0111001110，即为发送的序列。检验：在接收方，用相同的生成多项式G(x)除所收到的序列，若余数为0，则传输无差错，否则传输出现差错。52练习题3.3 某信道误码率为10-5，每帧长度为10kbits，那末(1) 若差错都是单个错，则在该信道上传送的帧的平均出错率是多少？ (2) 若差错大多为突发错，平均突发长度为100bits，则在该信道上传送的帧的平均出错率是多少？ 3.9 若信息位为7位，要构成能纠正一位错的海明码，则至少要加上多少位冗余位？并写出其监督关系式。 3.11 已知海明码的监督关系式为 s0 = a0 + a3 + a5 + a6 s1 = a1 + a4 + a5 + a6 s2 = a2 + a3 + a4 + a5 接收端收到的码字a6a5a4a3a2a1a0=1011110，在最多一位错的情况下，问发送端发送的码字是什么？ 3.14 已知循环冗余码的生成多项式G（X）= x5+x4+x+1，若接收方收到的码字为11，问传输中是否有差错？ 53