CRC 循环冗余校验算法

本文由 简悦 SimpRead) 转码， 原文地址 mp.weixin.qq.com)

（给算法爱好者加星标，修炼编程内功）

来源：Mr Bluyee

概述

循环冗余校验（Cyclic redundancy check，通称 “CRC”）是一种根据网络数据数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。

原理

CRC 校验（循环冗余校验）是数据通讯中最常采用的校验方式。在嵌入式软件开发中，经常要用到 CRC 算法对各种数据进行校验。

奇偶校验

奇偶校验是 CRC 校验的一种 (CRC-1)。RS232 串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中 1 的个数为奇数个或偶数个。比如我们要发送的字节是 0x1a，二进制表示为 0001 1010。

• 采用奇校验，则在数据后补上个 0，数据变为 0001 1010 0，数据中 1 的个数为奇数个（3 个）
• 采用偶校验，则在数据后补上个 1，数据变为 0001 1010 1，数据中 1 的个数为偶数个（4 个）

接收方通过计算数据中 1 个数是否满足奇偶性来确定数据是否有错。

奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有 50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。

累加和校验

另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子：

我们要传输的信息为：6、23、4
加上校验和后的数据包：6、23、4、33

这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。

加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有 1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为 CRC 校验在传输数据的形式上与累加和校验是相同的，都可以表示为：通讯数据 校验字节（也可能是多个字节）。

CRC 算法

CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。CRC 算法中，将二进制数据流作为多项式的系数，然后进行的是多项式的乘除法。

下面是一个例子：

`要传输的数据为：1101011011``除数设为：10011``在计算前先将原始数据后面填上4个0：11010110110000` `1100001010` `——————————————``10011)11010110110000` `10011` `——————————————` `10011` `10011` `——————————————` `10110` `10011` `——————————————` `10100` `10011` `——————————————` `1110`

从这个例子可以看出，采用了模 2 的加减法 (异或运算符) 后，不需要考虑借位的问题，所以除法变简单了。最后得到的余数就是 CRC 校验字。为了进行 CRC 运算，也就是这种特殊的除法运算，必须要指定个被除数，在 CRC 算法中，这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题，如果选的不好，那么检出错误的概率就会低很多。

最常用的几种生成多项式如下：

• CRC8 = X^8 + X^5 + X^4 + X^0 = 1 0011 0001 (0x31)
• CRC12 = X^12 + X^11 + X^3 + X^2 + X^0 = 1 1000 0000 1101 (0x080D)
• CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 1 0001 0000 0010 0001 (0x1021)
• CRC16 = X^16 + X^15 + X^2 + X^0 = 1 1000 0000 0000 0101 (0x8005)
• CRC32 = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X^1 + X^0 = 1 0000 0100 1100 0001 0001 1101 1011 0111 (0x04C11DB7)

生成多项式经常会说到多项式的位宽（Width，简记为 W），这个位宽不是多项式对应的二进制数的位数，而是位数减 1。比如 CRC8 中用到的位宽为 8 的生成多项式，其实对应的二进制数有九位：100110001。

另外一点，多项式表示和二进制表示都很繁琐，交流起来不方便。

因此，多用 16 进制简写法来表示，因为生成多项式的最高位肯定为 1，最高位的位置由位宽可知，故在简记式中，将最高的 1 统一去掉了，如 CRC32 的生成多项式简记为 04C11DB7 实际上表示的是 104C11DB7。当然，这样简记除了方便外，在编程计算时也有它的用处。

对于上面的例子，位宽为 4（W=4），按照 CRC 算法的要求，计算前要在原始数据后填上 W 个 0，也就是 4 个 0。

位宽 W=1 的生成多项式 (CRC1) 有两种，分别是 X1 和 X1+X0，10 对应的就是奇偶校验中的奇校验，而 11 对应则是偶校验。

原始 CRC 算法

假设生成多项式 (被除数) 为：100110001（简记为 0x31），也就是 CRC-8，
原始 CRC 计算步骤如下：

• 1. 将 CRC 寄存器（8-bits，比生成多项式少 1bit）赋初值 0
• 1. 在待传输信息流后面加入 8 个 0
• 3.While (数据未处理完)
• 4.Begin
• 5.—If (CRC 寄存器首位是 1)
• 6.——reg = reg XOR 0x31
• 7.— CRC 寄存器左移一位，读入一个新的数据于 CRC 寄存器的 0 bit 的位置。
• 8.End

CRC 寄存器就是我们所要求的余数。
实际 C 代码如下：

`unsigned char crc8_gen(unsigned char *data,unsigned char length){` `int j;` `unsigned char crc_reg = 0;` `while(length--){` `crc_reg ^= *data++;` `for(j=0;j<8;j++){` `if(crc_reg & 0x80){` `crc_reg = (crc_reg << 1) ^ 0x31;` `}else{` `crc_reg = crc_reg << 1;` `}` `}` `}` `return crc_reg;``}`

实际上，真正的 CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的 CRC 除法有个很明显的缺陷，就是数据流的开头添加一些 0 并不影响最后校验字的结果。因此真正应用的 CRC 算法基本都在原始的 CRC 算法的基础上做了些小的改动。所谓的改动，也就是增加了两个概念，第一个是 “余数初始值”，第二个是 “结果异或值”。

所谓的 “余数初始值” 就是在计算 CRC 值的开始，给 CRC 寄存器一个初始值。“结果异或值”是在其余计算完成后将 CRC 寄存器的值在与这个值进行一下异或操作作为最后的校验值。

实际 CRC 算法

实际 CRC 计算步骤如下：

• 设置 CRC 寄存器，并给其赋值为 “余数初始值”。
• 将数据的第一个 8-bit 字符与 CRC 寄存器进行异或，并把结果存入 CRC 寄存器。
• CRC 寄存器向左移一位，LSB 补零，移出并检查 MSB。
• 如果 MSB 为 0，重复第三步；若 MSB 为 1，CRC 寄存器与 0x31 相异或。
• 重复第 3 与第 4 步直到 8 次移位全部完成。此时一个 8-bit 数据处理完毕。
• 重复第 2 至第 5 步直到所有数据全部处理完成。
• 最终 CRC 寄存器的内容与 “结果异或值” 进行异或操作后即为 CRC 值。

实际使用中除了寄存器初始值、结果异或值外还有字节颠倒的标记 RefIn 和 RefOut：

所谓颠倒意思是字节数左右取反，例如 11010010，字节颠倒后变为 01001011。

RefIn：这是个 BOOL 值，表示字符串是否进行了字节颠倒。某些硬件传输时使用 LSB 模式，即先传输低位的 bit，这样使用 MSB 模式收到的字节就是颠倒的。假如 A 传输的是 1000 0000，但是底层硬件传输时按照 0000 0001 的顺序传给 B，B 的传输模式是 MSB，即认为接收的第一个 bit 是高位 bit。那么本来应该是 0x80，但是 B 却认为它接收的是 0x01。

对于这种情况，在做 crc 之前把每一个字节颠倒过来就好了。但是这么做将浪费大量时间和工作量，于是出现了颠倒 crc 算法，即除了源串字节不进行颠倒以外，初始值、poly、进寄存器方向、最后的 crc 结果都进行颠倒。这样与费时费事的颠倒每个字节计算的结果完全一致。

RefOut：颠倒输出结果。

常见 CRC 参数模型如下：

实现 CRC 算法主要有逐位计算和查表两种，逐位计算效率比查表低很多。具体算法实现将在后续章节给出。

• EOF -

推荐阅读 点击标题可跳转

1、算法题：奇偶分割数组

2、古代密码学与信息安全

3、表白后，女生发给我一串五层加密的密码

觉得本文有帮助？请分享给更多人

关注「算法爱好者」加星标，修炼编程内功

点赞和在看就是最大的支持❤️