【车载开发系列】CRC循环冗余校验码原理

【车载开发系列】CRC循环冗余校验码原理

一. CRC算法原理

CRC原理实际上就是在一个K位二进制数据序列之后附加一个R位二进制检验码(序列)，从而构成一个总长为N＝K＋R位的二进制序列。
附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误，这种特定关系就会被破坏。因此，通过检查这一关系，就可以实现对数据正确性的检验。

二. 生成多项式

当进行CRC检验时，发送方与接收方事先约定一个除数，即生成多项式，一般记作G（x）。生成多项式的最高位与最低位必须是1。常用的CRC码的生成多项式有：
CRC8=X8+X5+X4+1
CRC-CCITT=X16+X12+X5+1
CRC16=X16+X15+X5+1
CRC12=X12+X11+X3+X2+1
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
一个多项式就是一个比特流，也就是由0、1组合起来的一组数
我们需要获取的常数就是上面多项式所对应的反转多项式(反转多项式：在数据通讯时，信息字节先传送或接受低位字节，如重新排列则影响速度)。

三. 多项式与其对应代码

若X的最高次幂为R，那么对应代码应该有R+1位数。
以CRC8=X8+X5+X4+1为例，从bit0开始，CRC8没有X1,X2,X3,X6,X7，则其代码为 100110001.
如此可以得到CRC32的代码为：100000100110000010001110110110111
它的16进制表示为0x04C11DB7。

四. CRC码校验原理

CRC运算采用模2运算。
多项式模2运算也就是按位异或(Exclusive OR)的运算，即相同为0，相异为1。
模2加法：相加无进位，按位异或。
模2除法：模2减法，被除数 - 除数，直到得到余数
模2乘法：按位与后采用模2加法。
模2减法：无借位，按位异或。

1）发送端

发送端根据信息字段与生成多项式生成CRC码，CRC码作为数据发送给接收端，同时也会把计算出的校验字段的数据一同发送(注：目的是如果接受端检测到发送的数据是正确的，接收端能够从CRC码中提取出信息字段的数据)。

2）接收端

接收到CRC码数据后，检测接收到的数据是否正确
方法：将CRC码数据与生成多项式进行模2除，如果余数为0，则说明接收到的数据是正确的。然后，从CRC码中提取出信息字段的数据。

五. CRC码原理方法

1）发送端生成CRC码方法

CRC码是由两部分组成的，前部分是信息字段，就是需要校验的信息，后部分是校验字段，如果CRC码共长n个bit，信息字段长k个bit，就称为(n，k)码。它的编码规则是：
首先将信息字段值(k bit)左移r位(k+r=n)
运用一个生成多项式g(x) (也可看成二进制数) 模2除上面的式子，得到的余数就是校验字段值。
生成的CRC码值为：信息字段值+校验字段值(单位：位bit，次序：高位到低位)，例如字段值为1001，校验字段值为110，则CRC码为1001110

2）接收端验证方法

接收到CRC码数据后，将CRC码数据与生成多项式进行模2除，如果余数为0，则说明验证过程无误，数据是完整没有丢失的。

六. CRC码的优点

检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC是无处不在。

七. CRC总结

总结起来，CRC就是一个数值，该数值用于检验数据的正确性，CRC校验的原理就是将需要做校验的数据与一个数据模2相除，得到的余数即为校验值。
接收数据时，将再次生成校验和，并将其与发送的校验和进行比较。如果两者相等，则没有数据损坏。
发送方用发送数据的二进制多项式 t(x) 除以 g(x) ，得到余数 y(x) 作为 CRC 校验码。校验时，以计算的校正结果是否为 0 为据，判断数据帧是否出错