【算法】深入了解 CRC 校验码的计算过程
引言
在通信和数据存储过程中，数据的完整性至关重要。为了检测和纠正传输错误，校验技术被广泛应用。CRC（循环冗余校验，Cyclic Redundancy Check）是一种常见的错误检测方法，它通过生成冗余码来确保数据传输的可靠性。在这篇文章中，我们将探讨 CRC 码的基本原理，并详细介绍其计算过程。
CRC 校验码的原理
CRC 校验基于 模 2 除法 原理，它将数据视为二进制数串，然后通过一个预定的 生成多项式 来计算数据的余数。这个余数就是 CRC 校验码。具体过程如下：
- 数据二进制表示：将待校验的数据转换为二进制表示。
- 生成多项式：选择一个生成多项式，这是 CRC 算法的核心。常用的多项式包括 CRC-32、CRC-16 等。
- 附加零位：在数据末尾附加若干个零位，这些零位的个数取决于生成多项式的位数。
- 模 2 除法：将附加了零位的数据通过生成多项式进行二进制除法运算，得出的余数就是 CRC 校验码。
CRC 计算的步骤
-
确定生成多项式 CRC 的生成多项式是一组预定义的位模式。例如，对于 CRC-16，多项式可以表示为： $G(x) = x^{16} + x^{15} + x^2 + 1$
在二进制表示中为
11000000000000101。 -
附加零位 假设待校验的数据为 8 位，例如
11010101，生成多项式为 16 位，则我们需要在数据后面附加 16 个零，得到： $11010101 \text{0000000000000000}$ -
进行模 2 除法 将附加零的数据与生成多项式进行二进制除法。注意，二进制除法与十进制不同，不涉及借位和进位，直接进行异或运算。
示例：
11010101 0000000000000000 ÷ 11000000000000101通过逐步执行除法过程，我们将得到一个 16 位的余数。这就是 CRC 校验码。
-
校验码生成 最终的余数作为 CRC 校验码，附加到原始数据之后。这个新的数据包在传输时，如果接收方再次计算 CRC 校验码并与附带的校验码进行比较，可以确定数据是否在传输过程中出现了错误。
代码实现
我们可以通过 Python 来实现 CRC 校验码的计算。以下代码演示了使用 CRC-16 算法的计算过程。
def crc16(data: bytes, poly=0x11021, init_val=0xFFFF) -> int:
crc = init_val
for byte in data:
crc ^= byte << 8
for _ in range(8):
if crc & 0x8000:
crc = (crc << 1) ^ poly
else:
crc <<= 1
crc &= 0xFFFF # 取16位
return crc
# 示例
data = b"Hello, CRC!"
crc_value = crc16(data)
print(f"CRC-16 计算结果: {crc_value:04X}")
结论
CRC 校验是一种强大的错误检测工具，广泛应用于通信协议、数据存储和网络传输中。通过对数据进行 CRC 校验，我们可以在传输过程中检测到潜在的错误并采取适当的纠正措施。理解 CRC 的计算过程有助于我们更好地使用这种技术，并根据需要优化相关应用。