差错检验与校正

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

2、、脉动噪声、衰减、延迟、内部因素有噪声脉冲、脉动噪声、衰减、延迟、失真等。机器设备本身的不理想、技术不成熟失真等。机器设备本身的不理想、技术不成熟 外部因素有电磁干扰、太阳噪声、工业噪声等。外部因素有电磁干扰、太阳噪声、工业噪声等。对信号影响较大。对信号影响较大。 噪声脉冲噪声脉冲：通信中出现的离散型噪声的统称。：通信中出现的离散型噪声的统称。它由时间上无规则出现的突发性干扰组成。它由时间上无规则出现的突发性干扰组成。 一般来说，传输中的差错都是由噪声引起的。噪声有一般来说，传输中的差错都是由噪声引起的。噪声有两大类：随机热噪声和冲击噪声。两大类：随机热噪声和冲击噪声。随机差错：随机热噪声随机

3、差错：随机热噪声 信道所固有的，持续存在的，随机错通常信道所固有的，持续存在的，随机错通常 较少。较少。 突发差错：冲击噪声突发差错：冲击噪声 由于外界特定的短暂原因所造成的冲击噪声，冲击由于外界特定的短暂原因所造成的冲击噪声，冲击噪声的幅度可以相当大噪声的幅度可以相当大 ，它是传输中产生差错的重要原，它是传输中产生差错的重要原因因 。2 2、两种差错控制技术检错法纠错法在发送方的数据中增加在发送方的数据中增加一些用于检查差错的附一些用于检查差错的附加位。用于有反馈的传加位。用于有反馈的传输机制中。输机制中。实现方法简单，速度快。实现方法简单，速度快。在待发送数据中增加足够在待发送数据中增加足

4、够多的附加位，从而使得接多的附加位，从而使得接收方能够准确地检测到差收方能够准确地检测到差错，并且可以自动地纠正错，并且可以自动地纠正差错。用于无反馈信息的差错。用于无反馈信息的传输机制中，如汉明码。传输机制中，如汉明码。 3 3、奇偶校验 奇偶校验奇偶校验(Parity Check)是一种校验代码传输正确性的方法，是一种最简单的检错是一种校验代码传输正确性的方法，是一种最简单的检错方法。根据被传输的一组二进制代码的数位中方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。的个数是奇数或偶数来进行校验。采用何种校验是事先规定好的。采用奇数的称为奇校验，反之，称为偶校验。

5、通常采用何种校验是事先规定好的。采用奇数的称为奇校验，反之，称为偶校验。通常专门设置一个奇偶校验位，用它使这组代码中专门设置一个奇偶校验位，用它使这组代码中“1”的个数为奇数或偶数。若用奇校的个数为奇数或偶数。若用奇校验，则当接收端收到这组代码时，校验验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从而确定传输代码的个数是否为奇数，从而确定传输代码的正确性。的正确性。 例如，在传输例如，在传输ASCIIASCII字符字符时，每个时，每个ASCIIASCII字符字符用用7 7为表示，最后加上一个奇偶校验位总共成为表示，最后加上一个奇偶校验位总共成为为8 8位。对于奇校验来说，最后加上的

6、奇偶位位。对于奇校验来说，最后加上的奇偶位校验使整个校验使整个8 8位中位中1 1个数为奇数。个数为奇数。 如发送如发送11100011110001，采用奇校验时，奇偶位校，采用奇校验时，奇偶位校验为验为1 1，即传输，即传输1110001111100011。接收器检查接收到。接收器检查接收到的数据的的数据的1 1的个数为奇数，就认为的个数为奇数，就认为 无错误发无错误发生。若采用偶校验时，发送的二进制码是？生。若采用偶校验时，发送的二进制码是？已知字符T的ASCII码值的十进制表示为84，如果将最高位设置为奇校验位，则字符M的ASCII码值设置奇校验位后，它的二进制表示为（ ） A.0100

7、1101 B.11001101 C.01101011 D.10111101 解 答 ： M 的 A S C I I 码 7 7 ， 二 进 制 表 示 为01001101，里面有4个1所以奇偶校验取值为1，设置于最高位后就是B了。采用奇偶校验时，若其中2位同时发生错误，则会发生没有检测错误的情况。所以奇偶检验虽然简单，但并不是一种安全的差错控制方法。一般，在低速传输时，出错概率较低，效果还可以令人满意。而当传输数据速率较高或噪声持续时间较长时，由于可能发生多位出错，差错检验的结果很可能是错误的。 ASCIIASCII编码 ASCII（American Standard Code for Inf

8、ormation Interchange，美国标准信息交换代码）是基于拉丁字母的一套电脑编码系统，它是现今最通用的单字节编码系统。 在计算机中，所有的数据在存储和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示1和0），例如，像a、b、c、d这样的52个字母（包括大写）、以及0、1等数字还有一些常用的符号（例如*、#、等）在计算机中存储时都要使用二进制数来表示，而具体用哪些二进制数字表示哪个符号，当然每个人都可以约定自己的一套（这就叫编码），而大家如果要想互相通信而不造成混乱，那么大家就必须使用相同的编码规则，于是美国有关的标准化组织就出台了ASCII编码，统一规定了上述常用符号

9、用哪些二进制数来表示。 ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础ASCII码，使用7 位二进制数来表示所有的大写和小写字母，数字0 到9、标点符号以及在美式英语中使用的特殊控制字符。例如，A的7位ASCII编码为1000001。下图为7位ASCII代码表。d3 d2 d1d0位0 d6 d5d4位0000010100111001011101110000NULDELSP0Pp0001SOHDC1！1AQaq0010STXDC22BRbr0011ETXDC33CScs0100EOTDC44DTdt0101ENQNAK5EUe

10、u0110ACKSYN6FVfv0111BELETB7GWgw1000BSCAN8HXhx1001HTEM9IYiy1010LFSUB：JZjz1011VTESCKk1100FFFS，Ll1101CRGSMm1110SORSNn1111SIHSOoDEL4 4、循环冗余码校验 奇偶校验作为一种检验码虽然简单，但是漏检率太高。目前，在计算机网络和数据通信中用得最广泛的检错码是一种漏检率低得多也便于实现的循环冗余码CRC（Cyclic Redundancy Code）。CRC是一种较复杂的校验方法，又称多项式码，是通过多项式除法检测差错的方法。这种编码对随机差错和突发差错均能以较低的冗余度进行严格

11、的检查，有很强的检错能力。 CRC码称为多项式码。这是因为任何一个由二进制数位串组成的代码都可以和一个只含有0 0和1 1两个系数的多项式建立一一对应的关系。 x x的最高幂次对应二进制数的最高位，以下各位对应多项式的各幂次，有此幂次项对应1 1，无此幂次项对应0 0。可以看出：x x的最高幂次为R R，转换成对应的二进制数有R+1R+1位。( (因为从x x的0 0次幂算起) ) 代码1011011对应的多项式为 x6 + x4 + x3 +1 而多项式x5 + x4 + x2 + x对应的代码为110110 CRCCRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，

12、如果CRCCRC码共长N N个bitbit，信息码长K K个bitbit，就称为(N,K)(N,K)码。对于一个给定的（N N，K K）码，可以证明存在一个最高次幂为N-K=RN-K=R的多项式G(x)G(x)，可根据其生成信息的校验码，所以G(x)G(x)叫做这个CRCCRC码的生成多项式。 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)对应的二进制数

13、码，得余数R(x) ，即为校验码（4）令F(x)+R(x)=T(x)，即将余数拼到信息码左移后空出的位置，得到完整的CRC码，并传送T(x)（5）接受方用接收到的T(x)模2除以G(x)（6）察看结果为0则认为无差错，否则就是有差错要求重传。模2除法 模2除法与算术除法类似，但每一位除（减）的结果不影响其它位，即不向上一位借位。 多位模2除法采用模2减法，不带借位的二进制减法。循环冗余校验码由于具有良好的代数结构，计算机中易于实现，编码器简单，检错能力强，故在微机通信中广泛使用。循环冗余检验码的纠错能力与校验码的位数有关，校验码位数多，检错能力就强。例1.CRC 属于检错码还是纠错码？如果某一

14、数据通信系统采用 CRC校验方式，生成多项式G(x)为 X4 +X3+1 ，目的结点接收到二进制比特序列为 110111101（含CRC 校验码），判断传输过程中是否出现了错误？并解释原因。 答：属于检错码。出现了差错，因为余数为110。例 2 .利 用 标 准 C R C 方 法 传 输 位 流10011101，生成多项式为x3 +1，请给出实际被传输的位串。假设在传输过程中左边第三位变反了，请证明这个错误可以在接收端被检测出来。 答：（1）模2除，得余数，即校验码。（2）可以检测出来，因为余数是100.例3.如果某一数据通信系统采用CRC校验方式，生成多项式G(x)为X4 +X3+1，目的

15、结点接收到二进制比特序列为1101111101（含CRC校验码）。请回答以下问题：（ 1）该生成多项式对应的二进制比特序列是多少？（ 2）如果接收到的二进制比特序列长度正确，则发送端原始二进制比特序列的长度是几位？（ 3）判断传输过程中是否出现了差错？为什么？十进制 二进制（35）D=( )B 用若干个2n相加方法；除2取余法35用8421编码方法，转换成的代码序列：10001100110101数据通信中，利用编码方法来进行差错控制的方式，基本数据通信中，利用编码方法来进行差错控制的方式，基本上有两类：上有两类： 自动请求重发自动请求重发ARQARQ（Automatic ReQuest for repea