文章目录
- 海明码：从编码到纠错，一篇讲透
- 一、确定校验位数量
- 二、编码过程
- 第 1 步：确定校验位和数据位的位置
- 第 2 步：确定每个校验位负责检查哪些位
- 第 3 步：计算每个校验位的值（偶校验）
- 第 4 步：得到最终编码
- 三、纠错过程
- 第 1 步：重新计算每个校验组的奇偶性
- 第 2 步：拼出错误位置编号
- 第 3 步：纠正错误
- 四、如果没有错误呢？
- 五、总结
海明码：从编码到纠错，一篇讲透
海明码（Hamming Code）是纠错编码中最经典、最基础的方案，由理查德·海明于 1950 年提出。它的核心能力是：自动检测并纠正 1 位错误。
今天我们就用 4 位数据1011作为例子，完整走一遍海明码的编码和纠错过程。
一、确定校验位数量
校验位数量 r 需满足：
2 r ≥ d + r + 1 2^r \geq d + r + 12r≥d+r+1
其中 d 为数据位数。
对于 4 位数据：2 3 = 8 ≥ 4 + 3 + 1 = 8 2^3 = 8 \geq 4 + 3 + 1 = 823=8≥4+3+1=8，所以 r = 3。
总共 7 位编码，即(7, 4) 海明码。
二、编码过程
第 1 步：确定校验位和数据位的位置
校验位固定放在位置编号为 2 的幂次的位上，其余位置放数据位：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 类型 | P₁ | P₂ | D₁ | P₃ | D₂ | D₃ | D₄ |
- P = 校验位（第 1、2、4 位）
- D = 数据位（第 3、5、6、7 位）
将数据1011依次填入数据位：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 类型 | P₁ | P₂ | D₁ | P₃ | D₂ | D₃ | D₄ |
| 值 | ? | ? | 1 | ? | 0 | 1 | 1 |
第 2 步：确定每个校验位负责检查哪些位
规则：位置编号的二进制表示中，第 i 位为 1 的那些位置，归 Pᵢ 检查。
- P₁（第 1 位）：检查位置编号二进制末位为 1 的位 → 第 1、3、5、7 位
- P₂（第 2 位）：检查位置编号二进制倒数第 2 位为 1 的位 → 第 2、3、6、7 位
- P₃（第 4 位）：检查位置编号二进制倒数第 3 位为 1 的位 → 第 4、5、6、7 位
第 3 步：计算每个校验位的值（偶校验）
让每个校验位负责的那些位中，1 的个数为偶数：
P₁：检查第 1、3、5、7 位 → P₁ + D₁ + D₂ + D₄ = P₁ + 1 + 0 + 1 = P₁ + 2
要使总和为偶数 → P₁ =0
P₂：检查第 2、3、6、7 位 → P₂ + D₁ + D₃ + D₄ = P₂ + 1 + 1 + 1 = P₂ + 3
要使总和为偶数 → P₂ =1
P₃：检查第 4、5、6、7 位 → P₃ + D₂ + D₃ + D₄ = P₃ + 0 + 1 + 1 = P₃ + 2
要使总和为偶数 → P₃ =0
第 4 步：得到最终编码
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 类型 | P₁ | P₂ | D₁ | P₃ | D₂ | D₃ | D₄ |
| 值 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
最终编码为：0110011
三、纠错过程
假设传输过程中第 5 位出错，接收方收到的编码为：
0 1 1 0 1 1 1（第 5 位从 0 变成了 1）
第 1 步：重新计算每个校验组的奇偶性
P₁ 组（第 1、3、5、7 位）：0 + 1 + 1 + 1 = 3 → 奇数 →校验失败，记为 1
P₂ 组（第 2、3、6、7 位）：1 + 1 + 1 + 1 = 4 → 偶数 →校验通过，记为 0
P₃ 组（第 4、5、6、7 位）：0 + 1 + 1 + 1 = 3 → 奇数 →校验失败，记为 1
第 2 步：拼出错误位置编号
将校验结果按 P₃P₂P₁ 排列：
P₃P₂P₁ = 101101（二进制）=5（十进制）
→ 第 5 位出错！
第 3 步：纠正错误
将第 5 位翻转：1 → 0
纠正后的编码：0110011，与原始编码完全一致。
四、如果没有错误呢？
如果接收到的编码完全正确，那么所有校验组的奇偶性都会通过：
P₃P₂P₁ = 000000 = 0，表示没有错误。
五、总结
| 步骤 | 内容 |
|---|---|
| 确定校验位数量 | 2 r ≥ d + r + 1 2^r \geq d + r + 12r≥d+r+1 |
| 放置校验位 | 放在 2 的幂次位置上 |
| 计算校验位 | 让每个校验组中 1 的个数为偶数 |
| 纠错定位 | 用 P₃P₂P₁ 拼出错误位置编号 |
| 纠错操作 | 翻转对应位置的那一位 |
海明码的精妙之处在于：校验位的位置设计和覆盖规则，天然保证了每个位置出错时，产生的校验结果都是唯一的。所以只要错 1 位，就一定能精确定位并纠正。
