通信工程 / 系统课时

用CRC验证数据帧完整性

用CRC验证数据帧完整性

使用 4 位数据 1101 和生成多项式 1011,完成一次 CRC-3 校验位计算、发送帧构造和接收端验证。你将实际看到模 2 除法怎样产生校验位、单比特错误怎样被发现,以及为什么 CRC 即使校验通过也不能保证绝对没有错误。

学习目标

  • 理解 CRC 生成多项式、模 2 除法和校验余数的关系。
  • 使用 Python 计算 CRC-3,并在接收端验证完整数据帧。
  • 根据错误图案解释 CRC 的检错能力、漏检条件以及不能纠错的原因。

明确 CRC-3 的计算规则

CRC(循环冗余校验)将二进制数据看作多项式的系数序列,使用事先约定的生成多项式进行模 2 除法,并把得到的余数附加在数据后面。

模 2 除法不进行普通整数除法中的借位运算。对应位置相减直接用异或完成,规则是 0⊕0=0、1⊕1=0、0⊕1=1、1⊕0=1。

本实验采用以下固定参数:

项目 实验取值
原始数据 1101
生成多项式二进制表示 1011
对应多项式 G(x)=x3+x+1G(x)=x^3+x+1
CRC 宽度 3 bit
初始余数 000
输入与输出位反射 不使用
最终异或值 000

1011 的最高次数为 3,所以 CRC 余数宽度固定为 3 位。生成多项式最高位和最低位均为 1,满足本实验的基本要求。

手算 CRC 校验位

发送端先在原始数据后补上 3 个 0,得到待除数据 1101000。补零相当于将数据多项式乘以 x3x^3,为最终的 3 位余数预留位置。

将 1101000 除以 1011,从最高位开始处理。如果当前待处理的最高位为 1,就在对应位置对齐生成多项式并执行异或;如果为 0,直接继续处理下一位。

第一轮将 1101000 与左对齐的 1011000 异或,得到 0110000。继续按照相同规则处理剩余高位,最后得到 0000001。取末尾 3 位,CRC 余数就是 001。

CRC-3模2长除法和接收端余数验证

发送端不发送补零后的 1101000,而是用计算出的余数替换补零位置,形成实际发送帧:1101 加 001,即 1101001。

接收端将收到的完整 7 位帧再次除以相同的生成多项式。如果余数为 000,表示 CRC 校验通过;如果余数不为零,则表明当前帧不满足约定的校验关系。

用 Python 实现收发端 CRC 验证

下面使用 Python 3.8 或更新版本实现模 2 长除法。程序不依赖第三方库,可以直接保存为 crc_demo.py,然后运行 python crc_demo.py。

实验依次验证正常帧、单比特翻转帧,以及一种 CRC-3 无法发现的特定突发错误。

python
def crc_remainder(bits: str, generator: str) -> str:
    work = [int(c) for c in bits]
    divisor = [int(c) for c in generator]

    # 从最高位开始,只有当前位为1时才进行异或
    for i in range(len(work) - len(divisor) + 1):
        if work[i] == 1:
            for j, bit in enumerate(divisor):
                work[i + j] ^= bit

    return "".join(map(str, work[-(len(divisor) - 1):]))


def apply_error(frame: str, mask: str) -> str:
    # 错误掩码中1表示翻转对应比特
    assert len(frame) == len(mask)
    return "".join(str(int(a) ^ int(b)) for a, b in zip(frame, mask))


payload = "1101"
generator = "1011"
width = len(generator) - 1

crc = crc_remainder(payload + "0" * width, generator)
sent = payload + crc
print(f"发送帧={sent}, CRC={crc}")

for label, mask in [
    ("无错误", "0000000"),
    ("单比特翻转", "0000001"),
    ("跨度4位的突发错", "0001011"),
]:
    received = apply_error(sent, mask)
    remainder = crc_remainder(received, generator)
    status = "通过" if remainder == "000" else "检出错误"
    print(f"{label}: 收到={received}, 余数={remainder}, {status}")

预期输出:

text
发送帧=1101001, CRC=001
无错误: 收到=1101001, 余数=000, 通过
单比特翻转: 收到=1101000, 余数=001, 检出错误
跨度4位的突发错: 收到=1100010, 余数=000, 通过

正常发送帧 1101001 的校验余数为 000,与手工计算完全一致。末位发生一次翻转后,接收帧变成 1101000,重新除法得到 001,因此能够检出错误。

第三种情况下,错误掩码为 0001011。它表示最后 4 位范围内发生了 3 次比特翻转,属于跨度为 4 位的突发错误。虽然接收帧已经从 1101001 变成 1100010,CRC 余数却仍然为零。

这不是程序失效,而是特定生成多项式在特定错误图案下出现了数学意义上的漏检。

为什么 CRC 也会漏检

CRC 能否发现一个错误,取决于错误图案对应的多项式是否能够被生成多项式整除。

设发送帧多项式为 T(x)T(x),传输中发生的错误多项式为 E(x)E(x)。实际收到的多项式为:

R(x)=T(x)+E(x)R(x)=T(x)+E(x)

这里的加法是在二元域中进行,相当于按位异或。因为发送帧已经构造为能够被 G(x)G(x) 整除,所以接收端的校验余数只取决于错误多项式除以 G(x)G(x) 的余数。

如果错误多项式也能被 G(x)G(x) 整除,那么接收余数仍然为零,错误就会漏检。

本例中的 0001011 恰好是生成多项式 1011 在 7 位帧内右对齐后的形式,所以它对应的错误必然无法通过当前 CRC 检出。

对于本实验选用的生成多项式 1011,可以明确得到以下能力边界:

  • 所有单比特翻转都能检测,因为单比特错误多项式不可能被 1011 整除。
  • 所有长度不超过 3 位的突发错误都能检测,因为非零错误多项式的次数小于生成多项式次数。
  • 部分长度超过 3 位的突发错误也能检测,但不能保证全部检出。
  • 特定的多比特错误图案可能产生零余数,因此通过校验不等于绝对正确。

在实际数据链路中使用 CRC

生产系统一般使用经过协议明确规定的 CRC 变体,例如 CRC-16 或 CRC-32,而不是直接把本实验的 1011 作为通用参数。

实现时至少需要保证发送端与接收端约定一致:

参数 需要约定的内容
width CRC 校验值宽度
poly 生成多项式
init 寄存器初始值
refin 输入比特是否反射
refout 输出比特是否反射
xorout 最终异或值
帧格式 数据覆盖范围及 CRC 字段的发送顺序

这些参数不一致时,即使通信过程中没有错误,也可能出现校验失败。实际接入协议时,应先使用协议提供的标准测试向量确认本地实现,再连接真实发送设备。

接收端得到非零余数后,通常应将数据帧标记为错误并丢弃,由上层协议请求重传,或交给其他纠错机制处理。CRC 本身只提供校验结果,不能推断正确数据,也不能确定必须修改哪些比特。

同时,CRC 主要用于检测偶发传输错误,不具备抵抗恶意篡改的密码学安全性。如果通信系统需要验证消息来源与防止人为修改,还应使用消息认证码或经过认证的加密协议。

通过 1101、1011 这组短数据完成计算后,可以将程序中的载荷替换为更长的二进制序列,再分别尝试不同错误掩码。只要保持生成多项式与收发参数一致,就能继续用同一套模 2 除法检验 CRC 的检错范围。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用CRC验证数据帧完整性

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通