Appearance
差错控制：检错与纠错编码
概念
差错控制（error control）就是给数据加上"多余的信息"（冗余），使接收方能发现——甚至自动纠正——传输过程中被噪声改动的比特。
一句话说清它是什么：差错控制 = 给数据"配一把尺子"——发送前按尺子量一遍、把量出来的数附在数据后面；接收方再量一遍，对不上就说明传输过程出了问题。
两条完全不同的路线：
| 路线 | 名字 | 怎么做 | 代价 |
|---|---|---|---|
| 检错 + 重传 | ARQ（Automatic Repeat reQuest，自动重传请求） | 只发现错误，发现后请对方重发那一帧 | 冗余少；但需要反向信道，且重传有时延 |
| 纠错 | FEC（Forward Error Correction，前向纠错） | 自己算出哪一位错了，就地改回来 | 冗余多；但不需要反向信道，适合单向链路（如深空通信） |
⚠️ 一句话分清"检错"与"纠错"：检错是"发现家里进贼了"，纠错是"还能把小偷按住、把东西摆回原位"。 检错只要"知道错了"，纠错还要"知道错在第几位"——所以纠错码必须携带更多冗余，最小码距要求也更高。
与上一章（net/20-framing.md）的衔接：上一章说"帧尾放 FCS 校验码"；本章就是"这个校验码怎么算、能查出什么错、能不能纠正"。 上一章的 4 B FCS 就是本章 CRC-32 的落点。
原理
一、差错从哪来：随机错与突发错
| 类型 | 成因 | 特征 | 对编码的要求 |
|---|---|---|---|
| 随机错（热噪声） | 电路的热噪声、器件噪声 | 独立发生，多为单比特错；错位之间不相关 | 奇偶校验就能对付 |
| 突发错（冲击噪声） | 外部电磁干扰、脉冲干扰、接触抖动 | 成串出现，一段连续比特被破坏 | 需要能对付"连续一段"的编码（如 CRC） |
⚠️ "外界的冲击噪声是差错的主因"是常考的一句结论：热噪声引起的随机错虽然一直存在，但幅度小、可被电路容限吸收；真正让数据出错的大多是持续时间短、幅度大的冲击噪声——所以链路层编码要重点防"突发错"，这也是 CRC 比奇偶校验更实用的原因。
三种"错的粒度"：
- 比特错：1 位或几位被翻转（本章讨论的对象）
- 帧错：帧丢失、帧重复、帧失序（由
net/22-window.md的序号 + 确认机制处理） - 码元错：物理层一个码元判错（由
net/10-physical.md的编码与信噪比决定）
二、码距：检错与纠错能力的度量
海明距离（Hamming distance）
码集的最小码距
text
例: 合法码字集 {000, 011, 101, 110}
d(000,011) = 2, d(000,101) = 2, d(000,110) = 2
d(011,101) = 2, d(011,110) = 2, d(101,110) = 2
-> d_min = 2 (只能检出 1 位错, 不能纠错)三条判据（必背）：
把三条件摊开成表（
| 只检错最多 | 只纠错最多 | 同时检纠 | |
|---|---|---|---|
| 1 | 0（无检错能力） | 0 | — |
| 2 | 1 | 0 | — |
| 3 | 2 | 1 | (1, 1) |
| 4 | 3 | 1 | (2, 1) |
| 5 | 4 | 2 | (2, 2) |
| 6 | 5 | 2 | (3, 2) |
| 7 | 6 | 3 | (3, 3) |
⚠️ 两条易错点：
- "只检错最多
"= ；"只纠错最多 "= ——纠错要"占双份"距离（既要把错码拉回本码字，又不能拉进邻居的势力范围），所以纠错能力大约是检错能力的一半。 - 同时检纠时
： 时能"检 1 位 + 纠 1 位"，但不能"检 2 位 + 纠 1 位"（ ）。这个" "是考试常挖的坑——它代表"无错"这一种状态也要占一格距离。
三、奇偶校验：一维与二维
（1）一维奇偶校验（simple parity）
做法：在数据后加 1 位校验位，使整个码字中 1 的个数为偶数（偶校验）或奇数（奇校验）。
text
数据: 1 0 1 1 0 0 1 (1 的个数 = 4, 偶数)
偶校验: 1 0 1 1 0 0 1 0 (校验位 = 0, 1 的个数仍为 4)
奇校验: 1 0 1 1 0 0 1 1 (校验位 = 1, 1 的个数为 5)| 能力 | 说明 |
|---|---|
| 能检出 | 奇数个位错（1 位、3 位、5 位……） |
| 检不出 | 偶数个位错（2 位同时翻转，"1 的个数"的奇偶性没变） |
| 能纠错吗 | 不能——只知道"出错了"，不知道错在哪一位 |
⚠️ "一维奇偶只能检出奇数个错"是它的死穴：两位同时出错时就完全失效（错得越多越可能漏检）。 这就是为什么它只用在"出错概率极低"的场合（如内存的简单校验），而在网络链路上要用 CRC。
（2）二维奇偶校验（row-and-column parity）
做法：把数据排成
锚点（
text
列0 列1 列2 列3 行校验
行0: 1 0 1 1 | 1 (1+0+1+1 = 3, 奇数 -> 校验位置 1)
行1: 0 1 1 0 | 0 (0+1+1+0 = 2, 偶数 -> 校验位置 0)
行2: 1 1 0 1 | 1 (1+1+0+1 = 3, 奇数 -> 校验位置 1)
--------------------------+-------
列校验: 0 0 0 0 (每列 1 的个数都是 2, 偶数 -> 全 0)| 能力 | 说明 |
|---|---|
| 检出 | 所有奇数个位错 + 绝大部分偶数个位错（"绝大部分"指：除非出错位置恰好构成一个矩形四角那种特例） |
| ★ 纠正 | 能纠正 1 位错——行校验指出"错在第几行"、列校验指出"错在第几列"，交叉定位 |
| 冗余率 | 数据 12 位 + 行校验 3 位 + 列校验 4 位 = 19 位 → 冗余率 |
1 位错的定位过程（锚点）：设"行 1、列 2"那一位从 1 翻成 0：
text
① 该位在行 1 -> 行 1 的 1 的个数由 2 变 1, 与存的行校验 0 不符 -> 错在行 1
② 该位在列 2 -> 列 2 的 1 的个数由 2 变 1, 与存的列校验 0 不符 -> 错在列 2
③ 交叉定位: (行 1, 列 2) -> 把这一位取反即纠正⚠️ "二维奇偶能纠 1 位错"这个能力最容易漏：很多人只记住"奇偶校验只能检错不能纠错"，但那只适用于一维。 二维情况下"行 + 列"两个方向的校验合起来提供了定位信息，所以能纠 1 位——这是从"检错码"升级成"纠错码"最便宜的一种做法。
四、循环冗余校验 CRC
CRC（Cyclic Redundancy Check，循环冗余校验）把比特串当成多项式的系数，用"模 2 除法"取余数作为校验码。 它以最少的冗余换来了最强的检错能力，是数据链路层事实上的标准。
三步走（必背）：
text
设数据 M 共 k 位, 生成多项式 G(x) 的次数为 r (即 G 是 r+1 位的比特串)
① 补零: 在 M 后面添 r 个 0 -> 得到 k+r 位
② 模 2 除: 用 G 去除补零后的 M, 取余数 -> 余数是 r 位 (不足补前导 0)
③ 拼接: 发送序列 = M + 余数 -> 共 k+r 位
接收方: 把收到的整体再除一次 G, 余数为 0 说明无错★ 模 2 除法的三条铁律：
| 铁律 | 说明 |
|---|---|
| 只有异或，没有进位/借位 | 每一位独立相减， |
| 商的每一位只看"当前被除数首位" | 首位是 1 就商 1（做一次异或），首位是 0 就商 0（直接移位） |
| 余数位数恒为 |
锚点 1（
text
① 补 3 个 0: 1 0 1 0 0 1 0 0 0
② 模 2 除 (被除数 101001000, 除数 1101):
1 0 1 0 0 1 0 0 0
^ 1 1 0 1 <- 首位是 1, 商 1
------------
0 1 1 1 0 1 0 0 0 <- 异或后往下带一位
1 1 0 1 <- 首位变为 1, 商 1
------------
0 0 1 0 1 0 0 0
1 1 0 1 <- 首位仍为 1(第 4 位), 商 1
------------
0 1 1 1 0 0 0
1 1 0 1 <- 首位变为 1, 商 1
------------
0 0 1 0 0 0
0 0 0 0 <- 首位是 0, 商 0, 只移位
------------
0 1 0 0 0
0 0 0 0 <- 首位是 0, 商 0
------------
1 0 0 0
1 1 0 1 <- 首位是 1, 商 1
------------
0 1 0 1
0 0 0 0 <- 首位是 0, 商 0
------------
1 0 1
★ 余数 (取最低 3 位) = 0 0 1
③ 发送序列 = 1 0 1 0 0 1 0 0 1 (9 位)锚点 2（1110 → 发送序列 11010110111110（14 位）。
CRC 的检错能力（记住这几条就够）：
| 能检出 | 前提 |
|---|---|
| 所有长度 | 一定成立（这是 CRC 最核心的保证） |
| 所有奇数个位错 | |
| 所有 2 位错 | |
| 绝大多数长突发错 | 有 |
⚠️ 以太网用的是 CRC-32：生成多项式是 32 次（
），所以 FCS 占 4 B——它能检出所有 位的突发错，漏检概率约 。 "以太网帧尾那 4 B"就是这么来的（见 net/20-framing.md）。
⚠️ 一个常被问反的点：CRC 只能检错，不能纠错——它给出的是"余数是不是 0"，不给出"错在第几位"。 （理论上某些 CRC 变体能纠错，但教材里 CRC 一律按"检错码"处理。）
五、汉明码：能定位的纠错码
汉明码（Hamming code）通过多摆几位校验位，让"出错位置"本身变成可读出的信息——校验子（syndrome）的值直接就是出错位的编号。
校验位要几位？ 设信息位
不等式右边那个 "
校验位的摆放规则（必背）：第
分组规则（必背）：第
以
text
位置: 1 2 3 4 5 6 7
位置二进制: 001 010 011 100 101 110 111
放什么: p1 p2 d1 p3 d2 d3 d4
谁管谁 (位置编号的哪一位是 1):
p1 (第 1 位为 1): 1, 3, 5, 7 -> p1, d1, d2, d4
p2 (第 2 位为 1): 2, 3, 6, 7 -> p2, d1, d3, d4
p3 (第 3 位为 1): 4, 5, 6, 7 -> p3, d2, d3, d4编码（偶校验，数据
text
p1 = d1 ^ d2 ^ d4 = 1 ^ 0 ^ 1 = 0
p2 = d1 ^ d3 ^ d4 = 1 ^ 1 ^ 1 = 1
p3 = d2 ^ d3 ^ d4 = 0 ^ 1 ^ 1 = 0
码字 (位置 1~7) = p1 p2 d1 p3 d2 d3 d4 = 0 1 1 0 0 1 1纠错（接收方算校正子）：
text
S1 = p1 ^ d1 ^ d2 ^ d4 (位置 1,3,5,7)
S2 = p2 ^ d1 ^ d3 ^ d4 (位置 2,3,6,7)
S3 = p3 ^ d2 ^ d3 ^ d4 (位置 4,5,6,7)
校正子 S = S3 S2 S1 (二进制) —— 它就是"出错位的编号"
S = 0 -> 无错
S = 3 -> 第 3 位错, 取反即纠正锚点（码字 0110011，逐个翻转验证）：
| 翻转位 | 校正子 | 十进制 | 结论 |
|---|---|---|---|
| 第 1 位 | 001 | 1 | 错在第 1 位 |
| 第 2 位 | 010 | 2 | 错在第 2 位 |
| 第 3 位 | 011 | 3 | 错在第 3 位 |
| 第 4 位 | 100 | 4 | 错在第 4 位 |
| 第 5 位 | 101 | 5 | 错在第 5 位 |
| 第 6 位 | 110 | 6 | 错在第 6 位 |
| 第 7 位 | 111 | 7 | 错在第 7 位 |
⚠️ 校正子"直接就是位置编号"是汉明码最漂亮的地方：它把"定位"这件事从"搜索"变成了"读表"——7 种单比特错各对应一个非零校正子，一一对应、互不混淆，这就是"能纠 1 位错"的全部依据。
汉明码的冗余率（锚点表）：
| 信息位 | 校验位 | 总长 | 冗余率 | ||
|---|---|---|---|---|---|
| 1 | 2 | 4 | 4 | 3 | 66.67% |
| 4 | 3 | 8 | 8 | 7 | 42.86% |
| 8 | 4 | 16 | 13 | 12 | 33.33% |
| 11 | 4 | 16 | 16 | 15 | 26.67% |
| 16 | 5 | 32 | 22 | 21 | 23.81% |
| 26 | 5 | 32 | 32 | 31 | 16.13% |
| 32 | 6 | 64 | 39 | 38 | 15.79% |
| 57 | 6 | 64 | 64 | 63 | 9.52% |
| 64 | 7 | 128 | 72 | 71 | 9.86% |
| 120 | 7 | 128 | 128 | 127 | 5.51% |
| 1000 | 10 | 1024 | 1011 | 1010 | 0.99% |
⚠️ 表里加粗的 5 行（
）是"恰好取等"的那几个点：此时 正好等于 ，校验位一位都不能少，但也一位都不用多——这几个数是"汉明码最省"的经典参数（ 对应 码，是通信里常用的一个）。
⚠️ 汉明码的"能力上限"必须记牢：
汉明码的最小码距是 3，所以它"能纠 1 位错、能检 2 位错"，但两者不能同时做到——若要"纠正 1 位 + 同时检出 2 位"（SEC-DED），最小码距要到 4，需要在校验位之外再加 1 位总校验位（计算机内存常用的就是这种扩展汉明码）。
六、三种编码的横向对照
| 编码 | 冗余开销 | 能检出 | 能纠正 | 典型用途 |
|---|---|---|---|---|
| 一维奇偶校验 | 1 位 / 字节 | 奇数个位错 | 不能 | 内存简单校验、串口 |
| 二维奇偶校验 | 约 | 奇数个 + 大部分偶数个位错 | 1 位错 | 磁带、早期存储 |
| CRC | 所有 | 不能（教材口径） | 以太网 FCS、PPP、磁盘 | |
| 汉明码 | 2 位错 | 1 位错 | ECC 内存、卫星通信 |
⚠️ "为什么链路层选 CRC 而不选汉明码"：链路层的做法是"检错 + 重传"（ARQ），重传一次的成本远低于全程多带 42.86% 的冗余——只有"没法重传"的信道（深空、单向广播）才值得用汉明码这类纠错码。 这一条把"检错 vs 纠错"的选择逻辑讲通了。
示例
例 1：C 实现——CRC 模 2 除法与汉明码 (7,4)
参数：CRC 两组锚点
/ 与 / ；汉明码按"数据 1011、偶校验、校验位在位置 1/2/4"编码，再逐个单比特翻转求校正子。
#include <stdio.h>
/* ① 模 2 除法求 CRC 余数: msg 长 k 位, gen 长 glen 位(= r+1), 余数 r 位 */
void crc(const int *msg, int k, const int *gen, int glen, int *rem) {
int d[64], i, j, r = glen - 1;
for (i = 0; i < k; i++) d[i] = msg[i];
for (i = 0; i < r; i++) d[k + i] = 0; /* 数据后补 r 个 0 */
for (i = 0; i < k; i++)
if (d[i] == 1) /* 首位是 1 才做模 2 减 */
for (j = 0; j < glen; j++) d[i + j] ^= gen[j];
for (i = 0; i < r; i++) rem[i] = d[k + i]; /* 余数取最低 r 位 */
}
void pr(const int *a, int n) { int i; for (i = 0; i < n; i++) printf("%d", a[i]); }
int main(void) {
int g1[4] = {1, 1, 0, 1}, m1[6] = {1, 0, 1, 0, 0, 1};
int g2[5] = {1, 0, 0, 1, 1}, m2[10] = {1, 1, 0, 1, 0, 1, 1, 0, 1, 1};
int rem[8], i;
printf("① CRC 模 2 除法\n");
crc(m1, 6, g1, 4, rem);
printf(" M = "); pr(m1, 6); printf(", G = "); pr(g1, 4);
printf(" (r = 3) -> 余数 = "); pr(rem, 3); printf("\n");
printf(" 发送序列 = M + 余数 = "); pr(m1, 6); pr(rem, 3); printf("\n");
crc(m2, 10, g2, 5, rem);
printf(" M = "); pr(m2, 10); printf(", G = "); pr(g2, 5);
printf(" (r = 4) -> 余数 = "); pr(rem, 4); printf("\n");
printf(" 发送序列 = M + 余数 = "); pr(m2, 10); pr(rem, 4); printf("\n");
printf("\n② 汉明码 (7,4) 偶校验, 校验位在位置 1/2/4\n");
{
int d[4] = {1, 0, 1, 1}, c[7], e[7];
int j, s;
c[0] = d[0] ^ d[1] ^ d[3]; /* p1: 覆盖位置 1,3,5,7 */
c[1] = d[0] ^ d[2] ^ d[3]; /* p2: 覆盖位置 2,3,6,7 */
c[2] = d[0];
c[3] = d[1] ^ d[2] ^ d[3]; /* p3: 覆盖位置 4,5,6,7 */
c[4] = d[1]; c[5] = d[2]; c[6] = d[3];
printf(" 数据 "); pr(d, 4); printf(" -> 码字 "); pr(c, 7);
printf(" (位置 1~7), 校验位 p1p2p3 = %d%d%d\n", c[0], c[1], c[3]);
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++) e[j] = c[j];
e[i] ^= 1; /* 第 i+1 位翻转 */
s = ((e[3] ^ e[4] ^ e[5] ^ e[6]) << 2)
| ((e[1] ^ e[2] ^ e[5] ^ e[6]) << 1)
| (e[0] ^ e[2] ^ e[4] ^ e[6]);
printf(" 第 %d 位翻转 -> 校正子 %d (%03d) 定位正确 = %d\n",
i + 1, s, s, s == i + 1);
}
}
printf("\n③ 汉明码冗余率: 2^r >= k + r + 1\n");
{
int ks[8] = {1, 4, 8, 16, 32, 64, 120, 1000}, t;
for (t = 0; t < 8; t++) {
int k = ks[t], r = 2;
while ((1 << r) < k + r + 1) r++;
printf(" k = %4d -> r = %2d, 总长 %4d, 冗余率 %6.2f%%\n",
k, r, k + r, r * 100.0 / (k + r));
}
}
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
① CRC 模 2 除法
M = 101001, G = 1101 (r = 3) -> 余数 = 001
发送序列 = M + 余数 = 101001001
M = 1101011011, G = 10011 (r = 4) -> 余数 = 1110
发送序列 = M + 余数 = 11010110111110
② 汉明码 (7,4) 偶校验, 校验位在位置 1/2/4
数据 1011 -> 码字 0110011 (位置 1~7), 校验位 p1p2p3 = 010
第 1 位翻转 -> 校正子 1 (001) 定位正确 = 1
第 2 位翻转 -> 校正子 2 (002) 定位正确 = 1
第 3 位翻转 -> 校正子 3 (003) 定位正确 = 1
第 4 位翻转 -> 校正子 4 (004) 定位正确 = 1
第 5 位翻转 -> 校正子 5 (005) 定位正确 = 1
第 6 位翻转 -> 校正子 6 (006) 定位正确 = 1
第 7 位翻转 -> 校正子 7 (007) 定位正确 = 1
③ 汉明码冗余率: 2^r >= k + r + 1
k = 1 -> r = 2, 总长 3, 冗余率 66.67%
k = 4 -> r = 3, 总长 7, 冗余率 42.86%
k = 8 -> r = 4, 总长 12, 冗余率 33.33%
k = 16 -> r = 5, 总长 21, 冗余率 23.81%
k = 32 -> r = 6, 总长 38, 冗余率 15.79%
k = 64 -> r = 7, 总长 71, 冗余率 9.86%
k = 120 -> r = 7, 总长 127, 冗余率 5.51%
k = 1000 -> r = 10, 总长 1010, 冗余率 0.99%⚠️ 三点说明：
- 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现实跑核对，输出 25 行逐字一致。
d[i + j] ^= gen[j]就是"模 2 减法"：C 里没有"模 2 减"这个运算符，它恰好等于按位异或——写成d[i+j] -= gen[j]是错的（那是有借位的普通减法）。(1 << r)而不是pow(2, r)：求"最小的pow返回double，在
例 2：Python——码距、二维奇偶、CRC 与汉明码全表
def pad(s, w):
"""按"显示宽度"补空格: 中文算 2 列, 否则终端里对不齐"""
return s + ' ' * max(0, w - sum(2 if ord(c) > 0x2000 else 1 for c in s))
print('=== ① 最小码距与检错/纠错能力 ===')
print(' ' + pad('d_min', 8) + pad('只检错 e', 12) + pad('只纠错 t', 12) + '同时检纠 (e,t)')
for d in range(1, 8):
e, t = d - 1, (d - 1) // 2
both = '—' # t = 0 时"同时检纠"是退化情形, 记 —
if t >= 1:
for te in range(t, 0, -1):
if te * 2 <= d - 1:
both = '(e=%d, t=%d)' % (d - 1 - te, te)
break
print(' ' + pad(str(d), 8) + pad(str(e), 12) + pad(str(t), 12) + both)
print(' ★ e <= d_min-1; t <= (d_min-1)/2; 同时检纠 e+t <= d_min-1')
print()
print('=== ② 二维奇偶校验 (3x4 数据, 偶校验) ===')
data = [[1, 0, 1, 1], [0, 1, 1, 0], [1, 1, 0, 1]]
print(' ' + pad('行', 6) + pad('数据', 22) + '行校验')
for i, r in enumerate(data):
print(' ' + pad('行%d' % i, 6) + pad(' '.join(str(x) for x in r), 22) + str(sum(r) % 2))
colp = [sum(data[i][j] for i in range(3)) % 2 for j in range(4)]
print(' ' + pad('列校验', 6) + ' ' + pad(' '.join(str(x) for x in colp), 22)
+ '总校验 %d' % (sum(colp) % 2))
print(' 冗余: 数据 12 位 + 行校验 3 + 列校验 4 = 19 位 -> 冗余率 %.2f%%'
% (7 * 100.0 / 19))
print(' 纠 1 位错: 行校验指出行号, 列校验指出列号, 交叉定位')
bad = [row[:] for row in data]
bad[1][2] ^= 1 # 把 (行1, 列2) 那一位翻错
rp = [sum(r) % 2 for r in bad]
cp = [sum(bad[i][j] for i in range(3)) % 2 for j in range(4)]
ri = [i for i in range(3) if rp[i] != sum(data[i]) % 2]
ci = [j for j in range(4) if cp[j] != colp[j]]
print(' 实测: 翻转 (行1, 列2) -> 出错行 = %s, 出错列 = %s -> 定位 (行%d, 列%d)'
% (ri, ci, ri[0], ci[0]))
print()
print('=== ③ CRC: 补 r 个 0 -> 模 2 除 -> 取余数 ===')
def crc(msg, gen):
m, g, r = list(msg), list(gen), len(gen) - 1
d = m + [0] * r
for i in range(len(m)):
if d[i] == 1: # 首位是 1 就异或一次
for j in range(len(g)):
d[i + j] ^= g[j]
return d[len(m):]
for msg, gen in [([1, 0, 1, 0, 0, 1], [1, 1, 0, 1]),
([1, 1, 0, 1, 0, 1, 1, 0, 1, 1], [1, 0, 0, 1, 1])]:
rem = crc(msg, gen)
s = ''.join(map(str, msg)) + ''.join(map(str, rem))
print(' M = %s (%d 位), G = %s (%d 位, r = %d)'
% (''.join(map(str, msg)), len(msg), ''.join(map(str, gen)), len(gen), len(gen) - 1))
print(' 余数 FCS = %s; 发送序列 = %s (%d 位)' % (''.join(map(str, rem)), s, len(s)))
back = crc([int(c) for c in s], gen)
print(' 接收方重算余数 = %s -> %s' % (''.join(map(str, back)),
'无错' if any(back) == 0 else '有错'))
print(' ★ 模 2 除法没有进位/借位, 就是异或; 余数位数恒为 r')
print()
print('=== ④ CRC 检错能力 ===')
for r, note in [(3, '检出所有 <= 3 位突发错'), (4, '检出所有 <= 4 位突发错'),
(16, '漏检率 2^-16 = %.2e' % 2 ** -16),
(32, '漏检率 2^-32 = %.2e' % 2 ** -32)]:
print(' ' + pad('r = %d' % r, 12) + note)
print(' ★ 以太网 CRC-32 -> FCS 占 4 B (与 net/20 的帧结构一致)')
print()
print('=== ⑤ 汉明码 (7,4): 数据 1011 -> 码字 0110011 ===')
d = [1, 0, 1, 1]
c = [d[0] ^ d[1] ^ d[3], d[0] ^ d[2] ^ d[3], d[0],
d[1] ^ d[2] ^ d[3], d[1], d[2], d[3]]
print(' 位置: 1 2 3 4 5 6 7 （1/2/4 是校验位 p1/p2/p3）')
print(' 码字: %s' % ' '.join(map(str, c)))
print(' 校验位: p1=%d p2=%d p3=%d' % (c[0], c[1], c[3]))
print(' ' + pad('翻转位', 10) + pad('校正子 S3S2S1', 16) + '十进制 = 出错位置')
for pos in range(7):
e = c[:]
e[pos] ^= 1
s = ((e[3] ^ e[4] ^ e[5] ^ e[6]) << 2) | ((e[1] ^ e[2] ^ e[5] ^ e[6]) << 1) \
| (e[0] ^ e[2] ^ e[4] ^ e[6])
print(' ' + pad('第 %d 位' % (pos + 1), 10) + pad(format(s, '03b'), 16)
+ '%d %s' % (s, 'OK' if s == pos + 1 else 'NG'))
print(' ★ 校正子为 0 表示无错; 非 0 的值就是出错位的编号')
print()
print('=== ⑥ 汉明码冗余率: 2^r >= k + r + 1 ===')
print(' ' + pad('信息位 k', 12) + pad('校验位 r', 12) + pad('2^r', 10)
+ pad('k+r+1', 10) + pad('总长 n', 10) + '冗余率')
for k in [1, 4, 8, 11, 16, 26, 32, 57, 64, 120, 1000]:
r = 2
while (1 << r) < k + r + 1:
r += 1
mark = ' <= 恰好取等' if (1 << r) == k + r + 1 else ''
print(' ' + pad(str(k), 12) + pad(str(r), 12) + pad(str(1 << r), 10)
+ pad(str(k + r + 1), 10) + pad(str(k + r), 10)
+ '%.2f%%%s' % (r * 100.0 / (k + r), mark))
print(' ★ 取等的 k = 4/11/26/57/120 是"最省"的经典参数; k 越大冗余率越低')
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
=== ① 最小码距与检错/纠错能力 ===
d_min 只检错 e 只纠错 t 同时检纠 (e,t)
1 0 0 —
2 1 0 —
3 2 1 (e=1, t=1)
4 3 1 (e=2, t=1)
5 4 2 (e=2, t=2)
6 5 2 (e=3, t=2)
7 6 3 (e=3, t=3)
★ e <= d_min-1; t <= (d_min-1)/2; 同时检纠 e+t <= d_min-1
=== ② 二维奇偶校验 (3x4 数据, 偶校验) ===
行 数据 行校验
行0 1 0 1 1 1
行1 0 1 1 0 0
行2 1 1 0 1 1
列校验 0 0 0 0 总校验 0
冗余: 数据 12 位 + 行校验 3 + 列校验 4 = 19 位 -> 冗余率 36.84%
纠 1 位错: 行校验指出行号, 列校验指出列号, 交叉定位
实测: 翻转 (行1, 列2) -> 出错行 = [1], 出错列 = [2] -> 定位 (行1, 列2)
=== ③ CRC: 补 r 个 0 -> 模 2 除 -> 取余数 ===
M = 101001 (6 位), G = 1101 (4 位, r = 3)
余数 FCS = 001; 发送序列 = 101001001 (9 位)
接收方重算余数 = 000 -> 无错
M = 1101011011 (10 位), G = 10011 (5 位, r = 4)
余数 FCS = 1110; 发送序列 = 11010110111110 (14 位)
接收方重算余数 = 0000 -> 无错
★ 模 2 除法没有进位/借位, 就是异或; 余数位数恒为 r
=== ④ CRC 检错能力 ===
r = 3 检出所有 <= 3 位突发错
r = 4 检出所有 <= 4 位突发错
r = 16 漏检率 2^-16 = 1.53e-05
r = 32 漏检率 2^-32 = 2.33e-10
★ 以太网 CRC-32 -> FCS 占 4 B (与 net/20 的帧结构一致)
=== ⑤ 汉明码 (7,4): 数据 1011 -> 码字 0110011 ===
位置: 1 2 3 4 5 6 7 （1/2/4 是校验位 p1/p2/p3）
码字: 0 1 1 0 0 1 1
校验位: p1=0 p2=1 p3=0
翻转位 校正子 S3S2S1 十进制 = 出错位置
第 1 位 001 1 OK
第 2 位 010 2 OK
第 3 位 011 3 OK
第 4 位 100 4 OK
第 5 位 101 5 OK
第 6 位 110 6 OK
第 7 位 111 7 OK
★ 校正子为 0 表示无错; 非 0 的值就是出错位的编号
=== ⑥ 汉明码冗余率: 2^r >= k + r + 1 ===
信息位 k 校验位 r 2^r k+r+1 总长 n 冗余率
1 2 4 4 3 66.67% <= 恰好取等
4 3 8 8 7 42.86% <= 恰好取等
8 4 16 13 12 33.33%
11 4 16 16 15 26.67% <= 恰好取等
16 5 32 22 21 23.81%
26 5 32 32 31 16.13% <= 恰好取等
32 6 64 39 38 15.79%
57 6 64 64 63 9.52% <= 恰好取等
64 7 128 72 71 9.86%
120 7 128 128 127 5.51% <= 恰好取等
1000 10 1024 1011 1010 0.99%
★ 取等的 k = 4/11/26/57/120 是"最省"的经典参数; k 越大冗余率越低六条结论：
- 检错与纠错是两套成本：同样码距下"只检错"能查
- 一维奇偶的死穴是"偶数个位错"：它只能保证"1 的个数的奇偶性"，两位同时翻转时奇偶性不变、完全漏检——这是它"廉价但不可靠"的根源。
- 二维奇偶是"最便宜的纠错码"：行列两组校验交叉定位，能纠 1 位错，冗余率
- ★ CRC 锚点：
001、发送101001001；1110、发送11010110111110——接收方把整个序列再除一次，余数为 0 才算无错。 - ★ 汉明码锚点：数据
1011→ 码字0110011（校验位010）；7 种单比特翻转给出的校正子是001~111，与出错位编号一一对应——"校正子 = 位置编号"就是它能纠 1 位错的全部依据。 - 汉明码的冗余随
net/20-framing.md的帧效率表）。
考点
考点
1. 必背结论
- 差错控制的两条路线：检错 + 重传（ARQ） 与 前向纠错（FEC）。
- 两种差错：随机错（热噪声，独立单比特）与突发错（冲击噪声，成串出现）；外界冲击噪声是差错的主因。
- ★ 三条码距判据：
- 换算口径：只检错
- 一维奇偶校验：加 1 位；只能检出奇数个位错；不能纠错。
- ★ 二维奇偶校验：能纠 1 位错（行校验定行、列校验定列、交叉定位）；冗余率锚点（
- ★ CRC 三步：补
- ★ 模 2 除法的铁律：只有异或，没有进位/借位；余数位数恒为
- ★ CRC 锚点 1：
001→ 发送101001001。 - ★ CRC 锚点 2：
1110→ 发送11010110111110。 - CRC 检错能力：能检出所有长度
- CRC 只检错、不纠错（教材口径）；以太网用 CRC-32，故 FCS = 4 B。
- ★ 汉明码校验位位数：
- ★ 校验位位置：第
- ★ 汉明码锚点：数据
1011→ 码字0110011；校正子001~111直接就是出错位编号； - 汉明码冗余率锚点：
- 链路层选 CRC 不选汉明码的理由：链路层靠"重传"（ARQ）修错，重传一次比全程多带 40% 冗余便宜。
2. 高频陷阱
- 用普通除法做 CRC：错。模 2 除法"只异或、无进位无借位"——写成有借位的减法必错。
- 补零的位置搞错：错。补的
- 以为"有余数才是对的"：错。接收方把收到的整个序列再除一次
- 把 FCS 位数说成
- 认为"一维奇偶校验能纠错"：错。它只知道"出错了"，不知道错在哪位——能纠错的是二维奇偶或汉明码。
- 认为"一维奇偶能检出所有位错"：错。只能检出奇数个位错；偶数个位错完全漏检。
- 认为"二维奇偶也只能检错"：错。二维奇偶能纠 1 位错（行 + 列交叉定位）。
- 汉明码校验位放在位置 1、2、3：错。必须放在
- 校验位不等式写成
- 认为汉明码能同时"纠 1 位并检 2 位"：错。
- 认为"码距越大越好，所以拼命加冗余"：错。码距换的是抗错能力，代价是有效带宽——实际选码要看"信道误码率 + 能否重传"，不是越贵越好。
- 把"校正子为 0"当成"可能出错"：错。校正子为 0 表示"无错"（或错到了另一个合法码字上，这种漏检另算）。
3. 解题模板（"差错控制计算题"）
① 先认题型:
给"码字集合" -> 求最小码距 d_min, 再用三条判据定能力
给"奇偶校验" -> 一维只能检奇数个错; 二维能纠 1 位
给"生成多项式" -> CRC: 补 r 个 0, 模 2 除, 取余数
给"信息位数 k" -> 汉明码: 求最小 r 使 2^r >= k+r+1
② 码距题: 两两求海明距离(异或后数 1 的个数), 取最小
检错 e = d_min - 1; 纠错 t = floor((d_min-1)/2); 同时 e+t <= d_min-1
③ CRC 题: 三步走 —— 补零 -> 异或相除 -> 取最低 r 位
收到后自检: 整体再除一次 G, 余数 0 表示无错
FCS 位数 = r (不是 r+1); 以太网 r = 32 -> 4 B
④ 汉明码题: 摆位置(1/2/4...放校验位) -> 分组(位置编号的第 i 位为 1)
-> 偶校验求校验位 -> 收方算 S3S2S1 -> S 就是出错位编号
⑤ 冗余率题: 冗余率 = 校验位 / 总长
CRC: r / (k + r); 汉明码: r / (k + r), 其中 r 取最小解4. 与相邻章节的接口
net/20-framing.md（封装成帧）：本章的 CRC 就是上一章"帧尾 4 B FCS"的具体算法——上一章讲"要有个尾部放校验码"，本章讲"这个校验码怎么算、能查出什么"。net/22-window.md（滑动窗口）："检错发现错误之后怎么办"由下一章回答——ARQ（自动重传请求）就是"检出错误 → 重传"那条路线的具体实现；本章的"检错码"与下一章的"重传机制"合起来才是完整的差错控制。net/24-ethernet.md（以太网）：以太网帧尾的 4 B 就是 CRC-32；CRC 算出来的余数贴在帧尾，接收方校验不通过就直接丢帧、不通知发送方（"以太网不重传"这件事由上层 TCP 负责，见net/41-tcp.md）。net/10-physical.md（物理层）："码元判错"是物理层的差错来源；上一章的"信噪比决定误码率"与本章的"编码决定抗错能力"是同一枚硬币的两面。ds/32-hash.md（散列）："用一小段冗余信息代表一大段数据，且能发现改动"与哈希校验是同一个思路——区别在于 CRC 针对"比特翻转"设计（突发错），哈希针对"故意篡改"设计（抗碰撞）。os/31-disk.md（磁盘）：磁盘每个扇区也会存 ECC 校验码——"存储介质也会出错、也要校验"与网络链路是同一类问题。net/30-ip.md（IP 数据报）：IP 首部也有 16 位首部检验和——但 IP 只校验首部、不校验数据，且用的是反码求和（比 CRC 弱），这一对比是常考的点。
小结
- 差错控制的两条路线：检错 + 重传（ARQ） 与 前向纠错（FEC）；链路层走前者，深空/单向链路走后者。
- 随机错（热噪声）与突发错（冲击噪声）；冲击噪声是差错主因，所以编码要重点防突发错。
- ★ 三条码距判据：
- 一维奇偶：只检奇数个位错，不能纠错；二维奇偶能纠 1 位错（锚点冗余率
- ★ CRC 三步：补
- ★ CRC 锚点：
001、发送101001001；1110、发送11010110111110。 - CRC 能力：检出所有
- ★ 汉明码：
1011→ 码字0110011，校正子001~111即出错位编号。 - 冗余率锚点：汉明码
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。