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 是可以任意定义的，不同的多项式的检验错误的能力是不同的，校验过程中的运算是不同的。
基于此，很多行业形成固定的多项式，一般我们开发时遵循他们就可以了：
|
楼主
标题置顶
标题高亮
