CRC校验(1)：CRC原理、计算例子和最优多项式的选择
CRC校验(1)：CRC原理、计算例子和最优多项式的选择
CRC（Cyclic Redundancy Check），即循环冗余校验，它通过计算生成固定长度的校验码，用于验证数据在传输过程中是否发生了错误或损坏，从而确保数据的完整性。假设我们想把小写字母z发送出去。在Unicode中，z由数字0x7A表示，二进制为0111 1010。为了使接收方能够验证数据在传输时有没有被修改，我们计算出该数据的CRC为1000，并附加到我们的消息之后：0111 1010 1000。这个校验值1000被称为冗余，因为它是在原来数据的基础上增加的。
1 CRC计算
1.1 多项式
从数学上讲，CRC是数据的模二多项式（polynomial）除法的余数。因此，CRC可以写成：
CRC = data % 2 polynomial
该多项式可以是任何数学多项式（没有任何系数），但是它的最高指数不能超过CRC的位数。比如我们要生成一个8位CRC，那么多项式的最高指数也必须是8，比如：x8 + x2 + x + 1。而多项式都可以转换成二进制来表示，实际上就是看从每个指数是否存在，存在则为1，不存在则为0。比如说x8 + x2 + x + 1转换成二进制为100000111。
- 选择不同的多项式将导致相同数据产生不同的CRC。所以发送方和接收方需要使用共同的多项式
- 对于CRC来说，根据具体的使用场景，有些多项式比其他多项式更适合使用。例如，某些多项式可能更容易检测出连续位错误或交替位错误。
接下来，为了能够计算CRC，我们需要了解模二除法。
1.2 模二除法计算及例子
（1）模二运算
模二运算是对二进制数逐位进行的运算。在这种运算中，不存在进位或借位，每个位被视为独立于其相邻位的数字。实际上就是C语言中的异或运算：
bit1 bit2 XOR
0 0 0
0 1 1
1 0 1
1 1 0
（2）模二除法
模二除法的执行类似于算术除法，唯一的区别是我们使用模二减法（XOR）而不是算术减法来计算每一步的余数。假设被除数为100100，除数为1101，下面来看一下如何计算出CRC：
- 计算除数的长度为L，这里为4。
- 在被除数的后面加上L-1位，这里为3，这也是CRC的长度。注意：除数的最高位必须为1，附加的位数就对应二项式中的最高指数：x3 + x2 + 1
- 用二进制模二进行计算，得到的余数即CRC的结果：
001
1.3 CRC类型
CRC类型由其位大小命名。常见的有：CRC-8、CRC-16、CRC-32、CRC-64和CRC-1（奇偶校验位的特例）。显然对于同一个类型，不同的多项式也有不同的结果。比如对于被除数01000001来说，它的CRC-8在不同的多项式下的结果如下：
二进制多项式 CRC-8
110100111 11001100
100000111 11000000
101001001 01100110
111010101 01001000
- 以上是在蓝牙、GSM-B等不同应用中使用的标准CRC-8多项式
2 多项式的选择
我们应该如何选择合适的CRC和相应的多项式？有三个方面需要考虑：随机错误检测精度、突发错误检测精度和冗余系数。
（1）随机错误检测精度
随机错误是指在数据中随机出现的错误。例如，在传输数据时，单个比特被翻转，或者在传输过程中丢失几个比特。根据我们使用的CRC的位大小，我们可以检测到大多数这些随机错误。然而，对于CRC-n来说，这些错误的1/2n不能被检测到。下表显示了每种CRC类型未检测到错误的百分比：
CRC 不可检测错误 百分比%
CRC-8 1/2^8 0.39
CRC-16 1/2^{16} 0.0015
CRC-32 1/2^{32} 0.00000002
CRC-64 1/2^{64} 5.4×10^{-20}
（2）突发错误检测精度
数据传输中的错误通常不是随机的，而是连续的出现几个位的错误，这种错误称为突发错误，它是数据通信中最常见的错误。
CRC-n可以检测最大长度为n位的单突发错误。然而，这在很大程度上取决于用于计算CRC的多项式。有些多项式能够检测到传输数据中的多个突发错误。
CRC 突发差错检测
CRC-8 至少出现一个连续的错误突发,但这个长度≤8位
CRC-16 至少出现一个连续的错误突发,但这个长度≤16位
CRC-32 至少出现一个连续的错误突发,但这个长度≤32位
CRC-64 至少出现一个连续的错误突发,但这个长度≤64位
（3）冗余系数
使用CRC进行错误检测的代价是要增加额外的数据。比如CRC-32要比CRC-16多传输两个额外的字节。显然，比特位数较低的CRC只需要计算和存储更少的位数。
基于这三个因素，我们可以决定选择哪种CRC类型用于我们的应用程序。然而，CRC多项式也会影响错误检测的效率和质量。如果要深入研究的话，将是一个很复杂的话题，本文不做研究。幸运的是，网上有很多种用于特定CRC类型的标准多项式，在大多数情况下，使用其中之一就能有不错的检错效果。
3 总结
CRC校验在做项目的过程中经常会使用到，在我上大学的时候有浅浅地理解这个计算的过程，但我希望能理解其中的原理，所以写了这篇文章，下一篇，我将介绍CRC32的查表法实现。