差错检验与校正解读课件

1、差错检验与校正2.4差错检验与校正第2章 数据通信基础第1页，共23页。 计算机网络的基本要求是高速而且无差错的传输数据信息，而通信系统主要由一个个物理实体组成。一个物理实体从制造、装配等都无法达到理想的理论值，而且通信系统在运作中，也会受到周围环境的影响。因此数据在传输数据过程中发生差错是不可避免的，解决这个问题的技术称为差错控制技术 ，即把差错控制在允许的范围内。通常差错控制技术包括两个主要内容：差错的检验差错的校正第2页，共23页。1、差错出现的可能原因 数据传输中出现差错有多种原因，一般分为内部因素和外部因素。 内部因素有噪声脉冲、脉动噪声、衰减、延迟、失真等。机器设备本身的不理想、技

2、术不成熟 外部因素有电磁干扰、太阳噪声、工业噪声等。对信号影响较大。 噪声脉冲：通信中出现的离散型噪声的统称。它由时间上无规则出现的突发性干扰组成。第3页，共23页。 一般来说，传输中的差错都是由噪声引起的。噪声有两大类：随机热噪声和冲击噪声。随机差错：随机热噪声 信道所固有的，持续存在的，随机错通常 较少。 突发差错：冲击噪声 由于外界特定的短暂原因所造成的冲击噪声，冲击噪声的幅度可以相当大 ，它是传输中产生差错的重要原因 。第4页，共23页。2、两种差错控制技术检错法纠错法在发送方的数据中增加一些用于检查差错的附加位。用于有反馈的传输机制中。实现方法简单，速度快。在待发送数据中增加足够多的

3、附加位，从而使得接收方能够准确地检测到差错，并且可以自动地纠正差错。用于无反馈信息的传输机制中，如汉明码。第5页，共23页。 3、奇偶校验 奇偶校验(Parity Check)是一种校验代码传输正确性的方法，是一种最简单的检错方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用何种校验是事先规定好的。采用奇数的称为奇校验，反之，称为偶校验。通常专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的正确性。 第6页，共23页。 例如，在传输ASCII字符时，每个ASCII字

4、符用7为表示，最后加上一个奇偶校验位总共成为8位。对于奇校验来说，最后加上的奇偶位校验使整个8位中1个数为奇数。 如发送1110001，采用奇校验时，奇偶位校验为1，即传输11100011。接收器检查接收到的数据的1的个数为奇数，就认为 无错误发生。若采用偶校验时，发送的二进制码是？第7页，共23页。已知字符T的ASCII码值的十进制表示为84，如果将最高位设置为奇校验位，则字符M的ASCII码值设置奇校验位后，它的二进制表示为（ ） A.01001101 B.11001101 C.01101011 D.10111101 解答：M的ASCII码77，二进制表示为01001101，里面有4个1所

5、以奇偶校验取值为1，设置于最高位后就是B了。第8页，共23页。采用奇偶校验时，若其中2位同时发生错误，则会发生没有检测错误的情况。所以奇偶检验虽然简单，但并不是一种安全的差错控制方法。一般，在低速传输时，出错概率较低，效果还可以令人满意。而当传输数据速率较高或噪声持续时间较长时，由于可能发生多位出错，差错检验的结果很可能是错误的。 第9页，共23页。ASCII编码 ASCII（American Standard Code for Information Interchange，美国标准信息交换代码）是基于拉丁字母的一套电脑编码系统，它是现今最通用的单字节编码系统。 在计算机中，所有的数据在存储

6、和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示1和0），例如，像a、b、c、d这样的52个字母（包括大写）、以及0、1等数字还有一些常用的符号（例如*、#、等）在计算机中存储时都要使用二进制数来表示，而具体用哪些二进制数字表示哪个符号，当然每个人都可以约定自己的一套（这就叫编码），而大家如果要想互相通信而不造成混乱，那么大家就必须使用相同的编码规则，于是美国有关的标准化组织就出台了ASCII编码，统一规定了上述常用符号用哪些二进制数来表示。第10页，共23页。 ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础A

7、SCII码，使用7 位二进制数来表示所有的大写和小写字母，数字0 到9、标点符号以及在美式英语中使用的特殊控制字符。例如，A的7位ASCII编码为1000001。下图为7位ASCII代码表。第11页，共23页。d3 d2 d1d0位0 d6 d5d4位0000010100111001011101110000NULDELSP0Pp0001SOHDC1！1AQaq0010STXDC22BRbr0011ETXDC33CScs0100EOTDC44DTdt0101ENQNAK5EUeu0110ACKSYN6FVfv0111BELETB7GWgw1000BSCAN8HXhx1001HTEM9IYiy10

8、10LFSUB：JZjz1011VTESCKk1100FFFS，Ll1101CRGSMm1110SORSNn1111SIHSOoDEL第12页，共23页。4、循环冗余码校验 奇偶校验作为一种检验码虽然简单，但是漏检率太高。目前，在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码CRC（Cyclic Redundancy Code）。CRC是一种较复杂的校验方法，又称多项式码，是通过多项式除法检测差错的方法。这种编码对随机差错和突发差错均能以较低的冗余度进行严格的检查，有很强的检错能力。 第13页，共23页。 CRC码称为多项式码。这是因为任何一个由二进制数位串组

9、成的代码都可以和一个只含有0和1两个系数的多项式建立一一对应的关系。 x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1，无此幂次项对应0。可以看出：x的最高幂次为R，转换成对应的二进制数有R+1位。(因为从x的0次幂算起) 代码1011011对应的多项式为 x6 + x4 + x3 +1 而多项式x5 + x4 + x2 + x对应的代码为110110 第14页，共23页。 CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长N个bit，信息码长K个bit，就称为(N,K)码。对于一个给定的（N，K）码，可以证明存在一个最高

10、次幂为N-K=R的多项式G(x)，可根据其生成信息的校验码，所以G(x)叫做这个CRC码的生成多项式。 第15页，共23页。 CRC编码步骤：（1）给定一个生成多项式：G(x)=x4+x3+1,则x的最高次幂是R=4，转换为二进制数码11001（有R+1=5位）（2）将原信息码1011001(K=7bit)左移R位(K+R=N)（即后边补k个0）得到F(x)=10110010000（3）用F(x)模2除以G(x)对应的二进制数码，得余数R(x) ，即为校验码（4）令F(x)+R(x)=T(x)，即将余数拼到信息码左移后空出的位置，得到完整的CRC码，并传送T(x)（5）接受方用接收到的T(x)

11、模2除以G(x)（6）察看结果为0则认为无差错，否则就是有差错要求重传。第16页，共23页。模2除法 模2除法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位。 多位模2除法采用模2减法，不带借位的二进制减法。第17页，共23页。循环冗余校验码由于具有良好的代数结构，计算机中易于实现，编码器简单，检错能力强，故在微机通信中广泛使用。循环冗余检验码的纠错能力与校验码的位数有关，校验码位数多，检错能力就强。第18页，共23页。例1.CRC属于检错码还是纠错码？如果某一数据通信系统采用CRC校验方式，生成多项式G(x)为X4+X3+1，目的结点接收到二进制比特序列为1101111

12、01（含CRC校验码），判断传输过程中是否出现了错误？并解释原因。 答：属于检错码。出现了差错，因为余数为110。第19页，共23页。例2.利用标准CRC方法传输位流10011101，生成多项式为x3+1，请给出实际被传输的位串。假设在传输过程中左边第三位变反了，请证明这个错误可以在接收端被检测出来。 答：（1）模2除，得余数，即校验码。（2）可以检测出来，因为余数是100.第20页，共23页。例3.如果某一数据通信系统采用CRC校验方式，生成多项式G(x)为X4+X3+1，目的结点接收到二进制比特序列为1101111101（含CRC校验码）。请回答以下问题：（1）该生成多项式对应的二进制比特序列是多少？（2）如果接收到的二进制比特序列长度正确，则发送端原始二进制比特序列的长度是几位？（3）判断传输过程中是否出现了差错？为什么？第21页，共23页。十进制 二进制（35）D=( )B 用若干个2n相加方法；除2取余法35用8421编码方法，转换成的代码序列：10001100110101第22页，