循环冗余检查循环冗余码(CRC)及计算方法

大飞知识 2024-12-26 20:38:16 3浏览

关于CRC算法的详细解析

CRC，即循环冗余校验，是一种用于数据包或保存文件的校验与纠错算法。它利用除法和余数原理，通过计算获取校验数据，并重新组合成新的数据包。

在数据传输过程中，发送端会通过CRC算法计算数据的冗余部分，然后将这部分数据打包进新的数据包中发送出去。接收端在接收到数据包后，会运用同样的CRC算法对数据进行校验。只有当CRC校验的余数为0时，才证明传输的数据是正确的。

以下为CRC数据处理的一个示意图。在原始数据（K bit）后增加校验数据（R bit），便构成了新的数据包（(K+R) bit）。而这个校验数据，实际上是原始数据经过除法运算后的余数。

发送端数据的CRC处理主要包括以下五个步骤：

1. 确定CRC对应的除数及多项式

基于模2除法，必须有一个二进制除数。这个二进制除数与一个特定的多项式存在对应关系。

例如，二进制除数为“1101”对应的多项式为G(x) = X^3 + X^2 + 1。

这个多项式通常是由发送端和接收端共同商定，标准的CRC算法多项式可参考下表。

2. 确定CRC校验数据的位数

校验数据实际上是除法运算后的余数，因此需要明确余数的位数。

多项式的最高次幂即对应了余数的位数。

如G(x) = X^3 + X^2 + 1的最高次幂为3，因此余数（即校验数据）的位数为3。

3. 移位并补充校验位

将原始数据左移R bit（R为校验数据的位数），并在低位补0。

例如，原始数据为“10011010”，若校验数据位数为3，则左移3位得到新的数据“10011010_000”。

4. 计算CRC校验数据

使用先前确定的除数，对移位后的数据进行模2除法运算（实际上是一种异或运算）。得到的余数即为CRC校验数据。

例如，对于上述的移位后数据“10011010_000”，通过模2除法运算得到的余数为“0101”，考虑到我们只需要3位的余数，因此实际校验数据为“101”。

5. 组成新的数据包

将计算出的CRC校验数据添加到原始数据的末尾，组成新的数据包。

如新数据包格式为：原始数据 + 校验数据（余数），即“10011010_101”。

接收端在接收到数据包后，将使用相同的多项式（如G(x) = X^3 + X^2 + 1）进行异或运算。如果余数为0，则说明数据传输无误。