由浅至深了解海明码：实现、原理以及细节

目录

海明码的诞生目的

引入：如何确定哪一位出错呢

关于编号

*为什么要转为二进制？不能是十进制和其他进制？

二进制的特性

S 的值直接等于出错位置

校验位、数据位，位置怎么排

*为什么校验位要放在位置编号等于 2 的幂的地方？

海明不等式（求校验位数量 k）

*为什么这个不等式一定成立？

海明码分组规则

*为什么要进行这样的分组

计算校验位的值

完整例子

*为什么要偶检验

*这个校验的目的是什么？

接收端如何纠错（校正因子 S）

*实现纠错的原理

完整过程

前言：带*的是额外补充的问题以及原理部分，可以暂时跳过

海明码的诞生目的

数据在存储或者传输的时候，比特有可能出错：0 翻成 1，1 翻成 0。

传统的奇偶校验码： 增加 1 个校验位

只能发现：这一串里面存在错误。 但是有一个巨大短板：不知道到底是哪一位错了，没办法直接修好，只能丢弃数据，要求对方重发。

海明码就是为了解决这个问题：

✅ 不仅可以检测出发生了错误

✅ 还能定位哪一个比特出错，直接把这一位翻转，完成纠错

⚠️ 限制：普通海明码只能纠正 1 位错误。如果同时 2 个比特出错，会判断错误。

引入：如何确定哪一位出错呢

要确定一个特定的位置，我们往往要借助这个位置的编号来确定，因为编号是特定并且唯一的。

加入一串数据，第67位出错，那我们如何想办法定位呢？海明码是这样的：先确定个位数是几，再确定十位数是几。这就是海明码的基本原理，不同的是海明码会将编号变为二进制，来确认每一位数。详细原理请看下文。

关于编号

假设目前有一串二进制数据：10101100

我们正常以为的编号是这样的：

重点：位置编号从 1 开始计数，不是从 0。

但实际上，海明码是将编号转化为二进制

*

*为什么要转为二进制？不能是十进制和其他进制？

//此处为额外补充，可以先跳过不看

二进制的特性

这里运用了二进制的只有有无两种状态的特性

根据海明码的基本原理，我们知道我们要确定这个位置的编号的每一个数。

之后我们以每一位要进行分组

每一个校验组 P，对于一个位置来说只有两种情况：

① 这个位置在本组内

② 这个位置不在本组内

正好对应二进制的：1（在组里）、0（不在组里）。

二进制每一位：只有 0、1，刚好表示「是否加入这个 P 组」

十进制每一位：0~9，有 10 个数字，我们根本用不上这么多状态。

举例子：位置编号是 5 二进制 101： 右 0 位 = 1 → 在P1；

右 1 位 = 0 → 不在P2；

右 2 位 = 1 → 在P3；

刚好表达：P1，P3

如果强行用十进制来分组： 十进制 5，只有一个数字 5。 我们怎么靠这个 “5”，判断它该加入哪几个 P 组？

十进制的单个数字，不能拆成多个独立的 0/1 开关。

S 的值直接等于出错位置

按照二进制规则分组，算出校正因子 S 拼起来，这个二进制数直接就是出错位置编号。

• S=101 → 二进制 101 = 十进制 5 → 第 5 位出错。

如果用十进制分组，S 和位置编号之间没有这种天然对应关系。

就算算出 S，你还要自己建立相应的对应关系，额外查表，非常麻烦。

校验位、数据位，位置怎么排

海明码由两种比特组成：

• 数据位 D：你原本想要传输的原始二进制数据
• 校验位 P：额外新增的比特，专门用来查错纠错

排布规则：

校验位 P，固定放在位置编号等于 2 的幂的地方：

2^0=1号位 → P1

2^1=2号位 → P2

2^2=4号位 → P3

2^3=8号位 → P4

也就是位置：1，2，4，8，16…… 全部放校验位 P。

剩下所有位置（3、5、6、7、9、10……），放原始数据 D。

重点：位置编号从 1 开始计数，不是从 0。

举例：

4 位原始数据，总海明码位置 1~7

位置1： P1

位置 2：P2

位置 3：D

位置 4：P3

位置 5：D

位置 6：D

位置 7：D

*为什么校验位要放在位置编号等于 2 的幂的地方？

//为额外补充，可以跳过

根据海明码的基本原理。我们要依次确定编码中的每一位的数字，那么每一组都应该有各种的“代表”：

这样，每一个位数都有对应的自己的“组长”

海明不等式（求校验位数量 k）

对于一组数据，我们要求出它需要多少位的检验位

• n：原始数据的比特个数
• k：需要添加的校验位比特个数

海明不等式：

例子：

原始数据 n=4 位

试 k=2：2^2=4，4 >= 4+2+1 → 4 >= 7,不成立

试 k=3：2^3=8，8 >= 4+3+1 → 8 >= 8，成立

所以 k=3，需要 3 个校验位。 总编码长度 = n + k = 7 位。

*为什么这个不等式一定成立？

//为额外补充，可以跳过

为了方便理解，先将不等式变形

我们不妨先把没有用到的编号0，放进来

重点：位置编号从 1 开始计数，不是从 0。这里只是方便理解

 可以代表检验位可以覆盖的全部可检验的编号

（向左覆盖）

为什么可以这样覆盖呢？

因为二进制中，2的幂数每多一个，二进制就多一位，所以就可以覆盖前边所以的编号了

再看

那就是我们正常情况下去掉0的编号了

 就是所有有效的检验总位数（包括检验码本身）

 就是所有的位置

该不等式可以理解为：

所有有效的检验总位数  覆盖了    所有的位置

所以海明码可以生效

所以成立

海明码分组规则

前提约定：

二进制最右侧 = 第 0 位

二进制右数第二位 = 第 1 位

二进制右数第三位 = 第 2 位

……

分组规则原文： 对于某个位置编号，如果它的二进制第 i 位是 1，那么这个位置上的比特，就要归入校验位 Pi+1 的分组。

重点：一个位置可以归于多组；检验位也包括在内

简单来说就是：

该编号哪一位上有1，就去找哪一个检验位上同一位置也有1，那就归于这个组

举例：位置 1 ~ 7

表格

*为什么要进行这样的分组

根据海明码的基本原理，我们要找出一个数的每一位，那就当然要按一位数一位数这样分组，具体实现原理请往下看

计算校验位的值

我们已经分好组了，接下来算出每一个校验位 P 应该填 0 还是 1。

我们有 3 个分组：

• P1组：位置 1、3、5、7
• P2组：位置 2、3、6、7
• P3组：位置 4、5、6、7

位置 1 放P1，位置 2 放P2，位置 4 放P3，

这三个是校验位，现在还不知道是 0 还是 1。 位置 3、5、6、7 是我们要传输的原始数据，数值已知。

默认：偶校验 偶校验要求：这一整组里面，全部比特异或之后，结果 = 0

异或简单记

相同得 0，不同得 1

或者可以理解为保持该组内1的个数为偶数

拿 P₁组举例

D3,D5,D7都是已知的，只有P1未知。 我们把式子变形：

同理：

完整例子

原始数据：

1011

D3=1,

D5=0,

D6=1,

D7=1 

得到三个校验位：P1=0，P2=1，P3=0

组合起来，位置 1~7 海明码：0 1 1 0 0 1 1

核心一句话： 每组里面，把所有已知数据位异或，得到的结果，就是本组校验位 P 的值。目的：保证整组异或结果为 0（偶校验）。

*为什么要偶检验

其实偶校验和奇校验都可以的，不过常见的是偶校验

历史上偏好偶校验的小原因

⚠重点：这个只是硬件一点点便利，不是海明码必须偶校验的根本理由。

*这个校验的目的是什么？

我们填好 P（0 或者 1），是为了人为制造一个规律：

发送方编码完成后，每一个校验组，全部比特异或满足约定（偶校验 = 0 / 奇校验 = 1）。

也就是说创造了一个协议：

我以偶校验进行，接收方也要用偶检验进行检测；奇校验也一样

除了这个理由之外，就是检验位必须要有一位的bit填充，不能空着，仅此而已

接收端如何纠错（校正因子 S）

发送方把海明码编好发出去。接收方拿到这一串编码之后，再次按照原来的分组，分别做异或运算，得到三个校正因子：S1、S2、S3。

分组和发送时完全一样：

• S1：P1组全部比特异或结果（位置 1、3、5、7）
• S2：P2组全部比特异或结果（位置 2、3、6、7）
• S3：P3组全部比特异或结果（位置 4、5、6、7）

把 S3 S2 S1 拼成一个二进制数字：

注意：普通海明码只能保证1 位出错时正常纠错。如果同时 2 位出错，会给出错误的出错位置。

举个例子： 算出 S3 S2 S1 = 101，二进制 101 等于十进制 5 → 第 5 号位出错。翻转第 5 位即可。

*实现纠错的原理

S1对应P1

S2对应P2

S3对应P3

S/1P1都是负责第0位的检验

如果传输过程中没有差错，那么S1＝P1 = 0，也代表本位没有错误

若有（一处）错误，那么S1 = 1，表明这一位存在错误

同理第1位，第2位，第3位…..

将它们组合起来

如：S3 S2 S1 它们就可以凑出一个完整的二进制数，同时这个二进制数是和编号的二进制数是一一对应的，是唯一的

这个二进制数就是出错的bit对应的编号，之后进行反转即可纠错

同时也解释了为什么海明码只能用于出现一次错误的情况

若出现两次错误，则会出现：

同一组的两次错误：不会报错

不同组的：乱报错

完整过程

题目：原始数据 1011（n=4 位）

步骤 1：用海明不等式求校验位 

n=4：k=3，2^3 >= 4+3+1 → 8 >= 8成立，需要 3 个校验位。

总编码长度 4+3=7 位。

步骤 2：位置分配（位置从 1 开始）

位置 1：P1，

位置 2：P2，

位置 3：D=1，

位置 4：P3，

位置 5：D=0，

位置 6：D=1，

位置 7：D=1

步骤 3：分组 P1组：1,3,5,7

                      P2组：2,3,6,7

                      P3组：4,5,6,7

步骤 4：偶校验，求校验位

得到海明码（位置 1~7）：0 1 1 0 0 1 1

步骤 5：模拟出错，假设传输后第 5 位翻转，收到码：0 1 1 0 1 1 1

步骤 6：接收端计算校正因子

二进制 101 = 5，代表第 5 位出错。翻转第 5 位，恢复原始海明码。

参考以及推荐：海明码原理详细讲解(别再死记硬背了)_哔哩哔哩_bilibili