信道编码：冗余怎样换可靠性

WARNING

🧪 Beta公测版本提示：教程主体已完成，正在优化细节，欢迎大家提Issue反馈问题或建议。

香农 说：码率 $R<C$ 时存在编码使误差随码长趋于 $0$。本章用最短的非平凡纠错码 Hamming(7,4) 看这句话的「怎么做」：4 个数据比特加 3 个校验，能纠正 1 个翻转。BSC 交叉概率 $p$ 小时，译码后的误比特率明显低于不编码的 4 比特。高斯噪声见 AWGN。

正文先讲码率与球；需要把校验子或最小距离展开时，点开「逐步推导」。

---

一、码率与球

7 位码字、16 个合法中心（$2^4$），最小距离 $3$，半径 $1$ 的汉明球互不相交，所以能纠正单个错误。码率

$$R=\frac{4}{7}\approx 0.571.$$

$p$ 很小的 BSC 容量 $C=1-h_2(p)$ 大于 $4/7$ 时，香农保证「存在更好的长码」；Hamming 只是手算得动的短码，不是容量逼近码。

保姆级：冗余不是浪费，是保险。 不编码时每个数据比特直接过 BSC，错了就是错了。Hamming 多送 3 个校验，换来「7 位里坏 1 位仍能找回 4 个数据」。保险费是码率从 $1$ 降到 $4/7$；只有当信道还撑得住（$C>R$）这笔买卖才划算。$p$ 大到球叠在一起，保险会赔穿——曲线后段 Hamming 可能比不编码更差。

图解说明：左是 4 比特加 3 校验；中是半径 1 的球；右是未编码 vs Hamming 的误比特示意。校验子（syndrome）指出哪一位翻转。

逐步推导：最小距离 $3$ 为什么能纠 $1$ 错（点击展开）

汉明距离 $d(u,v)$ 是两位串有几位不同。一个码的最小距离 $d_{min}$ 是任意两个合法码字之间的最小 $d$。

纠 $t$ 个错的充分条件是 $d_{min}\ge 2t+1$。几何：以每个码字为球心、半径 $t$ 的球若互不相交，收到的向量落在某个球里就能唯一判给那个码字。不相交要求球心间距至少 $2t+1$。$t=1$ 则 $d_{min}\ge 3$。

Hamming(7,4) 的 $2^4=16$ 个码字恰好填满 $\{0,1{\}}^7$ 里半径 $1$ 的球：每个球体积 $1+7=8$，十六个球 $16\times 8=128=2^7$，完美密铺（完美码）。所以：无错时落在球心；恰 1 错时落在球内某点，能纠正；2 错会落到另一个码字的球里，会「纠错纠错」——本章只用纠 1，不讨论检 2。

与容量比：BSC $p=0.05$ 时 $C=1-h_2(0.05)\approx 0.71>4/7$，短码有资格工作，但远不是定理里的渐近最优。定理要 $n\to \mathrm{\infty }$。

---

二、位置 1,2,4 放校验

1-index 位置：校验在 $1,2,4$，数据在 $3,5,6,7$。每个校验覆盖二进制下对应比特为 1 的位置。收到后重算三个校验，合成 $1$–$7$ 的错误位置；为 $0$ 则无错。

逐步推导：校验子怎样指出翻转位（与 encode74 / decode74 一致）（点击展开）

把 7 个位置写成 1-index。校验位 $p_1,p_2,p_4$ 放在位置 $1,2,4$（0-index 的 $0,1,3$）。数据 $d_1,d_2,d_3,d_4$ 放在位置 $3,5,6,7$（0-index $2,4,5,6$）。偶校验约定：

$$\begin{array}{rlrl}{p}_1& =d_1\oplus d_2\oplus d_4& & \text{覆盖二进制第 0 位为 1 的位置：1,3,5,7},\\ p_2& =d_1\oplus d_3\oplus d_4& & \text{位置 2,3,6,7},\\ p_4& =d_2\oplus d_3\oplus d_4& & \text{位置 4,5,6,7}.\end{array}$$

这正是 demo 里

c[0] = c[2] ^ c[4] ^ c[6]
c[1] = c[2] ^ c[5] ^ c[6]
c[3] = c[4] ^ c[5] ^ c[6]

译码：用收到的 7 位重算三个校验，得到校验子 $(s_0,s_1,s_2)$，整数

$$\mathrm{pos}=s_0+2s_1+4s_2.$$

$\mathrm{pos}=0$：无错。否则翻转 1-index 的第 $\mathrm{pos}$ 位（代码里 r[pos-1] ^= 1）。最后取出数据位 r[[2,4,5,6]]。

为什么 pos 等于翻转位置：每个数据/校验位的编号，其二进制 1 恰好标出它参与了哪些校验。一位翻转会让「它参与的那些校验」全部跳变，校验子的二进制就是该编号。两位同时翻，校验子变成两个编号的异或，不再指向真实位置——所以只能保证纠 1。

---

三、代码在做什么

demo.py 在一串 $p$ 上各抽 4000 个随机 4 比特组：一条不编码直接过 BSC，一条 Hamming 编码再译。纵轴是数据比特的误比特率（BER）。$p\to 0$ 时 Hamming 接近 $0$ 更快；$p$ 太大（球重叠）纠错帮倒忙。

扫描点：$p\in \{0.01,0.03,0.05,0.08,0.12,0.18\}$，种子 42。终端会打印每个 $p$ 的两套 BER；正文常看 $p=0.05$ 那一行。

终端打印 $p=0.05$ 时两套 BER。不要把短码的 BER 曲线当成信道编码定理的证明——定理要码长 $\to \mathrm{\infty }$。

---

四、小结

概念	一句话
码率 $R$	数据位 / 发送位
Hamming(7,4)	纠 1 错，检 2 错（本章只用纠 1）
校验子	三个校验合成错误位置
$R<C$	可靠通信的前提，短码只是例子
下游	高斯信道

下一章 高斯信道。

📥 Code

File	View	Download
demo.py	Open	Download
exercise.py	Open	Download

参考

1. MacKay, ITILA（Hamming 码）
2. Cover & Thomas, 信道编码定理