介绍

海明校验码（Hamming Code）是一种用于 错误检测 和 纠正 的编码技术，它是由理查德·海明在1950年代提出的

海明码通过在数据中添加 冗余位（parity bits），使得在 传输过程 中出现的错误可以被 检测 和 纠正

特点

能够 检测错误 和 纠正错误

原理

• 有一个数据块，其长度为 m 位

• 要在数据块中添加 r 个冗余位（海明校验码），那么数据块的总长度变为 m + r

• 冗余位（海明校验码）的位置：通常是 2^(r-1)，r 从 0 开始，即 第1位、第2位、第4位、第8位 等等，这些位置称为 校验位（Parity bits）

第一步：计算校验位的数量

已知 m（数据位的数量） 的情况下，求出最小的 r（校验位的数量）

公式：

2^r - 1 >= m + r

解释：

• r：海明校验码的数量。
• m：数据位的数量
• 2^r -1：一共可以表示 2^r 种校验信息结果，其中有一种要用来表示 没有出错 的情况，则其余还剩 2^r - 1 种结果

第二步：计算每个校验位的位置

海明校验码的位置：通常是 2^(r-1)，r 从 0 开始

即 第1位、第2位、第4位、第8位 等等

这些位置称为 校验位（Parity bits）

第三步：确定每个数据位与哪些校验位有关系

第四步：确定每个校验位与哪些数据位有关系

根据第三步总结

第五步：各个海明码，由有关系的数据位异或得出结果

例子

求二进制数据 1011 的海明码

第一步：计算海明码的数量

公式：

2^r - 1 >= m + r

m数据位是 4 ，套入公式：

2^r - 1 >= 4 + r

变化公式：

2^r >= 5 + r

当 r=1 时不成立
当 r=2 时不成立
当 r=3 时 成立

所以海明码的数量是 3

第二步：计算每个校验位的位置

由上面原理可知：

第一个海明码位置：2^0 = 1
第二个海明码位置：2^1 = 2
第三个海明码位置：2^2 = 4

数据位+校验位如下：

提示：表头从 1 开始算，校验码的 索引 从 0 开始，是为了方便第三步计算

第三步：确定每个数据位与哪些校验位有关系

第7位数据 与 哪些 校验位 有关系

见下面计算：

7 = 2^2 + 2^1 + 2^0 = 4 + 2 + 0

说明 第7位数据：与 上面表格 第4位、第2位、第1位 校验位有关系

即：第7位数据：与 校验位2、校验位1、校验位0 有关系

第6位数据 与 哪些 校验位 有关系

见下面计算：

6 = 2^2 + 2^1 = 4 + 2

说明 第6位数据：与 上面表格 第4位、第2位 校验位有关系

即：第6位数据：与 校验位2、校验位1 有关系

第5位数据 与 哪些 校验位 有关系

见下面计算：

5 = 2^2 + 2^0 = 4 + 1

说明 第5位数据：与 上面表格 第4位、第1位 校验位有关系

即：第5位数据：与 校验位2、校验位0 有关系

第3位数据 与 哪些 校验位 有关系

见下面计算：

3 = 2^1 + 2^0 = 2 + 1

说明 第3位数据：与 第2位、第1位 有关系

即：第3位数据：与 校验位1、校验位0 有关系

第四步：确定每个校验位与哪些数据位有关系

根据第三步可知：

• 校验位2：与 第7位数据、第6位数据、第5位数据 有关

• 校验位1：与 第7位数据、第6位数据、第3位数据 有关

• 校验位0：与 第7位数据、第5位数据、第3位数据 有关

第五步：各个海明码，由有关系的数据位异或得出结果

• 校验位2：1(第7位数据) ⊕ 0(第6位数据) ⊕ 1(第5位数据) = 0

• 校验位1：与 1(第7位数据) ⊕ 0(第6位数据) ⊕ 1(第3位数据) = 0

• 校验位0：与 1(第7位数据) ⊕ 1(第5位数据) ⊕ 1(第3位数据) = 1

最终结果

参考：
https://blog.csdn.net/weixin_47872288/article/details/137608772

https://blog.csdn.net/breakin123/article/details/120817489

原文出处：/show_1GWrjinLaJC.html