2025年CRC算法

大家好，我是讯享网，很高兴认识大家。

CRC(Cycle Redundancy Check)：循环冗余校验，在链路层被广泛使用的检错技术。

CRC原理（通俗讲）

1.发送端

1.1 在发送端先将数据分组，每组k个数据。假定要传送的数据是M。

1.2 在数据M后面添加供差错检测的n位冗余码，然后构成一帧发送出去，一共发送(k+n)位。

虽然添加n位冗余码增大了数据传送的开销，但是可以进行差错检测，当传输可能出现差错时，付出这种代价是值得的。

1.3 冗余码可以用下面的方法得出：

1.3.1 用二进制模2运算进行2^n*M（相当于M左移n位）的运算。意思就是在M后面补n个0.现在M就变成了k+n位。

1.3.2 用M除以收发双方事先商定的长度n+1的除数P

1.3.3 得到的余数R，这个R就是FCS（帧校验序列）。将这个FCS序列加到M上然后发出去。

2.接收端

2.1 在接收端把接收到的数据以帧为单位进行CRC校验

2.2 把收到的每一个帧都除以同样的除数P，然后检查余数R

2.3 如果余数R为0，那么在传输过程中没有差错

2.4 如果出现误码，那么余数R为零的概率是非常小的

总结：在接收端对接收到的每一帧进行CRC校验后，若余数R为0，则表示这个帧没有错，就接受。如果不为0，则判定这个帧出错，就丢弃。

例：M=, P=1101, n=3

在发送端：

1. M=(2^n*M); 则M=

2. 用M除以P

讯享网

3.得到余数R也就是FCS，将FCS加到M上，就得到了要发送的帧。

M=+FCS=

在接收端：

接收到的每一帧都要进行差错检验，假设收到，P=1101

最后余数R=0，则判定这个帧没有出错。

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’取值的多项式一一对应。例如：代码对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码。

这里还有个问题，如果被除数比除数小，那么余数就是被除数本身，比如说只要传一个字节，那么他的CRC就是他自己，为避免这种情况发生，在做除法之前先将他移位，使他大于除数，那么移位多少位呢？这是所选的固定除数有关，左移位数比除数的位数少1，下面是常用标准中的除数：

CRC8：多项式是X8+X5+X4+1，对应的数字是0x131，左移8位
CRC12：多项式是X12+X11+X3+X2+1，对应的数字是0x180D，左移12位
CCITT CRC16：多项式是X16+X12+X5+1，对应的数字是0x11021，左移16位
ANSI CRC16：多项式是X16+X15+X2+1，对应的数字是0x18005，左移16位
CRC32：多项式是X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，对应数字是0x104C11DB7，左移32

因此，在得到字节串对应的数字后，再将数字左移M位（比如ANSI-CRC16是左移16位），就得到了被除数。

好了，现在被除数和除数都有了，那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似，首先是被除数与除数高位对齐后，被除数减去除数，得到了差，除数再与差的最高位对齐，进行减法，然后再对齐再减，直到差比除数小,这个差就是余数。不过和普通减法有差别的是，CRC的加(减)法是不进(借)位的，比如10减01，它的结果是11，而不是借位减法得到的01，因此，实际上CRC的加法和减法所得的结果是一样的，比如10加01的结果是11，10减01的结果也是11，这其实就是异或操作。虽然说了这么多也不一定能说清楚，我们还是看一段CRC除法求余程序吧：

unsigend short crc16_div() { unsigned long data = 0x; unsigned long ccitt16 = 0x11021; unsigned long cmp_value = 0x10000; int i; ccitt16 <<= 7; cmp_value <<=7; while(cmp_value >= 0x10000) { if((data & cmp_value) != 0) { data ^= ccitt16; //^为按位运算符：异或 } else { } ccitt16 >>= 1; cmp_value >>= 1; } return (data & 0xFFFF); }

讯享网

好了，现在我们已经会计算0x88的CRC校验码了，它只是对0x做除法运算求余数而已，不过这只是求单字节的CRC校验码，那如果有十多个字节怎么办？我们的计算机也存不下那么大的数呀，看来我们还要对程序进行些改进，使它能对大数求除法了。

讯享网unsigned short crc16_div_2() { unsigned short data = 0x88; unsigned short ccitt16 = 0x1021; int i; data <<= 8; for (i = 0; i < 8; i++){ if (data & 0x8000){ data <<= 1; data ^= ccitt16; } else{ data <<= 1; } } return data; }

现在对单字节0x88求CRC16，我们只需要两字节short型的整数就行了，而不需要象以前必须用long型0x，其实不管多少字节，只用short型就能够计算它的CRC16。下面说说怎么求多字节的样验码：

unsigned short crc16_ccitt(unsigned char data, unsigned short crc) {         unsigned short ccitt16 = 0x1021;         int i;         crc ^= (data<<8);         for (i=0; i<8; i++)         {                   if (crc & 0x8000)                   {                            crc <<= 1;                            crc ^= ccitt16;                   }                   else                   {                            crc <<= 1;                   }         }         return crc; } void main() {         int i;         unsigned short crc;         char data[5] = { 0x71, 0x88, 0x93,0xa5, 0x13 };         crc = 0;         for (i=0; i<5; i++)         {                   crc = crc16_ccitt(data[i], crc);         }         printf("crc is %x", crc); }

讯享网unsigned short crc16_ccitt_r(unsigned char data, unsigned short crc) {         unsigned short ccitt16 = 0x8408;         int i;         crc ^= data;         for (i=0; i<8; i++)         {                   if (crc & 1)                   {                            crc >>= 1;                            crc ^= ccitt16;                   }                   else                   {                            crc >>= 1;                   }         }         return crc; } unsigned short crc16_ccitt_r2(unsigned char data, unsigned short crc) {         unsigned char c;         c = crc & 0xff;         crc >>= 8;         crc ^= CRC16_CCITT_R_TABLE[data ^c];         return crc; }

相关推荐