海明码
海明（Hamming）码是通过冗余数据位来检测和纠正差错的编码方式。
海明距离（码距）：一个码字要变成另一个码字时必须改变的最小位数，即两个码字之间不同的比特数。
例：
1011 01 00
1011 01 11两个码字后两位不同（00 vs 11），海明距离（码距）为 2。
例题：
海明码原理与海明不等式
海明码原理
在数据中间加入几个校验码，码距均匀拉大，当某一位出错，会引起几个校验位的值发生变化。
海明不等式
校验码个数为 k，可以表示 2ᵏ 个信息：
- 1 个信息用来表示没有错误
- 其余 2ᵏ - 1 个表示数据中存在错误
如果满足：
2ᵏ - 1 ≥ m + k
（m 为信息位，m+k 为编码后的数总长度）
则在理论上 k 个校验码就可以判断是哪一位出现了问题。
编码规则
- 第 （i=0, 1, 2, 3...）位是校验位，其余位存放数据。
- 假设传送信息
1001011，把数据放在 3、5、6、7、9、10、11 位置，1、2、4、8 留作校验位。
数据位初始分配
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 数据 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
校验位与数据位的关系
每个数据位的位号可以分解为校验位号之和：
| 数据位 | 分解 | 参与校验位 |
|---|---|---|
| 3 | 2 + 1 | 1, 2 |
| 5 | 4 + 1 | 1, 4 |
| 6 | 4 + 2 | 2, 4 |
| 7 | 4 + 2 + 1 | 1, 2, 4 |
| 9 | 8 + 1 | 1, 8 |
| 10 | 8 + 2 | 2, 8 |
| 11 | 8 + 2 + 1 | 1, 2, 8 |
各数据位对应校验位（二进制表示）
| 数据位 | 校验位 | |||
|---|---|---|---|---|
| 8 | 4 | 2 | 1 | |
| 3 | 0 | 0 | 1 | 1 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 9 | 1 | 0 | 0 | 1 |
| 10 | 1 | 0 | 1 | 0 |
| 11 | 1 | 0 | 1 | 1 |
3、5、7、9、11 号位参加第 1 位校验。按偶校验计算，1 号位应为 1。
计算校验位后的完整码字
类似地：
- 3、6、7、10、11 号位参加 2 位校验
- 5、6、7 号位参加 4 位校验
- 9、10、11 号位参加 8 位校验
全部按偶校验计算，最终得到：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 码字 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
红色为校验位，绿色为数据位。
错误检测示例
如果 6 号位在传输中出错（0 → 1），码字变为：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 接收 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
接收端按同样规则计算奇偶性：
- 1 号位奇偶性正确 ✅（ACK1 = 3,5,7,9,11）
- 8 号位奇偶性正确 ✅（ACK8 = 9,10,11）
- 2 号位奇偶性不对 ❌（ACK2 = 3,6,7,10,11）
- 4 号位奇偶性不对 ❌（ACK4 = 5,6,7）
奇偶性不对的校验位：2 + 4 = 6，立即可确认错在 6 号位。
例题
第一题
第二题
第三题
第四题
第五题