一、crc校验是什么?

  CRC即循环冗余校验码(Cyclic Redundancy Check[1] ):是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。

二、crc的原理是什么?

  循环冗余校验码(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)得到的余数就是校验码。
  任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。

三、基本概念

对应关系

  多项式和二进制数有直接对应关系:X的最高幂次对应二进制数的最高位,以下各位对应多项式的各幂次,有此幂次项对应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码)任何一位发生错误时,被生成多项式做除后应该使余数不为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位的原始报文为1010,求编码后的报文。
解:
  1、将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。
  2、此题生成多项式有4位(R+1)(注意:4位的生成多项式计算所得的校验码为3位,R为校验码位数),要把原始报文C(X)左移3(R)位变成1010 000
  3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除(高位对齐),相当于按位异或:

1010000
1011
------------------
   1000
   1011
------------------
    011

得到的余位011,所以最终编码为:1010 011
  【说明】“模2除法”与“算术除法”类似,但它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行相除即可。模2加法运算为:1+1=0,0+1=1,0+0=0,无进位,也无借位;模2减法运算为:1-1=0,0-1=1,1-0=1,0-0=0,也无进位,无借位。相当于二进制中的逻辑异或运算。也就是比较后,两者对应位相同则结果为“0”,不同则结果为“1”。如100101除以1110,结果得到商为11,余数为1,如图5-9左图所示。如11×11=101,如图5-9右图所示。
这里写图片描述

五、扩展学习:奇偶校验

1.奇偶校验是什么?

  奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位,用它使这组代码中“1”的个数为奇数或偶数。若用奇校验,则当接收端收到这组代码时,校验“1”的个数是否为奇数,从而确定传输代码的正确性。

2.奇偶校验的工作方式:

  为了能检测和纠正内存软错误,首先出现的是内存“奇偶校验”。内存中最小的单位是比特,也称为“位”,位只有两种状态分别以1和0来标示,每8个连续的比特叫做一个字节(byte)。不带奇偶校验的内存每个字节只有8位,如果其某一位存储了错误的值,就会导致其存储的相应数据发生变化,进而导致应用程序发生错误。而奇偶校验就是在每一字节(8位)之外又增加了一位作为错误检测位。在某字节中存储数据之后,在其8个位上存储的数据是固定的,因为位只能有两种状态1或0,假设存储的数据用位标示为1、1、1、0、0、1、0、1,那么把每个位相加(1+1+1+0+0+1+0+1=5),结果是奇数。对于偶校验,校验位就定义为1,反之则为0;对于奇校验,则相反。当CPU读取存储的数据时,它会再次把前8位中存储的数据相加,计算结果是否与校验位相一致。从而一定程度上能检测出内存错误,奇偶校验只能检测出错误而无法对其进行修正,同时虽然双位同时发生错误的概率相当低,但奇偶校验却无法检测出双位错误。

优缺点:

  奇偶校验有两种类型:奇校验和偶校验。奇偶校验位是一个表示给定位数的二进制数中1的个数是奇数或者偶数的二进制数,奇偶校验位是最简单的错误检测码。如果传输过程中包括校验位在内的奇数个数据位发生改变,那么奇偶校验位将出错表示传输过程有错误发生。因此,奇偶校验位是一种错误检测码,但是由于没有办法确定哪一位出错,所以它不能进行错误校正。发生错误时必须扔掉全部的数据,然后从头开始传输数据。在噪声很多的媒介上成功传输数据可能要花费很长的时间,甚至根本无法实现。但是奇偶校验位也有它的优点,它是使用一位数据能够达到的最好的校验码,并且它仅仅需要一些异或门就能够生成。奇偶校验被广泛应用。


更详尽内容见百度百科:
http://baike.baidu.com/link?url=PgjWgrSq3Qz9ITPYezOVsuLE8LXeMyflye3ZmZW9c8lJOt2w52_Il3rNPJyl0QGFJURNgZR3jMYmWka9aMWK-zv0hTEU8MdxQgo1bMXk2TWOXHV9eraZ-RIlWXC4xp20

版权声明:本文为daanzhijia原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/daanzhijia/p/14420959.html?ivk_sa=1024320u