数制与编码：海明码、CRC循环冗余校验

可视化演示

展示海明码校验位编码原理、单比特错误定位纠错流程与CRC多项式除法校验过程，三步演示从编码到纠错到校验的完整链路，可切换模式查看不同阶段。

海明码的校验位设计

想象你管理着一座堆放古董瓷器的仓库。货架编号从1排到N，每件瓷器都价值连城，最怕搬运时磕碰——一个瓷瓶碎了，你得知道具体是哪个位置的碎了才能补货。你雇了几位巡检员，但工钱不菲，人数必须精打细算。一位巡检员只能报告“这排有没有碎”；两位巡检员各按一套分区巡逻，组合起来能区分4种情况；三位就是8种。问题来了：要在 N 个货架中定位任何一处损坏，最少要雇几人？

计算机里的比特，就是那些货架上的瓷器。海明码用 r 个校验位（巡检员）看护 n 个数位（货架），校验位的数量必须满足一个不等式：所有校验位能组合出的状态数，至少要能区分“一切正常”以及 n+r 个位置中任何一处出错——合计一共需要标识 n+r+1 种情况。

$$\displaystyle 2^r \geq n + r + 1$$

1. 数据位数 n：原始有效信息占用的比特数。例如要传输4位数据，n=4。

$$n$$

2. 校验位数 r：额外添加的冗余比特数，它们不携带新信息，只负责“盯梢”。

$$r$$

3. 状态总数 2^r：r 个校验位能组合出 2^r 种“口供组合”，如同 r 个巡检员各报“正常/异常”，能形成 2^r 种汇报模式。

$$2^r$$

4. 待区分情况 n+r+1：码字总长 n+r 个位置，加上“无错误”这一种情况，就是需要区分的全部情形。

$$n + r + 1$$

第二件要事：校验位放在哪里？答案是 2 的幂次位置：第 1、2、4、8……位。这么做有一个精妙的好处——每个校验位只属于一个校验组，数值互不影响，接收端可以独立地算出每一位，不会出现“牵一发而动全身”的混乱。

$$\displaystyle p_i = 2^{\,i-1}, \quad i = 1, 2, \dots, r$$

1. 第 i 个校验位 p_i：从 1 开始计数，第1个校验位、第2个校验位、第3个校验位……依次排列。

$$p_i$$

2. 位置公式 2^(i-1)：第 i 个校验位放在码字的第 2^(i-1) 位，即位置 1、2、4、8、16……这些位置上。

$$2^{\,i-1}$$

3. 二进制独特性：这些位置编号的二进制表示只有单独一个 1（如 1=001、2=010、4=100），所以每个校验位只出现在自己的校验组里，不会干扰其他校验位的计算。

$$p_i = 2^{\,i-1}$$

于是，雇几个巡检员、他们站在哪些位置，都有了数学依据：正如不等式决定了人工预算，位置公式则确保每个人的“领地”清爽独立。海明码的骨架就此搭好——接下来就是让巡检员们开始干活了。

海明码的纠错流程

巡检员们上岗了。他们手里各有一张巡逻清单，清单不是随便划的，而是按照货架编号的二进制编码来分：位置编号的二进制表示中，第 i 位为 1 的位，就归第 i 个巡检员管。于是位置3（二进制 011）同时出现在1号和2号巡检员的清单上；位置5（二进制 101）则出现在1号和3号的清单上。这样，当某个位置出错时，哪些巡检员会拉响警报，就构成了一串独一无二的二进制编码。

接收端做同样的分组——把每个组内的所有位做异或运算。若某组异或结果为1，说明这一组内有奇数个位出错了。注意，这个“分组”把校验位自己也算进去了：校验位的值在发送时就被设计成让每组异或结果为0，所以接收端的异或结果天然就是“是否出错”的指示器。

$$\displaystyle S = P_1 \cdot 1 + P_2 \cdot 2 + P_3 \cdot 4$$

1. 各组校验结果 P_i：每组做异或的结果，正常为0，异常为1。它是一份“证词”。

$$P_i = \bigoplus_{j \in \text{组}i} b_j$$

2. 加权求和：第 i 组的结果乘以 2^(i-1)，再把三项加起来。因为位置编号的二进制中各位的权重正是 1、2、4。

$$S = P_1 + 2P_2 + 4P_3$$

3. 校正子 S：S=0 表示无错；S 非零时，它的数值直接告诉我们出错位置。比如 S=6，说明第6位翻转了。

$$S = \text{出错位编号}$$

看，这就是交叉汇报的力量——每个人只报告自己辖区内的异常，但把所有人的证词拼在一起，谜底就浮出水面了。海明码不需要“挨个检查”，只需要 3 个异或门和一次小加法，就能在纳秒内锁定肇事比特，然后把它取反，数据恢复如初。

CRC的生成多项式与除法

处理完仓库的磕碰，你还要对付另一个隐患：快递。瓷器打包寄往外地，要经过十几个中转站，你怀疑有人偷偷开箱。你想了一个点子：不用昂贵的巡检员，而是在每件包裹上贴一枚“防伪封条”——封条上的数字由货物内容用一套神秘算法算出来，收货方重新一算，对不上就说明箱子被动过。这枚封条，就是 CRC 校验码。

CRC 的数学舞台是二进制多项式。把信息比特 1011 写成多项式 x³+x+1，把商定的“神秘算法”叫做生成多项式 G(x)。发件方把信息左移 r 位（预留出校验码的位置），用 G(x) 做模2除法，把余数 R(x) 贴在信息尾部。这里的“模2除法”很特别：每一步减法都用异或代替，既不借位也不产生进位。

$$\displaystyle R(x) = \left( M(x) \cdot x^r \right) \bmod G(x)$$

1. 信息多项式 M(x)：原始数据的每一位对应 x 的幂的系数。比如 1011 = x³ + x + 1。

$$M(x) = m_{k-1}x^{k-1} + \cdots + m_1 x + m_0$$

2. 左移 r 位：乘以 x^r 相当于在信息末尾补 r 个0，腾出 r 位的空间来放校验码。

$$M(x) \cdot x^r$$

3. 模2除法取余：用 G(x) 做模2除法，余数的最高次数必然小于 r，因此余数只占 r 位。

$$\bmod G(x)$$

4. 余数即校验码 R(x)：把 r 位的余数拼接到左移后的信息后面，组成完整的发送码字。

$$T(x) = M(x) \cdot x^r + R(x)$$

收件方对完整码字再做一次同样的除法，如果余数为0，说明封条完好；余数非0则说明数据被篡改过。

$$\displaystyle T(x) \bmod G(x) = 0$$

1. 接收码字 T(x)：收件方拿到的完整比特串，包含原始信息和 CRC 校验码。

$$T(x)$$

2. 再做一次除法：用同一个 G(x) 去除 T(x)，因为 T(x) 是左移后的信息加上余数，理论上应当整除。

$$T(x) \div G(x)$$

3. 余数判据：整除（余数为0）说明数据完好；产生余数说明传输中发生了错误。

$$T(x) \bmod G(x) = 0 \iff \text{无误}$$

与海明码的“精准定位”不同，CRC 的封条只回答一个问题：这箱子被动过没有？它不告诉你动了哪一件，但足以让收货方决定“拒收重发”——在可靠传输协议中，重发远比现场修复更划算。

CRC的硬件实现

制作防伪封条的工艺，比你想象中简单——只需要一枚模板（生成多项式）和一颗图章（异或门）。不需要乘法器、不需要除法器，几块小电路就能在数据流过的一瞬间完成盖章。这一切的核心，是一种叫做“线性反馈移位寄存器”（LFSR）的电路。

模2除法的每一次“减法”都退化为异或：1 与 1 相遇立即抵消为 0，没有借位、没有进位。这意味着电路里只需要一种逻辑门——异或门。而 LFSR 的结构更是直接由生成多项式的形状决定：寄存器的每一位串联起来，在系数为 1 的位置引出反馈线，接入异或门，再把结果送回寄存器首位。

$$\displaystyle G(x) = x^r + g_{r-1}x^{r-1} + \cdots + g_1 x + 1$$

1. 最高次项 x^r：生成多项式的次数 r 决定了寄存器的位数（也是校验码的位数）。

$$x^r$$

2. 中间系数 g_i：值为 1 的系数位对应一条反馈抽头，值为 0 则直接跳过。

$$g_{r-1}, \dots, g_1$$

3. 常数项 1：最低位恒为 1，保证余数不会出现“除尽”时的退化情况。

$$+1$$

这台“盖戳机”的速度快得惊人。以千兆以太网为例，数据以每秒 1G 比特流过，CRC-32 电路在线计算，延迟以纳秒计。你还在核对快递单，封条已经悄悄盖好并校验完毕了——这正是硬件实现的魅力：用最少的资源，在数据流动的途中完成数学计算。

典型应用场景

现在你回到仓库总经理的位置。不同的货物，你会选择不同的安保方案：传世字画派武装押运（海明码），普通标件贴防伪封条（CRC）。数字世界里，这个决策同样讲究“量体裁衣”——没有最好的编码，只有最合适的编码。

内存 ECC：服务器内存是数据暂存的黄金库，宇宙射线和热噪声会导致比特随机翻转。ECC 内存采用海明码的升级版（SEC-DED），每 64 位数据附加约 8 位校验。单比特错误在读取时自动纠正，用户毫无感知；双比特错误则触发告警，防止数据继续被污染。这是海明码“纠错”能力的经典战场。

网络传输：以太网帧在嘈杂的铜缆和光纤中穿行，噪声容易引发成串的突发错误。网卡在发送帧时计算 CRC-32，把 4 字节的帧校验序列（FCS）附在帧尾；接收时重新计算，不匹配就丢弃该帧。因为网络协议允许重传，所以“检测到就重发”远比“试图修复”更高效——这是 CRC“检错”优势的典型体现。

存储校验：磁盘和 SSD 也可能发生“静默数据损坏”——硬件报错但数据已错，普通校验发现不了。ZFS、Btrfs 等现代文件系统在每个数据块旁存储校验和，读取时即时验证，发现损坏就从冗余副本恢复。RAID 控制器同样大量使用 CRC 来做一致性校验。

金子用保险箱，瓷器用海绵，标签用封条，各有各的妙处。选海明码还是 CRC 的黄金法则：需要现场修复且错误以单比特为主，选海明码；错误可能是一串突发且允许重传，选 CRC。

海明码与CRC的对比

巡检员与封条，此刻站在你面前等你做最终抉择。它们都能发现数据异常，但能力边界截然不同：巡检员能告诉你“哪件瓷器碎了”并当场补上，封条只能告诉你“包裹被动过”，要挽回损失还得靠重寄。

从信息论的角度看，海明码把冗余花在了“位置编号”上——校正子的大小直接映射到出错位置，因此它天然适合纠正单比特错误。而 CRC 把冗余花在了“特征提取”上——用多项式除法把数据揉成一个高强度的指纹，只要有任何一处异动，指纹就会对不上。两者的根本差异可以浓缩为一句话：海明码是“哪里坏了修哪里”，CRC 是“坏了就重新来”。

$$\displaystyle \text{冗余率} = \frac{r}{n + r}$$

1. 冗余位 r：校验位（或 CRC 校验码）的位数，是为安全付出的额外带宽。

$$r$$

2. 总码长 n+r：信息位加上校验位的完整长度，是实际占用信道的比特数。

$$n + r$$

3. 冗余率：冗余位占总码长的比例。海明码随数据增长（如 8 位数据要 4 位校验，冗余率约 33%），CRC 则固定开销（如 CRC-32 对任意长数据都只加 32 位）。

$$\frac{r}{n+r}$$

回到整体：两道防线，各司其职。海明码靠着分层巡检的巧思，用最少的人手在单比特错误面前做到“现场修复”；CRC 靠着数学指纹的韧性，在无处不在的突发噪声面前做到“明察秋毫”。理解了它们，你就理解了计算机系统如何在资源与安全之间做出优雅的权衡。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""海明码(7,4)与CRC-3完整演示"""  def hamming_encode(d):    """海明码(7,4)编码：输入4位数据，输出7位码字"""    b = [0] * 7    # 数据位映射到位置3,5,6,7    b[2], b[4], b[5], b[6] = d[0], d[1], d[2], d[3]    # 校验位放在位置1,2,4    b[0] = b[2] ^ b[4] ^ b[6]    b[1] = b[2] ^ b[5] ^ b[6]    b[3] = b[4] ^ b[5] ^ b[6]    return b  def hamming_syndrome(b):    """海明码校正子：返回0表示无错，否则返回出错位置"""    s = b[0] ^ b[2] ^ b[4] ^ b[6]    s |= (b[1] ^ b[2] ^ b[5] ^ b[6]) << 1    s |= (b[3] ^ b[4] ^ b[5] ^ b[6]) << 2    return s  def hamming_correct(b):    """海明码纠错：单比特翻转自动纠正"""    s = hamming_syndrome(b)    if s:        b[s - 1] ^= 1    return b, s  def crc_encode(data, poly):    """CRC编码：返回完整码字与校验码"""    r = len(poly) - 1    work = data[:] + [0] * r       # 信息左移r位    for i in range(len(data)):        if work[i]:            for j in range(1, len(poly)):                work[i + j] ^= poly[j]   # 模2除法    remain = work[len(data):]    return data + remain, remain  def crc_check(code, poly):    """CRC校验：余数全为0表示无误"""    r = len(poly) - 1    work = code[:]    for i in range(len(code) - r):        if work[i]:            for j in range(1, len(poly)):                work[i + j] ^= poly[j]    return not any(work[len(code) - r:])  if __name__ == "__main__":    # 海明码演示    data = [1, 0, 1, 1]    code = hamming_encode(data)    print("海明码(7,4)编码:", data, "->", code)    code[5] ^= 1    fixed, s = hamming_correct(code)    print("翻转第6位后 校正子 =", s, " 纠正后:", fixed)     # CRC演示    g = [1, 1, 0, 1]   # G(x)=x^3+x^2+1    tx, crc = crc_encode([1, 1, 0, 1, 0], g)    print("CRC编码: 信息11010 校验码", crc, "-> 完整码字", tx)    tx[4] ^= 1    print("接收端校验 余数为0?", crc_check(tx, g))

1. b[2], b[4], b[5], b[6] = d[0], d[1], d[2], d[3]把4位原始数据安插到海明码的位置3、5、6、7上，位置1、2、4留给校验位。
2. b[0] = b[2] ^ b[4] ^ b[6]计算第1组校验位：它需要让位置1、3、5、7的异或结果为0，这正是奇偶校验的本质。
3. s |= (b[1] ^ b[2] ^ b[5] ^ b[6]) << 1把第2组异常结果左移1位（乘以2），与第1组结果按位相加，为组成校正子做准备。
4. b[s - 1] ^= 1校正子 s 就是出错位置，直接对该位置取反，一步完成纠错——简洁得令人惊叹。
5. work = data[:] + [0] * rCRC 编码第一步：信息左移 r 位，在后面补 r 个0，给校验码腾出空间。
6. work[i + j] ^= poly[j]模2除法的核心：当前位为1时，从第 i 位开始与多项式系数逐位异或，实现无借位除法。
7. return data + remain, remain把余数（校验码）拼接到信息尾部，形成最终发送的码字。
8. return not any(work[len(code) - r:])接收端检查最后 r 位是否全为0，全0则说明除法整除，数据没有破损。

常见误区

面试题