通信工程 / 系统课时

循环码与 CRC

循环码与 CRC

CRC 把一段比特序列看成二元域上的多项式,通过生成多项式做模二除法,把余数附在原数据之后。掌握这套过程后,你可以手工完成一个小型 CRC 编码与校验,并判断接收端余数代表什么。

学习目标

  • 理解循环码、生成多项式与 CRC 余数之间的关系
  • 掌握模二除法中“异或代替减法”的计算规则
  • 能完成发送端补零、求余、拼接以及接收端复验

CRC 的核心模型

在二元域 GF(2) 中,比特串可以写成多项式。例如 1101 对应 x3+x2+1x^3+x^2+1。系数只有 0 和 1,加法与减法都等价于异或,因此整个 CRC 计算不需要进位或借位。

设原始信息多项式为 M(x)M(x),生成多项式为 G(x)G(x),其次数为 rr。发送端先把信息左移 rr 位,再用 G(x)G(x) 求余:

R(x)=[xrM(x)] mod G(x)R(x) = [x^r M(x)] \bmod G(x)

随后构造发送码字:

T(x)=xrM(x)+R(x)T(x) = x^r M(x) + R(x)

这里的加号仍是 GF(2) 上的加法,也就是按位异或。因为 T(x)T(x) 能被 G(x)G(x) 整除,接收端只要再次求余,就能得到一个用于差错检测的判据。

CRC 从生成余数到接收端复验的流程

循环码之所以称为“循环”,是因为合法码字循环移位后仍落在同一个码集合中。CRC 利用了循环码的多项式结构,但工程上最常用的目标是检错,而不是直接定位或纠正错误。

模二除法的计算规则

模二除法与普通长除法的对齐方式相似,但每次“相减”都改成异或。当前最高位为 1 时,用生成多项式与当前窗口异或;最高位为 0 时,不需要真的做减法,只继续向后移动窗口。

以信息位 1101、生成比特 1011 为例。1011 对应三次多项式,所以需要补 3 个 0,得到被除数 1101000。按模二除法逐步处理后,余数为 001,因此 3 个 CRC 校验位就是 001。

这个例子中生成多项式的次数是 3,所以余数最多只有 3 位;若计算得到更短的结果,左侧要补 0,直到长度固定为 3 位。固定长度是接收端准确切分信息位和校验位的前提。

发送与接收的完整校验

发送端把原始信息 1101 与余数 001 拼接,得到码字 1101001。接收端收到后,不需要先拆出原始信息,只需把整个码字直接除以同一个 1011。若传输无误,本例余数为 000。

如果传输中把第三位翻转,使接收序列变成 1100001,再次除以 1011 后得到余数 011。非零余数说明接收到的序列不是该生成多项式下的合法码字,因此可以确认发生了可检测差错。

生成多项式决定什么

生成多项式首先决定冗余位数:次数为 rr,每个码字就增加 rr 个 CRC 位。它还决定哪些错误模式必然可检测、哪些可能漏检,因此实际协议通常直接规定 CRC-8、CRC-16、CRC-32 等具体多项式,而不是只规定“使用多少位 CRC”。

选择生成多项式时不能简单认为次数越高就一定越好,还要结合帧长、期望检测的突发错误长度和实现成本。CRC 也不是加密哈希:它是线性检错码,目标是高效发现传输或存储中的随机差错,不提供身份认证或抗恶意篡改能力。

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

目录与阅读设置

阅读设置

17

记录一个想法

循环码与 CRC

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

登录哪都通