跳到主要内容

循环冗余校验(CRC)

什么是循环冗余校验(CRC)？​

循环冗余校验（Cyclic Redundancy Check，简称CRC）是一种用于检测数据传输或存储过程中是否发生错误的技术。它通过生成一个固定长度的校验码（通常称为CRC码），并将其附加到原始数据中。接收方可以使用相同的算法对接收到的数据进行校验，以验证数据的完整性。

CRC广泛应用于数据链路层协议中，如以太网、Wi-Fi和蓝牙等，以确保数据在传输过程中未被篡改或损坏。

CRC的工作原理​

CRC的核心思想是将数据视为一个二进制多项式，并通过一个预定义的生成多项式对其进行除法运算。计算得到的余数就是CRC码。以下是CRC的基本步骤：

  1. 选择生成多项式：生成多项式是一个预定义的二进制数，用于计算CRC码。不同的CRC标准使用不同的生成多项式。
  2. 附加零位：在原始数据的末尾附加与生成多项式位数减一相同数量的零位。
  3. 多项式除法：将附加零位后的数据与生成多项式进行模2除法运算，得到余数。
  4. 生成CRC码：将余数附加到原始数据的末尾，形成最终的传输数据。

示例：CRC-8​

假设我们使用CRC-8标准，生成多项式为 x^8 + x^2 + x + 1，对应的二进制表示为 100000111。

输入数据​

11010101

附加零位​

由于生成多项式的长度为9位（8次方），我们需要在原始数据后附加8个零位：

1101010100000000

多项式除法​

将附加零位后的数据与生成多项式进行模2除法运算，得到余数：

1101010100000000
÷ 100000111
= 余数 00001101

生成CRC码​

将余数附加到原始数据的末尾：

1101010100001101

实际应用场景​

CRC广泛应用于各种通信协议中，以下是一些常见的应用场景：

  1. 以太网：以太网帧使用CRC-32来检测数据传输中的错误。
  2. Wi-Fi：Wi-Fi协议使用CRC-32来校验数据帧的完整性。
  3. 蓝牙：蓝牙协议使用CRC-16来校验数据包。

代码示例​

以下是一个使用Python实现CRC-8的简单示例：

python
def crc8(data):
    generator = 0x107  # CRC-8生成多项式 x^8 + x^2 + x + 1
    crc = 0
    for byte in data:
        crc ^= byte
        for _ in range(8):
            if crc & 0x80:
                crc = (crc << 1) ^ generator
            else:
                crc <<= 1
            crc &= 0xff  # 确保CRC保持在8位
    return crc

# 示例数据
data = [0x55]  # 二进制 11010101
crc_value = crc8(data)
print(f"CRC-8: {crc_value:02x}")

输出​

CRC-8: 0d

总结​

循环冗余校验（CRC）是一种简单而有效的数据校验方法，广泛应用于数据链路层协议中。通过生成一个固定长度的校验码，CRC能够检测数据传输或存储过程中的错误，确保数据的完整性。

附加资源与练习​

提示

建议初学者通过编写代码实现CRC算法，以加深对其工作原理的理解。