海明码：从编码到纠错，一篇讲透

文章目录

• • • 海明码：从编码到纠错，一篇讲透
    • 一、确定校验位数量
    • 二、编码过程
    • • 第 1 步：确定校验位和数据位的位置
      • 第 2 步：确定每个校验位负责检查哪些位
      • 第 3 步：计算每个校验位的值（偶校验）
      • 第 4 步：得到最终编码
    • 三、纠错过程
    • • 第 1 步：重新计算每个校验组的奇偶性
      • 第 2 步：拼出错误位置编号
      • 第 3 步：纠正错误
    • 四、如果没有错误呢？
    • 五、总结

海明码：从编码到纠错，一篇讲透

海明码（Hamming Code）是纠错编码中最经典、最基础的方案，由理查德·海明于 1950 年提出。它的核心能力是：自动检测并纠正 1 位错误。

今天我们就用 4 位数据 1011 作为例子，完整走一遍海明码的编码和纠错过程。

一、确定校验位数量

校验位数量 r 需满足：

2

r

≥

d

+

r

+

1

2^r \\geq d + r + 1

2r≥d+r+1

其中 d 为数据位数。

对于 4 位数据：

2

3

=

8

≥

4

+

3

+

1

=

8

2^3 = 8 \\geq 4 + 3 + 1 = 8

23=8≥4+3+1=8，所以 r = 3。

总共 7 位编码，即 (7, 4) 海明码。

二、编码过程

第 1 步：确定校验位和数据位的位置

校验位固定放在位置编号为 2 的幂次的位上，其余位置放数据位：

• P = 校验位（第 1、2、4 位）
• D = 数据位（第 3、5、6、7 位）

将数据 1011 依次填入数据位：

第 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 步：得到最终编码

最终编码为：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₁ = 101

101（二进制）= 5（十进制）

→ 第 5 位出错！

第 3 步：纠正错误

将第 5 位翻转：1 → 0

纠正后的编码：0110011，与原始编码完全一致。

四、如果没有错误呢？

如果接收到的编码完全正确，那么所有校验组的奇偶性都会通过：

P₃P₂P₁ = 000

000 = 0，表示没有错误。

五、总结

海明码的精妙之处在于：校验位的位置设计和覆盖规则，天然保证了每个位置出错时，产生的校验结果都是唯一的。所以只要错 1 位，就一定能精确定位并纠正。