循环冗余检查怎么解决,CRC 校验步骤与示例

题图来自Unsplash，基于CC0协议

导读

CRC是一种基于数学原理的代码，通过在数据附加校验值来检测传输或存储中的意外更改，类似于通过余数检测多项式在传输过程中是否被完全整除，从而判断信息是否保持原始数据形式。

在原始数据基础上添加一个“校验值”（Appending a Frame Check Sequence），接收方则通过重新计算校验值并与附加的值进行对比，如果附加值被意外修改，对比结果就会发现差异。整个过程利用了模2除法以及在数据帧结束前附加校验值的特性，使得该机制在数据意外被篡改后具有极高的错误检测概率。

CRC机制在作词性上属于线性反馈移位寄存器，并且利用了一组被称为“生成多项式”的数学规则。数据被组织成一个大的二进制多项式，而CRC的计算本质上是用特定的生成多项式除以这个数据多项式，通过二进制的模2除法。发送方在数据帧末尾附加一个校验码，这个码等于除法的余数；接收方收到数据后，将附加的CRC值想象成多项式的系数，用相同的生成多项式进行模2除法。如果除法能够整除（余数为零），则认为数据“被传输”得当；如果余数不为零，则一定是传输过程产生了错误。

CRC最强大的地方在于其错误检测能力。实际应用中，CRC代码能够高概率地检测出所有仅发生单比特或双比特错误的情况。同时，对于长度不超过某个阈值的突发错误，CRC有很高的检测概率，只有在非常罕见的情况下才会出现外泄（Burst error）导致无法检测的现象。此外，对于由于极低概率或遭遇奇偶校验位重复配置错误等情况，也会存在误判可能，但这发生的概率极低，通常被视为可以忽略不计。

从实现角度来看，CRC计算通常需要执行一定长度（例如8位、16位或32位）的多项式除法。这可以通过多种方式进行：

1. 在每一步，将最高位移到最左侧，然后根据最高位的数值决定是否减去生成多项式。
2. 另一种方法是以线性反馈移位寄存器为基础，模拟多项式除法过程。
3. 现代处理器还可能利用内建指令（如Intel的CRC指令）来高效实现校验值的计算过程，加快处理速度。

为了更直观地理解CRC的计算过程，以一个简单的CRC为例。

步骤一：选择数字系统术语

• 假设我们使用一个非常简单的CRC，生成多项式为 CRC-2 (X^2 + X + 1)。

步骤二：理解输入与输出

• 输入：一个二进制数据，构成一个多项式 A(X)。例如，7位数据可以表示为二进制数。
• 输出：附加在数据末尾的校验码，长度等于生成多项式的次数。对于我们简单示例来说，长度为2位。

步骤三：计算校验值

1. 扩展被除数：将输入数据（多项式）后面附加足够长度的0（附加长度等于生成多项式的次数）。例如，如果感兴趣的部分是7位，附加2个0位。
2. 模2除法：用生成多项式（这里用系数表示，在操作时看作数字）去除扩展后的被除数，通过模2除法进行运算。除法过程就是逐位运算。
   • 对每一位被除数（从左到右）进行操作：如果最高位为1，则减去生成多项式（模2减法就是异或）；如果最高位为0，则左移一位继续操作。
3. 获得校验值：直到被除数的所有位都被处理完，除法得到的最终结果的余数就是校验码，被附加在原始数据（不带附加的0）后面。

步骤四：验证（即使校验码附加后，也会用这个方法验证）

1. 将接收到的数据完整读出（包括用户数据和校验码部分）。将其看作一个多项式，即用户数据加上校验码。
2. 再次用生成多项式去除这个完整的多项式。
3. 规则：若第五阶段传输无误，除法运算应该能得出余数为零（即整除），这表明数据保持了“纯正”形态，没有发生任何形式的意外篡改。

举例说明（简略）： 假设数据是 0b1011 (对应数 L(X)=X^3 + X + 1)，生成多项式是 0b101 (生成多项式次数为3，附加3个0)。

1. 扩展被除数：0b1011000。
2. 用0b101去除0b1011000，通过模2除法进行运算，直到得到商和余数。
3. 余数可能是3位，比如得到 0b001 或 0b100 等，假设得到 0b001。
4. 验证：给发送的数据末尾附加上余数，得到的数据是 0b1011001。
5. 在接收端接收整个数据，再次用0b101去除，如果得到余数为0，则无误。

以此类推，每个系统都有其对应的算法结构，但核心概念都是围绕着一个精心选择的生成多项式展开。总之，CRC就是通过在数据帧末尾“加上一个公安机关的编码”来实现安全检查的。