一、信息论中的 CRC

我上大学的时候，有一门课程叫做信息论，我就是从这个课程中学到的 CRC 校验这个词的，没错，当时学完整个课程后，CRC 对我来说依然只是一个单薄的缩写词语，全称我都不知道是啥。

CRC 全称是循环冗余校验（Cyclic Redundancy Check）。

说到信息论中的码可真是数不胜数，信源编码，信道编码，校验码，纠错码，无损失的霍夫曼编码，有损的熵编码等等，话说当时我还是手工计算过霍夫曼编码，现在也确实不知道哪里会用到。

这个 CRC 编码应该属于信息论中的信道编码中的校验码，它没有纠错能力，主要是对信道传输过程中做一个信息完整性的检验。

回到我们的产品开发中，我们可能最先接触的是奇偶校验，累加和以及 CRC 编码，而并不是什么信道编码和检错码。

奇偶校验：

奇偶校验码常用来做串口通信的校验，它一种简单的检错码，用于检测数据传输中的错误。

它通过在数据中增加一个额外的bit，使得整个数据块中1的个数（或0的个数）为奇数（或偶数），从而实现简单的错误检测。

如果接收端接收到的数据中奇偶校验位与发送端发送的数据中的奇偶性不一致，就说明在传输过程中可能出现了错误。

累加和校验：

累加和校验也称为求和校验或加法校验，它也是一种简单的校验方法，它的原理是将数据中的所有字节（或比特）相加，并将结果附加到数据的末尾进行传输。

接收端对接收到的数据进行相同的操作，然后比较计算得到的校验和是否相同，以判断数据是否在传输过程中发生了错误，这种校验和在 IP 协议中有部分使用。

不足：

以上两种算法都是非常简单的，无论是计算 0 或者 1 的个数，还是两端同时做加法运算都避免不了失误。

在奇偶校验中如果两个 bit 异位就会被判断为正确，这发生的概率非常大。

而在累加和校验中，如果出现两个字节错误，且他们的累加和和原值的累加和相等，最终也会被判断为完整，这个概率相对于奇偶校验要小很多，但是对于大数据量，糟糕的信道环境中的传输还是不够的。

我们来看看 CRC 校验是怎么提升这个检错能力的。

二、CRC 循环校验码的原理方法

CRC算法是以GF(2)(模 2 除法求余数)多项式算术为数学基础的。

我们先看多项式是怎么来的！

假设我们有一段数据需要传输，数据是二进制的 10100111，那么我们以 x 为变量，定义如下的一个多项式：

1x^7 + 0x^6 + 1x^5 + 0x^4 + 0x^3 + 1x^2 +1x^1 + 1x^0

可以看出，数据就是多项式的系数，每个 bit 对应到的是 x 的对应指数项的系数，这个系数非 0 即 1，因此多项式可以简化为：

x^7 + x^5 + x^2+ x + 1

这样是不是就很像我们平时看到的 CRC 校验的多项式了。上面这个是 8bit 的多项式，最高次幂为 7，对应的 16bit 的多项式中，最高次幂就为 15 了。

什么是模 2 除法求余呢？

多项式中的加减法，使用模2算术执行对应项上系数的加减，模2就是指的加减时不考虑进位和借位。

即：

0 + 0 = 0 0 - 0 = 0

0 + 1 = 1 0 - 1 = 1

1 + 0 = 1 1 - 0 = 1

1 + 1 = 0 1 - 1 = 0

总结一下规律可以得出，这种加减法的运算正好等同于我们计算机中的异或运算，数学理论是基础，我们这里可以记住异或运算就好了。

多项式乘法和一般多项式乘法也是一样的，只是在各项相加的时候按模2算术相加进行，例如：

(x^3 + x^2 + 1)(x^3 + x^1 + 1)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x + 1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

换成除法，我们也可以通过列一下二进制的除法算式来求余数，我们把包含 n 次幂的项省略掉。

上面的除法就是我们用在 CRC 中做运算用的，我们看看 CRC 的逻辑

假如我们需要传输一个长度为 k 位的数据块，它对应的多项式我们称为 M，按照上面图片中的除法运算，我们需要传输的 8bit 数据为：11100110。假设我们传输 MSB，则它对应多项式为 x^7 + x^6 + x^5 + x^2 + x。最后没有常数项 1，因为最后一个 bit 为 0。

这时候，发送信息的一端和接收信息的一端就要约定一个多项式 G。假设按照上图除法中的数据，我们这里使用的就是 CRC-3（一般没有，是为了适合上图的除式），取多项式为x^3 + x + 1，最高次幂为r = 3。

这时候，发送端先在 M 后面添加 r = 3 个 0，标记为 Mx，然后我们使用 Mx 除以 G 将得到一个次数等于或者小于 r - 1 的余数多项式，我们标记为 R 多项式，这个 R 对应的 bit 串就是校验码。

发送端会将原始数据和校验码一起发送出去，接收端则按照同样的方式进行计算余数 R，然后判断和接收到的是否相同来检验传输是否有错误。

细心的你会发现，这里的原理和校验和其实是一样的，差别在于校验和是累加，这里是对一个多项式 G 做除法。

而这个多项式 G 是可以任意定义的，不同的多项式的检验错误的能力是不同的，校验过程中的运算是不同的。

基于此，很多行业形成固定的多项式，一般我们开发时遵循他们就可以了：

三、CRC 循环校验的代码分析

我们如何用程序来计算这个CRC 的除法呢？

1. 将Mx^r的前r位放入一个长度为r的寄存器；
2. 如果寄存器的首位为1，将寄存器左移1位(将Mx^r剩下部分的MSB移入寄存器的LSB)，再与G的后r位异或，否则仅将寄存器左移1位(将Mx^r剩下部分的MSB移入寄存器的LSB)；
3. 重复第2步，直到M全部Mx^r移入寄存器；
4. 寄存器中的值则为校验码。

我们用下面这个式子来看一下过程

通过上面的模拟寄存器操作，我们就得到了一个校验码，理论上无论多少个 bit 的数据块，对我们 4bit 的多项式做除法最后都会得到一个4bit 可以存放的校验码，我们就把他挂在我们的数据块尾巴上送出去。

只要发送接收到的多项式一致，就可以根据这个校验码来进行完整性校验了。

这部分代码的实现，我之前讲过，在我的 从 0 到 1 完成 BMS 保护板设计专辑里面。

I2C 驱动及其 Checksum在 BMS 系统中的应用

文章里面讲到，TI 规定的 CRC8 的多项式为：x^8 + x^2 + x +1，对应可知多项式 G 的 Key 为100000111。

由于我们在算法中是先左移再做异或，因此最高位可以去掉，对应到我们程序中的参数 key 就是 00000111, 16 进制为 0x7。

static u8 CRC8(u8 *ptr, u8 len, u8 key)

{
    u8 i;
    u8 crc = 0;
    while(len-- != 0) //按照数据长度进行CRC计算
    {
        for(i=0x80; i!=0; i>>=1) //右移位8次
        {
            if((crc & 0x80) != 0) //crc高bit不为0，crc异或key
            {
                crc <<= 1;
                crc ^= key; 
            }
            else
                crc <<= 1;
            if(((*ptr) & i) != 0) //字节中bit不为0，crc异或key
                crc ^= key;
        }
        ptr++; //下一个字节
    }
    return(crc);
}

这是对于 CRC8 的循环校验算法，看起来比较简单，移位几次，异或几次就可以了，但是当我们把校验位数增加到 CRC32 的时候，这个算法就复杂起来，因此很多 MCU，比如 STM32 就内置了硬件的 CRC 校验。多项式也可以自定义，使用起来还是很灵活的。

如果没有硬件帮忙，我们解决 CRC32 校验的问题可以通过查表法。制作这个表的方法其实就是上面这样的移位和异或算法。简化的写法如下：

unsigned int CRC;//int的大小是32位，作32位CRC寄存器
unsigned int CRC_32_Table[256];//用来保存CRC码表
void GenerateCRC32_Table()
{
   for(int i=0;i<256;++i)//用++i以提高效率
   {      
       CRC=i;
       for(int j=0;j<8;++j)
         {
             if(CRC&1)// LSM为1
                 CRC=(CRC>>1)^0xEDB88320;//采取反向校验
             else //0xEDB88320就是CRC-32多项表达式的reversed值
                 CRC>>=1;
         }
     CRC_32_Table[i]=CRC;
  }
}

看到没，我们先把一个字节可以表示的 256 个数对应的校验和计算出来了，我们的通信往往都是以字节为单位进行传输的，那么我们有了这样的表后，就相当于直接有了一个 8bit 数及其 CRC32 校验码的映射表，直接查表速度极快。

以上就是对 奇偶校验，累加和校验和 CRC 校验的理解。

更多技术讨论，可以看我主页呀