海明码简单介绍

简介

海明码是一种既能检错也能纠错的校验码，校验的原理其实用的是多重奇偶校验；

本篇文章只介绍能纠正一位错误的海明码，这种编码又称为SEC(Single-bit Eror Corection)码。

编码过程

这里以一个示例来进行说明编码过程，假设原始数据为：1101000

1、计算校验位的位数

根据公式 k + r ≤ 2^r - 1 计算，其中【r】为校验位位数( r 取满足公式的最小值)，【k】为原始数据的位数。

因此 1101000 对应的校验位的位数 r = 4，则海明码的位数 n = k + r = 7 + 4 = 11

原始数据用D表示，7位表示为：D₇D₆D₅D₄D₃D₂D₁

校验位用 P表示，4位表示为：P₄P₃P₂P₁

海明码用 H表示，11位海明码为：H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁

2、计算校验位的位置

经过上一步计算，虽然知道了校验位的位数，但是怎样将4位校验位和7位数据位组合成11位海明码呢？

在海明码中，校验位通常放置于2的幂次的位置上，也就是P_i放在 2^i-1 的位置上，如下：

• P₁ 位于第 1 (2^1-1) 位（H₁ 所在位置）
• P₂ 位于第 2 (2^2-1) 位（H₂ 所在位置）
• P₃ 位于第 4 (2^3-1) 位（H₄ 所在位置）
• P₄ 位于第 8 (2^4-1) 位（H₈ 所在位置）

然后将信息位按照从右到左依次将数据填充上去，最后整个海明码的数据表示如下：

3、将信息位进行分组

海明码的本质其实是多组偶校验，也就是每一组的数据进行异或运算，如果结果是0，表明没有错，等于1说明有错。

所以我们需要将7位信息位进行分组，分组规则是通过信息位的位置信息进行分组的，如下：

从右到左依次有4列，取出每列每行值为1的数据位组成一组，共有4组，依次为

• G₁ ：D₁、D₂、D₄、D₅、D₇

• G₂ ：D₁、D₃、D₄、D₆、D₇

• G₃ ：D₂、D₃、D₄

• G₄ ：D₅、D₆、D₇

4、计算校验位的值

通过以上步骤，我们将信息位分成了4组数据，校验位的值就等于每组数据异或后的值，

P₁ = D₁ ⊕ D₂ ⊕ D₄ ⊕ D₅ ⊕ D₇ = 0
P₂ = D₁ ⊕ D₃ ⊕ D₄ ⊕ D₆ ⊕ D₇ = 0
P₃ = D₂ ⊕ D₃ ⊕ D₄ = 1
P₄ = D₅ ⊕ D₆ ⊕ D₇ = 1

5、海明码的校验

每个校验组分别利用校验位和参与该校验位的数据位进行偶校验检查，构成4个校验方程，如下：
S1 = P₁ ⊕ D₁ ⊕ D₂ ⊕ D₄ ⊕ D₅ ⊕ D₇
S2 = P₂ ⊕ D₁ ⊕ D₃ ⊕ D₄ ⊕ D₆ ⊕ D₇
S3 = P₃ ⊕ D₂ ⊕ D₃ ⊕ D₄
S4 = P₄ ⊕ D₅ ⊕ D₆ ⊕ D₇

以上分组保证了，没有出错的情况下 S1 S2 S3 S4 都应该等于0（偶校验检查，1的数量为偶数）

校验时，如果S1 = 1，S2\S3\S4都等于0，那么可以确定是P1出错了，也就是P1的值由 0 变为 1了

为什么这样确定呢？可以逐一排查，比如：

• 如果D₁ 错，那么 S2 应该也等于1，也出错
• 如果D₂ 错，那么 S3 应该也等于1，也出错
• 如果D₄ 错，那么 S2 、S3 应该也等于1，也出错
• 如果D₅ 错，那么 S4 应该也等于1，也出错
• 如果D₇ 错，那么S2 、S4 应该也等于1，也出错

如果以上表述没有看明白，可以参考下图，更直观一些

6、海明码纠错

现在数据位、校验位的位置都已确定，校验位的值也已计算出来，校验原理也知道了，咱们再说下纠错

例1： 只有S1出错，在上一步知道是P1出错了，也就是H1出错

S1 = 1
S2 = 0
S3 = 0
S4 = 0

例2：只有S2出错呢，和上一步排查错误原理一样，可以确定是P2出错了，也就是H2出错

S1 = 0
S2 = 1
S3 = 0
S4 = 0

例3：只有S3出错呢，确定是D1出错了，也就是H4出错

S1 = 0
S2 = 0
S3 = 1
S4 = 0

通过以上示例，大家应该注意到了，出错的位数其实和S4 S3 S2 S1排列组合成的二进制数是一样的，如下：

例1 排列的值是0001 = 1

例2 排列的值是0010 = 2

例3 排列的值是0100 = 4

咱们再举个例子，比如H11（D7）错了，有可能是1变为0，或者由0变为1，不管哪种情况，肯定导致了D7所在的组的偶检验的结果是1，那么也就是S4、S2、S1为1，

排列的值是：1011 = 11