计算机三种校验方式,三种校验码

1、三种校验码奇偶校验、海明码、CRC循环冗余校验码三种校验码较重要，需要牢记，在计算机络中处较奇偶校验根据被传输的组进制代码的数位中“1”的个数是奇数或偶数来进校验。采奇数的称为奇校验，反之，称为偶校验。采何种校验是事先规定好的。通常专门设置个奇偶校验位，它使这组代码中“1”的个数为奇数或偶数。若奇校验，则当接收端收到这组代码时，校验“1”的个数是否为奇数，从确定传输代码的正确性。校验法奇校验：就是让原有数据序列中(包括你要加上的位)1的个数为奇数1000110(0)你必须添0这样原来有3个1已经是奇数了所以你添上0之后1的个数还是奇数个。偶校验：就是让原有数据序列中(包括你要加上的位)1的个数

2、为偶数1000110(1)你就必须加1了这样原来有3个1要想1的个数为偶数就只能添1了范例串数据在传输过程中，由于扰可能引起信息的出错，例如，传输字符E，其各位为：0100，0101=45HD7 D0由于扰，可能使位变为1，(为什么不变0？)这种情况，我们称为出现了“误码”。我们把如何发现传输中的错误，叫“检错”。发现错误后，如何消除错误，叫“纠错”。最简单的检错法是“奇偶校验”，即在传送字符的各位之外，再传送1位奇/偶校验位。可采奇校验或偶校验。奇校验：所有传送的数位(含字符的各数位和校验位)中，“1”的个数为奇数，如：1 0110，01010 0110，0101偶校验：所有传送的数位(含字

3、符的各数位和校验位)中，“1”的个数为偶数，如：1 0100，01010 0100，0101奇偶校验能够检测出信息传输过程中的部分误码(奇数位误码能检出，偶数位误码不能检出)，同时，它不能纠错。在发现错误后，只能要求重发。但由于其实现简单，仍得到了泛使。有些检错法，具有动纠错能。如循环冗余码(CRC)检错等CRC校验CRC即循环冗余校验码(Cyclic Redundancy Check)：是数据通信领域中最常的种查错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是种数据传输检错功能，对数据进多项式计算，并将得到的结果附在帧的后，接收设备也执类似的算法，以保证数据传

4、输的正确性和完整性。作原理循环冗余校验码(CRC)的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码也叫(N，K)码。对于个给定的(N，K)码，可以证明存在个最次幂为N-K=R的多项式G(x)。根据G(x)可以成K位信息的校验码，G(x)叫做这个CRC码的成多项式。 校验码的具体成过程为：假设要发送的信息多项式C(X)表，将C(x)左移R位(可表成C(x)2R)，这样C(x)的右边就会空出R位，这就是校验码的位置。 C(x)2R 除以成多项式G(x)得到的余数就是校验码。对应关系多项式和进制数有直接对应关系：X的最幂次对应进制数的最位，以下各位对应多项式的各幂次

5、，有此幂次项对应1，此幂次项对应0。可以看出：X的最幂次为R，转换成对应的进制数有R+1位。多项式包括成多项式G(X)和信息多项式C(X)。如成多项式为G(X)=X4+X3+X+1， 可转换为进制数码11011。发送信息位 101111，可转换为数据多项式为C(X)=X5+X3+X2+X+1。成多项式是接受和发送的个约定，也就是个进制数，在整个传输过程中，这个数始终保持不变。在发送，利成多项式对信息多项式做模2除成校验码。在接收利成多项式对收到的编码多项式做模2除检测和确定错误位置。应满以下条件：A、成多项式的最位和最低位必须为1。B、当被传送信息(CRC码)任何位发错误时，被成多项式做除后应

6、该使余数不为0。C、不同位发错误时，应该使余数不同。D、对余数继续做除，应使余数循环。校验码位数CRC校验码位数 = 成多项式位数 - 1。注意有些成多项式的简记式中将成多项式的最位1省略了。成步骤1、将X的最次幂为R的成多项式G(X)转换成对应的R+1位进制数。2、将信息码左移R位，相当于对应的信息多项式C(X)*2R。3、成多项式(进制数)对信息码做除，得到R位的余数(注意：这的进制做除法得到的余数其实是模2除法得到的余数，并不等于其对应进制数做除法得到的余数。)。4、将余数拼到信息码左移后空出的位置，得到完整的CRC码。【例】假设使的成多项式是G(X)=X3+X+1。4位的原始报为101

7、0，求编码后的报。解：1、将成多项式G(X)=X3+X+1转换成对应的进制除数1011。2、此题成多项式有4位(R+1)(注意：4位的成多项式计算所得的校验码为3位，R为校验码位数)，要把原始报C(X)左移3(R)位变成1010 0003、成多项式对应的进制数对左移3位后的原始报进模2除(位对齐)，相当于按位异或：10100001011】00010000001011-】0000011得到的余位011，所以最终编码为：1010 011原则若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任码字，存在且仅存在个R次多项式g(x)，使得V(x)=A(x)g(x)=x

8、Rm(x)+r(x);其中:m(x)为K次原始的信息多项式， r(x)为R-1次校验多项式(即CRC校验和)，g(x)称为成多项式：g(x)=g0+g1x1+ g2x2+g(R-1)x(R-1)+gRxR发送通过指定的g(x)产CRC码字，接收则通过该g(x)来验证收到的CRC码字。成法借助于模2除法则，其余数为校验字段。例如：信息字段代码为:1011001；对应m(x)=x6+x4+x3+1假设成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为:11001x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；采模2除法则:得余数为:1010(即校验字段为：

9、1010)发送：发出的传输字段为:1 0 1 1 0 0 1 1010信息字段 校验字段接收：使相同的成码进校验:接收到的字段/成码(进制除法)如果能够除尽，则正确，给出余数(1010)的计算步骤：除法没有数学上的含义，是采计算机的模除法，即除数和被除数做异或运算。进异或运算时除数和被除数最位对齐，按位异或。1011001000011001】01111010000111101000011001-】00111100001111000011001】0011100011100011001-】001010则四位CRC校验码就为：1010。利CRC进检错的过程可简单描述为：在发送端根据要传送的k位进制码

10、序列，以定的规则产个校验的r位监督码(CRC码)，附在原始信息后边，构成个新的进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“成多项式”。海明码校验将有效信息按某种规律分成若组，每组安排个校验位，做奇偶测试，就能提供多位检错信息，以指出最可能是哪位出错，从将其纠正。实质上，海明校验是种多重校验。假设为k个数据位设置r个校验位，则校验位能表2r个状态，可其中的个状态指出 “没有发错误”，其余的2 r -1个状态指出有错误发在某位，包括k个数据位和r个校验位，因此校验位的位数应满如下关系:2r k +

11、 r + 1 (2.7)如要能检出与动校正位错，并能同时发现哪位错，此时校验位的位数r和数据位的位数k应满下述关系:2r-1 k + r (2.8)按上述不等式，可计算出数据位k与校验位r的对应关系，如表2.2所。表2.2k值 最r值24 3511 41226 52757 658120 7分组原则编辑在海明码中， 位号数(1、2、3、n)为2的权值的那些位，即：1(20)、2(21)、4(22)、8(23)、2(r-1)位，作为奇偶校验位，并记作:P1、P2、P3 、P4、Pr，余下各位则为有效信息位。例如：N=11(海明码位数)K=7(数据位数)r=4(校验位)，相应海明码可表位号为： 1，

12、 2， 3， 4 ，5 ，6， 7， 8， 9 ，10 ，11，校验位P占第1，2，4，8位，其他位为有效信息位，海明码中的校验位分别标为P1,P2,P3,P4 Pr ,并被信息位中的若位所校验，其规律是：第i位，由校验位位号之和等于i的那些校验位所校验，如：海明码的位号为3，它被P1P2(位号分别为1,2)所校验，海明码的位号为5，它被P1P3(位号分别为1,4)所校验。归并起来:形成了4个组，每个组个校验位，校验位的取值，仍采奇偶校验式确定。设计海明码编码的关键技术，是合理地把每个数据位分配到r个校验组中，以确保能发现码字中任何位出错；若要实现纠错，还要求能指出是哪位出错，对出错位求反则得

13、到该位的正确值。例如，当数据位为3位(D3 D2 D1表)时，检验位应为4位(P4 P3 P2 P1表)。可通过表2.3表的关系，完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。表2.3 校验位与数据位的对应关系在P1、P2、P3、P4竖列相应分别填1，在该4列的低3横其它位置分别填0，在最顶横的每个尚空位置都分别填1。若只看低3横，右4竖列的3个bit的组合值分别为进制的1、2、4、0，则分配 D1 D2 D3列的组合值为3 5 6，保证低3横各竖列的编码值各不相同。表中D3 D2 D1为三位数据位，P4 P3 P2 P1为四位校验位。其中低三位中的每个校验位P3 P2 P1的

14、值，都是三个数据位中不同的位通过偶校验运算规则计算出来的。其对应关系是：对Pi(i的取值为13)，总是处在Pi取值为1的中的、1标记出来的数据位计算该Pi的值。最个校验位P4，被称为总校验位，它的值，是通过对全部三个数据位和其它全部校验位(不含P4本)执偶校验计算求得的。形成各校验位的值的过程叫做编码，按刚说明的规则，4个校验位所的编码程为：P4 = D3 D2 D1 P3 P2 P1P3 = D3 D2P2 = D3 D1P1 = D2 D1由多个数据位和多个校验位组成的个码字，将作为个数据单位处理，例如被写内存或被传送。之后，在执内存读操作或在数据接收端，则可以对得到的码字，通过偶校验来检

15、查其合法性，通常称该操作过程为译码，所的译码程为：S4 = P4 D3 D2 D1 P3 P2 P1S3 = P3 D3 D2S2 = P2 D3 D1S1 = P1 D2 D1对应关系编辑译码程和编码程的对应关系很简单。译码程，是个校验码和形成这个校验码的编码程执异或，实际上是次执偶校验运算。通过检查四个S的结果，可以实现检错纠错的的的。实际情况是，当译码求出来的S4、S3、S2、S1的得值与表2.3中的那列的值相同，就说明是哪位出错；故们称表2.3为出错模式表。若出错的是数据位，对其求反则实现纠错；若出错的是校验位则不必理睬。举例如下：任何位(含数据位、校验位)均不错，则四个S都应为0值；任何单独位数据位出错，四个S中会有三个为1；如D3错，则S4 S3 S2 S1为1110。若单独位校验位出错，四个S中会有个或两个为1；如P1错，S4 S3 S2 S1为1001，如P4错，S4 S3 S2 S1为1000。任何