kp-007 组帧与差错检测：奇偶校验、CRC 与海明码

注：本文基于模型知识整理，建议结合权威教材与 RFC 原文核对细节。

一句话定义

数据链路层把不可靠的比特流切成帧（定界），并给每帧附加冗余比特让接收方能查出错误（奇偶校验、互联网校验和、CRC），冗余足够多时甚至能直接纠正错误（海明码）。

为什么重要

物理层交上来的只是一串可能出错的比特：不定界，接收方既无法把数据交付上层，也不知道该对哪段做校验；不检错，损坏的数据会被当正确数据处理，比丢帧危害更大。CRC 是以太网、Wi-Fi、HDLC 等几乎所有链路协议共用的检错地基；海明码是理解纠错的最小模型，内存 ECC 与无线编码都在用它背后的思想。手工模 2 除法也是课程考试与面试的高频题。

前置知识

建议先读 kp-004《封装》，了解帧在分层模型中的位置；会二进制异或（XOR）运算即可跟上本文。

核心概念

为什么必须切帧：定界让接收方知道一帧从哪开始、到哪结束，才能确定校验范围并把数据交给网络层。
四种定界方法及其缺陷：
字符计数法：帧首部放一个「本帧总长」计数字段。致命缺陷：计数字段一旦传错，后续所有帧的边界全部错位且无法自动恢复。
字节填充（byte stuffing）：用特殊标志字节定界，数据中出现标志字节就在前面插转义字节，接收端删除转义还原。缺陷是数据越像标志，填充开销越大。
比特填充（bit stuffing）：以 01111110 作帧界，发送端每遇五个连续 1 就插入一个 0，接收端收到五个连续 1 之后的 0 一律删除。缺陷是数据每含五个连 1 就要多传 1 比特，填充比特出错还会牵连边界判断。
物理编码违例法：利用线路编码中的非法信号组合作定界，如曼彻斯特编码中每个码元中点必有跳变，「中点不跳变」的组合即可专用于帧界；前提是物理层编码必须提供这种冗余状态。
检错（error detection）与纠错（error correction）：检错加重传（ARQ, Automatic Repeat reQuest）在误码率低的有线链路上最省冗余；前向纠错 FEC（Forward Error Correction）靠足够冗余直接改错，适合重传代价高的无线、实时与深空场景。两者是「冗余度与重传开销」的权衡。
一维奇偶校验（parity check）：附加 1 位使整帧中 1 的个数为奇（奇校验）或偶（偶校验）。任何奇数个比特错都会改变奇偶性从而被发现；但两位错、四位错等偶数个错误互相「抵消」，完全漏检。
互联网校验和（Internet checksum）：把数据按 16 位分组做反码求和再取反。实现极简，但检错能力弱——例如两个字交换位置后总和不变即漏检。它服务于 IP/TCP/UDP，链路层的强检错仍靠 CRC。
循环冗余校验 CRC（Cyclic Redundancy Check）：把比特串看作多项式，收发双方约定生成多项式 G(x)，发送端在数据后附上模 2 除法的余数（帧检验序列 FCS, Frame Check Sequence），接收端将整帧除以 G(x)，余数为零即认为无错。
海明码（Hamming code）：把 k 个校验位安插在 2 的幂次位置，按二进制位分组做奇偶，能纠正 1 位错、发现 2 位错。

公式与模型

CRC 的数学骨架：

比特串按每位对应多项式一项、系数取 0 或 1，如 1011 按降幂对应 x^3 + x + 1。
模 2 运算：加减都是按位异或 XOR，无进位借位；除法即「首位为 1 则商 1 并异或除数，为 0 则商 0 跳过」。
生成多项式 G(x) 共 r+1 位时，FCS 取 r 位：FCS = (数据 × x^r) mod G(x)。
接收端判据：接收帧除以 G(x) 余数为 0 则通过。出错等价于真实帧叠加了错误多项式 E(x)；只要 G(x) 的因式结构保证它不能整除常见类型的 E(x)（单比特错、奇数位错、给定长度内的突发错），相应错误就一定被检出。能防住哪些错误由 G(x) 的选取决定，标准如 CRC-32 已被长期实践检验。
海明码的规模条件：k 个校验位、m 个数据位满足 2^k ≥ m + k + 1；校验位放在第 1、2、4、8（即 2^i）位，第 i 个校验位负责所有「二进制编号含 2^i 位」的位置。

图示

CRC 流水线

发送端：数据 M ── 左移 r 位 ──→ 模 2 除以 G ──→ 余数即 FCS
        发送帧 = M ‖ FCS
接收端：收到的整帧 ── 模 2 除以 G ──→ 余数 = 0 ?
        是 → 判定无错（严格说是未检出错）；否 → 丢弃该帧

原理与机制

组帧与检错是一套组合拳：先定界，让「一段完整的比特」有了边界；再在这段比特上计算冗余。一维奇偶只用 1 位冗余，代价最小、检错也最弱；互联网校验和用逐字求和，实现快但代数结构弱；CRC 用多项式除法把整帧「揉」进一个余数里，任何位置的比特翻转几乎都会改变余数，因而以极低冗余（如以太网 FCS 仅 4 字节）换来极强检错能力——这就是它统治链路层的根本原因。检错只告诉你「错了」，纠错还要能指出「哪里错了」：海明码让每个校验位分管一组位置，出错时把各组的奇偶检查结果按权拼成一个二进制数（校验子 syndrome），这个数恰好就是出错位置的编号——冗余经过精心设计后，「检错信息」自然升级成了「定位信息」。

实例分析

CRC 完整算例：数据 M = 101001，生成多项式 G = 1101（r = 3），求 FCS 并验证。
发送端把 M 左移 3 位得 101001000，模 2 除以 1101：

步骤 1  1010 ⊕ 1101 = 0111，落下下一位 0 → 1110
步骤 2  1110 ⊕ 1101 = 0011，落下 1 → 0111
步骤 3  0111 首位为 0，商 0 不异或，落下 0 → 1110
步骤 4  1110 ⊕ 1101 = 0011，落下 0 → 0110
步骤 5  0110 首位为 0，商 0 不异或，落下 0 → 1100
步骤 6  1100 ⊕ 1101 = 0001 → 余数 001

FCS = 001，发送帧 = 101001 001。接收端将 101001001 除以 1101，余数为 000，校验通过；若传输中第 5 位翻转，收到 101011001，除以 1101 余数为 111（非零），错误被检出。

海明码最小例子：数据 4 位 1011（记 d1 d2 d3 d4 = 1 0 1 1），需 k = 3 个校验位（2^3 = 8 ≥ 4 + 3 + 1）。7 位布局为 p1 p2 d1 p3 d2 d3 d4，即位置 1 到 7 依次放：p1、p2、1、p3、0、1、1。

p1 管位置 1、3、5、7（编号末位为 1）：p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0
p2 管位置 2、3、6、7（编号第二位为 1）：p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1
p3 管位置 4、5、6、7（编号第三位为 1）：p3 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0

码字为 0110011。设第 5 位在传输中翻转，接收序列为 0110111；重新检查三个分组得 s1 = 1、s2 = 0、s3 = 1，拼成校验子 s3 s2 s1 = 101，即十进制 5——出错位置就是第 5 位，翻转该位即完成纠错。

检错之后怎么办由自动重传请求 ARQ 回答：停等、回退 N、选择重传等协议用重传消化被检出的坏帧，TCP 确认与重传机制也是同一思想在传输层的重演。

常见误区

认为余数为零就「绝对无错」：只能保证「未检出错误」，某些多位错组合仍可能恰好整除 G 而漏检，只是概率被设计得极低。
把模 2 除法当普通除法：模 2 加减是无进位借位的异或，不能套用普通算术。
混淆校验和与 CRC 的分工：互联网校验和管 IP/TCP/UDP 层，链路层强检错靠 CRC，两者叠加而非互替。
认为一维奇偶聊胜于无就够用：它对偶数个错完全免疫，链路质量差的场景不可依赖。
把海明码的校验子当成奇偶检查结果本身：校验子是各组检查结果按权拼成的二进制数，直接给出出错位置编号。
忽略定界与检错的耦合：定界决定「对哪段算校验」，边界一旦错位，一切校验都失去意义。

自测题

字符计数法的致命缺陷是什么？

答案要点： 计数字段一旦传错，接收方会把错误值当作帧长，后续所有帧的边界全部错位且无法自动恢复。

比特填充如何防止数据被误认为帧界标志？

答案要点： 发送端在数据中每出现五个连续 1 后插入一个 0，保证不会出现六个连 1；接收端把五个连 1 之后的 0 一律删除还原数据。

求数据 101001、生成多项式 1101 对应的 FCS。

答案要点： 数据左移 3 位得 101001000，模 2 除以 1101 余数为 001，FCS = 001，发送帧为 101001001。

一维奇偶校验为什么对偶数个比特错失效？

答案要点： 偶数个比特翻转时 1 的个数的奇偶性不变，校验结果仍与发送端一致，错误被掩盖。

海明码如何用校验子定位出错位？

答案要点： 每个校验位分管一组按二进制位划分的位置；接收端对各组做奇偶检查得 s1、s2、s3，拼成二进制数即为出错位置编号，翻转该位即纠正。