通信工程 / 系统课时

按生成多项式计算 CRC 余数

按生成多项式计算 CRC 余数

给定待发送比特和生成多项式,先通过模二长除法求出 CRC 校验位,再将余数附在信息位后;接收端用同一除数检查整帧。本课用信息位 1101 和生成多项式 1011 完成手算、Python 复现和差错检验。

学习目标

  • 根据生成多项式的次数确定 CRC 宽度和补零数量。
  • 逐位对齐并执行异或长除法,求出准确的余数。
  • 复现发送端编码与接收端检验,识别 CRC 漏检边界。

先确定多项式与校验位宽度

二进制串从左到右依次表示多项式由高到低的系数。1011 对应 G(x)=x3+x+1G(x)=x^3+x+1,次数为 3,因此 CRC 余数固定保留 3 位;信息位 1101 对应 M(x)=x3+x2+1M(x)=x^3+x^2+1。

模二除法只使用异或(XOR),例如 1 XOR 1 = 0、1 XOR 0 = 1,不进位也不借位。发送端先在 1101 后补三个零,得到 1101000,相当于计算 M(x)x3M(x)x^3,再对它取余。直接对原始 1101 取余,得不到本次发送需要的校验位。

逐位对齐执行异或

从最左侧开始扫描:当前待处理位是 1,就把除数 1011 的首位对齐到此处并逐位异或;若是 0,就跳到下一位。为了手算时不丢失位次,始终保持 7 位长度。

对齐起点(从 0 起) 异或前 对齐后的除数 异或后
0 1101000 1011000 0110000
1 0110000 0101100 0011100
2 0011100 0010110 0001010
3 0001010 0001011 0000001

生成多项式逐位对齐进行四轮异或的长除法示意图

最后得到的 7 位工作状态为 0000001,只取最右侧 3 位,CRC 即 001。将余数拼回原信息位:1101 + 001 = 1101001。发送的是 7 位码字,而不是长除法产生的整段工作状态。

用 Python 生成与校验 CRC

下面的 Python 3 程序直接处理最高位在左的二进制串,采用初始余数为零、非反射、无最终异或的教学约定。发送端对补零数据取余,接收端则直接对收到的完整码字取余。

python
def remainder(bits: str, generator: str) -> str:
    if (not bits or len(generator) < 2 or generator[0] != "1"
        or generator[-1] != "1" or len(bits) < len(generator)
        or (set(bits + generator) - {"0", "1"})):
        raise ValueError("请输入足够长的比特串,生成多项式首尾须为1")
    work = [int(bit) for bit in bits]
    poly = [int(bit) for bit in generator]
    # 当前最高待处理位是1时,才进行一次对齐异或。
    for i in range(len(work) - len(poly) + 1):
        if work[i]:
            for j, bit in enumerate(poly):
                work[i + j] ^= bit
    # 生成多项式的次数决定余数宽度。
    return "".join(map(str, work[-(len(poly) - 1):]))

message = "1101"
generator = "1011"
padded = message + "0" * (len(generator) - 1)
crc = remainder(padded, generator)
frame = message + crc
one_flip = frame[:4] + "1" + frame[5:]
# 用恰好能被生成多项式整除的差错模式测试漏检。
missed = "".join(str(int(a) ^ int(b)) for a, b in zip(frame, "0001011"))
print("补零数据:", padded)
print("CRC 余数:", crc)
print("发送帧:", frame)
print("无差错检验:", remainder(frame, generator))
print("一位翻转:", one_flip, "余数:", remainder(one_flip, generator))
print("特定多位翻转:", missed, "余数:", remainder(missed, generator))

预期输出:

text
补零数据: 1101000
CRC 余数: 001
发送帧: 1101001
无差错检验: 000
一位翻转: 1101101 余数: 100
特定多位翻转: 1100010 余数: 000

接收端直接用 1011 除完整的 1101001,不再补零。正常帧余数为 000,左起第 5 位被翻转后余数为 100,说明发现了差错;但 CRC 本身无法根据这个余数直接恢复原始信息。

余数为零为何仍可能出错

余数非零表示检测到差错,余数为零只表示没有检测到差错。例如差错模式 0001011 恰好是生成多项式左侧补零后的形式,能被 1011 整除;因此 1101001 翻转这些位置变为 1100010,接收端余数依然是 000,发生漏检。

本例是用于解释模二长除法的 3 位教学 CRC,并非标准 CRC-8、CRC-16 或 CRC-32。实际通信双方还必须一致约定生成多项式、位序、初始值、是否反射、最终异或及校验位的传输方式;某些标准 CRC 的整帧校验残值并不为零,不能机械套用本例的判定值。

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

目录与阅读设置

阅读设置

17

记录一个想法

按生成多项式计算 CRC 余数

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

登录哪都通