CRC-知识解析 cyclic redundancy check

写在前面的话：

之前在做学校项目的时候用到了CRC 原理，但在网上查找的过程中，发现讲解CRC知识的资源很多，但是对新手比较友好的、讲的十分清楚的又很少，很多博主也不求甚解，弄得读起来心中常常不由自主地奔腾过上千个“为什么”“为什么”，本文是我在阅读了许多资料的基础上整理、解析出来的文章，尽可能的对新手友好、解答CRC里面的一些知识点，而不是简单的应用。

依据学习目的不同，如果大家只想简单应用，不求原理，那么直接复制--粘贴最后的代码即可。

------------------------------这是一条华丽的分界线------------------------------

1. CRC 算法原理

在对信息的处理过程中，我们可以将要被处理的数据块M看成一个n阶的二进制多项式，其形式如下：

CRC校验就是基于这种多项式进行的运算，以GF(2)(The integers modulo 2)多项式算术为数学基础，即(模-2)除法的余数运算（其实说白了就是异或Xor（见2.2）），使用的除数不同，CRC的类型也就不一样。CRC传输实际上就是在长度为 k 的数据后面添加供差错检测(Frame Check Sequence) 用的 r 位冗余码（Redundant code 没错CRC里面的R就是这个），使原数据构成 n = k + r 位并发送出去, 此方式又叫（n, k）码。可以证明存在一个最高次幂为n-k=r的多项式G(x), 根据G(x)可以生成k位信息的校验码，而 G(x) 叫做这个CRC码的生成多项式( Poly )。而根据 k 值的不同，就形成了不同的CRC码的生成多项式，以下为各种常用的多项表达式：

这些多项表达式的值便是(模-2)除法的除数，本博客这里选取CRC-32多项式（即为对应除数）格式，通过取余做操，获取CRC检验码。

2. CRC 传输过程

2.1 传输原理

按 1. CRC 算法原理 所述，将长度为 k 位的数据块对应一个GF(2)多项式M，以 8 位数据块11100110举例，如果先传输MSB（Most Significant Bit），则它对应的多项式为x^7 + x^6 + x^5 + x^2 + x （8位对应x的7次幂，因为从x0 开始计数，2进制为1时有效）。发送端和接收端约定一个次数为 r 的CRC多项式，取CRC-4 为例：x^4 + x + 1，r = 4。在数据块后面加上r个0对应的多项式为M'，显然有M' = Mx^r 。用 M' 除以CRC-4 将得到一个次数等于或小于 r-1 的余数多项式 R，其对应的 r 位数值则为校验码。发送方通过指定的CRC多项式产生r位的CRC校验码，接收方则通过该CRC多项式来验证收到的报文码的CRC校验码是否为0。

具体推算如下：

设CRC多项式为G(x)：

假设发送信息用信息多项式C(x)表示，将C(x)左移 r 位，则可表示成C(x)x^r，这样C(x)的右边就会空出r位校验码的位置，使用GF(2)（模2除法），得到的余数R就是校验码。发送的CRC编码是, 至于验证接收到的报文编码是否至正确，方法依然是做模2除：，若余数为0则正确。

2.2 逻辑异或运算

CRC校验是基于多项式进行的运算，其加减法运算以2为模GF(2) ，加减时不进（借）位，实际上与逻辑异或（XOR）运算是一致, XOR是将参加运算的两个数据，按二进制位进行“异或”运算。

异或运算规则（^）规则如下：

0^0=0； 0^1=1； 1^0=1； 1^1=0；

即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

2.3 传输计算示例

以G(X)=X4+X3+1为例，设原数据为10110011。

（1）G(X)=X4+X3+1, 二进制比特串为11001。（在 X 的n 次方不为0处2的n次方的位=1 )

（2）因为校验码4位，所以10110011后面需加4个0，得到101100110000，用“模2除法” (即逻辑亦或^) 即可得出结果：

（3）即CRC^101100110000得到101100110100，并发送到接收端。

（4）接收端收到101100110100后除以11001(以“模2除法”方式去除),余数为0则无差错。

3. CRC 的实现（Reversed 反向校验模式）

一般来说CRC有多种实现方式，在本文中我们以C语言为例，并给出 直接生成法 和 查表法 两个例子。

直接生成法 适用于 CRC 次幂较小的格式，当CRC 次幂逐渐增高时，因为其复杂的Xor 逻辑运算会拖累系统运行速度，不再建议使用直接生成法，取而代之的是查表法——将数据块M 的一部分提前运算好，并将结果存入数组中，系统开始执行运算时，相当于省去了之前的操作，直接从类似中间的位置开始计算，所以会提高效率。

在计算CRC时也可以选择正向校验（Normal） 或者反向校验（Reversed），由于 Normal 和 Reversed 是镜像关系，两种方法会影响到最后的校验码，使得两种方式最后得到的校验码呈现镜像关系。但这对CRC 本身的成功率并没有影响，只不过是：正向走一遍，还是镜像走一遍罢了。

那为什么还会有Reversed格式呢？是因为在大多数硬件系统的传输中，普遍先发送LSB，而Reversed 的CRC 正是满足于这种LSB First 的格式，因此适用。

下面为计算过程：

设数据块为Mx, CRC校验式为G(x) FCS位数为 r。

如下表所示，当采取反向校验设计时, 需进行以下操作：

Name	Polynomial Representations
Name	Normal	Reversed	Reciprocal	Reversed reciprocal
CRC-3-GSM	0x3	0x6	0x5	0x5
CRC-8	0xD5	0xAB	0x57	0xEA
CRC-16-CCITT	0x1021	0x8408	0x811	0x8810
CRC-32	0x04C11DB7	0xEDB88320	0xDB710641	0x82608EDB

（1）将翻转后的Mx^r的后r位放入一个长度为r的寄存器中；

（2）如果寄存器的首位为1，将寄存器右移1位(将Mx^r剩下部分的MSB移入寄存器的MSB（高八位）)，再与G(x) 的后r位异或，否则仅将寄存器右移1位(将Mx^r剩下部分的LSB（低八位）移入寄存器的LSB)；

（3）重复第2步，直到M全部 Mx^r 移入寄存器；

（4）寄存器中的值则为校验码。

代码如下（基于C语言）：

复制代码

#include<stdio.h>unsigned int CRC32_table[256] = {0};void init_CRC32_table()
{for (int i = 0; i != 256; i++){unsigned int CRC = i;for (int j = 0; j != 8; j++){if (CRC & 1)CRC = (CRC >> 1) ^ 0xEDB88320;elseCRC >>= 1;}CRC32_table[i] = CRC;}
}unsigned int GetCRC32(unsigned int crc, unsigned char *data, unsigned int size)
{for (unsigned int i = 0; i < size; i++){crc = ((crc >> 8) & 0xFFFFFF) ^ CRC32_table[(crc ^ data[i]) & 0xFF];}return crc;
}int main()
{// 初始化数据表init_CRC32_table();printf("CRC32 TABLE:\n");for(int i=0;i<256;i++){printf("0x%08x ",CRC32_table[i]);if((i+1)%8 == 0) printf("\n");}printf("\n");// 计算CRCunsigned char data[8] = {0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};printf("BUFFER i's CRC32: 0x%x\n", ~GetCRC32(0xffffffff, data, 8));// 分段计算unsigned int crc = 0xffffffff;for(int i=0; i<4; i++){crc = GetCRC32(crc, data+i*2, 2);}printf("BUFFER i's CRC32: 0x%x\n", ~crc);
}

复制代码

4. 生成多项式的选择

不同的CRC生成多项式，其检错能力是不同的。要使用R位校验码，生成多项式的次幂应为R。同时生成多项式应该包含项"1"，否则校验码的LSB(Least Significant Bit)将始终为0。如果数据块M (包括校验码) 在传输过程中产生了差错，则接收端收到的消息可以表示为M +R’。若R’ 不能被CRC 生成多项式G 除尽，则该差错可以被检测出。考虑以下几种情况：

1) 1位差错，即R’ = x^n = 100...00，n >= 0。只要G至少有2位1，R'就不能被G除尽。这是因为G x^k相当于将G左移k位，对任意多项式Q，QG相当于将多个不同的G的左移相加。如果G至少有两位1，它的多个不同的左移相加结果至少有两位1。

2)奇数位差错，只要G含有因子F = x + 1, R' 就不能被G除尽。这是因为QG = Q'F，由1)的分析，F的多个不同的左移相加结果1的位数必然是偶数。

3)爆炸性差错，即R' = (x^n + ... + 1)x^m = 1...100...00，n >= 1，m >= 0，显然只要G包含项"1"，且次数大于n，就不能除尽R'。

4)2位差错，即R' = (x^n + 1)x^m = 100...00100...00，n >= 0。设x^n + 1 = QG + R，则R' = QGx^m + Rx^m，由3)可知R'能被G除尽当且仅当R为0。因此只需分析x^n + 1，对于次数R，总存在一个生成多项式G，使得n最小为2^R - 1时，才能除尽x^n + 1。称该生成多项式是原始的(primitive)，它提供了在该次数上检测2位差错的最高能力，因为当n = 2^R - 1时，x^n + 1能被任何R次多项式除尽。

------------------------------这又是一条华丽的分界线------------------------------

5. Q & A

Q: 为什么寄存器初始化置0？

A: 寄存器的初始值不为 0，那么寄存器中的值就相当于是待测数据，这样算出的 CRC 结果并不正确。再考虑CRC32 模型的 Init=0xFFFFFFFF，待测数据的内容和长度为随机，如果寄存器初始值为 0，那么待测字节则为 1 字节 0x00，计算出来的 CRC32 值也就为 0。寄存器用0xFFFFFFFF 进行初始化，就可以避免这个问题

Q：为什么先移位再XOR？

A: 0xEDB88320已经是Gx 去掉最高项的简写，为了确保运算无误，所以需要先移位再XOR。这不会影响最后的结果，因为在做XOR运算时，gx 的最高位都会被消掉（因为在除法运算中每次循环都是从1 开始除，而gx 的最高项就是1，所以每次都会被消掉）

Q: 查表法的index 是什么，而内容又是什么？

A: Index 为数据块M 的前8位，内容是前8位与CRC XOR后的值，用时需再与gx异或。

Q: 查表法为什么会有256个字符？

A: 在CRC-16和32中，一次移出的待测数据为 8 位 bits，即一次进行一个字节的计算，则表格有 2^8＝256 个表值。一个字节有8位二进制数，每一位都有2种选择。