软考-软件设计：海明校验码 作者：马育民 • 2025-04-01 09:54 • 阅读：10004 # 介绍 海明校验码（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 ``` **数据位+校验位如下：** |第7位 |第6位 |第5位 |第4位 |第3位 |第2位 |第1位| | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |------------ | |1 |0 |1 |校验位2 |1 |校验位1 |校验位0| **提示：**表头从 `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` ### 最终结果 |第7位 |第6位 |第5位 |第4位 |第3位 |第2位 |第1位| | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |------------ | |1 |0 |1 |校验位2 |1 |校验位1 |校验位0| |1 |0 |1 |0 |1 |0 |1| 参考： https://blog.csdn.net/weixin_47872288/article/details/137608772 https://blog.csdn.net/breakin123/article/details/120817489 原文出处：http://malaoshi.top/show_1GWrjinLaJC.html