6 题型 - 检错与纠错机制
Chinese-language Computer Science 408 note: 6 题型 - 检错与纠错机制. Original source available where applicable.
On this page
This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.
描述：网络各层采用的检错方法不同：IPv4 首部、TCP，以及启用校验和的 UDP 使用 16 位反码算术求和；以太网、PPP、802.11 的 FCS 使用 CRC。普通奇偶校验只能发现部分错误，海明码可纠正单比特错误；实际计算机网络更常用“检错后重传”而不是大量前向纠错冗余。
6.1 四类方法对比
| 方法 | 基本原理 | 检错/纠错能力 | 网络中的典型用途 |
|---|---|---|---|
| 反码算术求和 | 16 位字做回卷进位加法，结果按位取反 | 只能检错，能力弱于 CRC | IPv4 首部、UDP、TCP 校验和 |
| CRC | 以生成多项式做模 2 除法，余数作为 FCS | 检错能力强，通常不直接纠错 | PPP、以太网、802.11 帧尾 FCS |
| 奇偶校验 | 增加 1 位使 1 的个数为奇数或偶数 | 可检出奇数个比特翻转，不能纠错 | 串行通信、部分存储/外设场景 |
| 海明校验 | 在特定位置加入多个校验位并计算综合征 | 可定位并纠正单比特错误 | 存储系统等；普通网络较少用其做前向纠错 |
检错码本身不一定纠错。网络发现帧或报文错误后，通常选择丢弃并依靠可靠传输协议重传；若该层提供不可靠服务，则可能只丢弃而不恢复。
6.2 反码算术求和
6.2.1 发送端步骤
- 将校验范围按 16 bit 分组；若最后不足 16 bit，按协议规定补零。
- 进行普通二进制加法。
- 若最高位产生进位，把进位回卷到最低位继续相加，直到没有新的进位。
- 对最终 16 位和按位取反，得到校验和。
可写成：
$$Checksum=\operatorname{NOT}\left(\operatorname{ones_complement_sum}(word_1,word_2,\ldots)\right)$$
接收端把收到的所有 16 位字连同校验和一起做反码求和。无差错时结果应为全 1，即 0xFFFF；若不是全 1，则检测到错误。
6.2.2 2024 年 UDP 校验和真题
已知中间结果为：
1011 1001 1011 0110 = 0xB9B6
还需加上最后一个 16 位数：
0110 0101 1100 0101 = 0x65C5
先做普通加法：
0xB9B6
+ 0x65C5
--------
0x11F7B
产生最高位进位 1，将其回卷到低 16 位：
0x1F7B + 0x0001 = 0x1F7C
最后按位取反：
~0x1F7C = 0xE083
1110 0000 1000 0011
答案：C，1110 0000 1000 0011。
6.3 IPv4、UDP 与 TCP 的校验范围
| 对象 | 校验范围 | 校验位置与长度 | 路由器是否校验 | IPv6 中的情况 |
|---|---|---|---|---|
| IPv4 数据报 | 仅 IPv4 首部 | 首部校验和，16 bit | 是 | IPv6 基本首部取消首部校验和 |
| UDP 用户数据报 | IP 伪首部 + UDP 首部 + 数据 | UDP 首部校验和，16 bit | 否，由端系统校验 | IPv4 中可选；IPv6 中通常必须使用 |
| TCP 报文段 | IP 伪首部 + TCP 首部 + 数据 | TCP 首部校验和，16 bit | 否，由端系统校验 | IPv4/IPv6 均使用 |
6.3.1 IPv4 首部校验
- 发送端计算时先把首部校验和字段置 0，只对 IPv4 首部做反码求和。
- 路由器收到 IPv4 数据报后检查首部；校验失败则静默丢弃，不发送 ICMP 差错报告。
- 若校验成功，路由器转发前会修改 TTL 等首部字段，因此必须重新计算首部校验和。
- IPv6 为提高路由器转发效率，取消了基本首部校验和。
**原 PDF 第 2 页的 20 B 首部计算示例。**计算时先将校验和字段置 0，再按网络字节序把首部拆成十个 16 位字：
| 顺序 | 16 位字 | 对应字段 |
|---|---|---|
| 1 | 0x4500 |
版本 4、首部长 5 个 32 位字、服务字段 0 |
| 2 | 0x003C |
总长度 60 B |
| 3 | 0x050E |
标识 |
| 4 | 0x0000 |
标志与片偏移 |
| 5 | 0x4001 |
TTL 为 64、协议号为 1（ICMP） |
| 6 | 0x0000 |
待计算的首部校验和 |
| 7–8 | 0xC0A8、0x0502 |
源地址 192.168.5.2 |
| 9–10 | 0xC0A8、0x0504 |
目的地址 192.168.5.4 |
普通求和得到 0x215A1；将高位进位 0x2 回卷到低 16 位，得到 0x15A1+0x2=0x15A3；按位取反后，首部校验和为 0xEA5C（1110 1010 0101 1100）。把 0xEA5C 填入第 6 个字后重新做反码求和，结果为 0xFFFF，与原图中的校验值一致。这里计算的是 IPv4 首部，不包含后面的数据载荷。
6.3.2 TCP/UDP 的伪首部
IPv4 下，TCP/UDP 校验计算前要临时加入 12 B 伪首部：
| 字段 | 长度 | 含义 |
|---|---|---|
| 源 IPv4 地址 | 4 B | 来自 IPv4 首部 |
| 目的 IPv4 地址 | 4 B | 来自 IPv4 首部 |
| 保留字段 | 1 B | 全 0 |
| 协议号 | 1 B | TCP 为 6，UDP 为 17 |
| TCP/UDP 长度 | 2 B | 首部与数据的总长度 |
IPv6 也有用于上层校验和的伪首部，但格式不同：含 16 B 源地址、16 B 目的地址、4 B 上层报文长度、3 B 全 0 和 1 B Next Header，共 40 B。伪首部只参与校验和计算，不会作为 TCP/UDP 报文的一部分在网络中单独传输。它把源/目的地址和上层协议标识纳入保护，可防止报文被错误交付到不匹配的端点或协议。
普通 IP 转发路径不校验 TCP/UDP 校验和；端系统检测到 UDP/TCP 校验错误时丢弃该报文。UDP 不自动重传，TCP 则可能因收不到有效确认而由发送方超时重传。具备防火墙、NAT、深度检测等功能的网络设备可能检查或改写传输层字段，但这不是普通路由转发本身的校验职责。
IPv4 UDP 允许把校验和字段置 0 表示未启用校验；TCP 校验和不可省略，IPv6 UDP 校验和通常也不可省略。若参与校验的数据为奇数字节，计算时补一个全 0 字节凑成 16 bit，但该填充字节不随 UDP 数据发送。
6.4 CRC 与 FCS
CRC 把待发送比特串看作二进制多项式，用生成多项式 $G(x)$ 做模 2 除法：
- 若 $G(x)$ 的最高次数为 $r$，在原数据后补 $r$ 个 0。
- 用生成多项式做异或除法，不借位、不进位。
- 得到的 $r$ 位余数就是 CRC 校验序列，填入 FCS。
- 接收端以同一生成多项式除收到的完整序列；余数为 0 表示未检出错误，非 0 表示有错。
PPP 帧、以太网 MAC 帧和 802.11 数据帧尾部的 FCS 都使用 CRC 生成。以太网常用 CRC-32，FCS 长度为 4 B；其检验覆盖目的地址、源地址、类型/长度、数据与填充等 MAC 帧字段，不包含前导码和 FCS 自身。
6.4.1 模拟题
题目问 PPP 帧尾 FCS 字段采用哪种计算方法。
答案：B，循环冗余校验 CRC。
CRC 的作用是发现错误，不会自动定位并修正错误位；发现错误后的丢弃或重传由协议决定。
6.5 奇偶校验与海明校验
6.5.1 码距决定检错与纠错能力
INFO · 教材补充
两个等长码字之间不同的比特位数称为海明距离；一个编码集合任意两合法码字之间距离的最小值称为最小码距 $d_{min}$。合法码字在比特空间中分得越开，接收端越能分辨传输错误。
| 目标 | 对最小码距的要求 |
|---|---|
| 保证检出至多 $t$ 位错误 | $d_{min}\ge t+1$ |
| 保证纠正至多 $t$ 位错误 | $d_{min}\ge 2t+1$ |
普通单奇偶校验的 $d_{min}=2$，所以能保证检出 1 位错误但不能纠错。普通海明码的 $d_{min}=3$，可选择“保证纠正 1 位错误”或“保证检出 2 位错误”；若要在纠正单错的同时可靠标出双错，需再加总奇偶校验位形成扩展海明码（SECDED，$d_{min}=4$）。
6.5.2 奇偶校验
- 偶校验使码字中 1 的总数为偶数，奇校验使其为奇数。
- 单个比特翻转一定会改变奇偶性，因此能检出。
- 偶数个比特同时翻转可能保持原奇偶性，因而漏检。
- 普通奇偶校验不能指出哪个比特出错，也不能纠错。
6.5.3 海明校验
若数据位数为 $m$，校验位数为 $r$，为使每个单比特错误位置及“无错”状态都有唯一综合征，需满足：
$$2^r\ge m+r+1$$
校验位通常放在编号为 $1,2,4,8,\ldots$ 的位置。接收端重新计算各校验组，综合征的二进制值指出出错位，可纠正单比特错误。若需要可靠地区分双比特错误，通常还要使用扩展海明码的总奇偶校验位。
6.6 易错点
- UDP/TCP 的校验范围包含伪首部、首部和数据；IPv4 首部校验和只覆盖 IPv4 首部。
- IPv4 伪首部不是实际发送的附加首部；TCP 协议号为 6，UDP 为 17。
- IPv4 UDP 校验和可选且以全 0 表示未启用；TCP 和通常的 IPv6 UDP 校验和不可省略。
- 反码求和的最高位进位必须回卷到最低位，最后还要按位取反。
- CRC 的模 2 除法使用异或，不产生算术进位或借位。
- FCS 是承载 CRC 余数的字段；“CRC”是计算方法，二者不能简单当成同一个概念。
- IPv4 路由器校验并重算首部校验和，但不检查 TCP/UDP 校验和。
- 基本奇偶校验不能纠错；海明码的典型能力是纠正单比特错误。
相关知识
- 科目导航：计算机网络导航
- 阅读顺序：上一篇：调制与复用技术 · 下一篇：数据链路层思维导图
- 关联专题：数据链路层检错与可靠传输
6.7 本节复盘
- IPv4、UDP、TCP 使用 16 位反码算术求和；以太网、PPP、802.11 的 FCS 使用 CRC。
- 2024 年真题将
0xB9B6与0x65C5相加、回卷进位再取反，得到0xE083。 - IPv4 只校验首部且 IPv6 已取消该字段；TCP/UDP 把相应 IP 版本的伪首部纳入校验，但伪首部不实际传输。
- CRC 检错能力强但不直接纠错；网络通常依靠丢弃与重传恢复差错。
- 奇偶校验能检出奇数个比特错误，海明码通过综合征定位并纠正单比特错误。