你家猫娘都能看懂的海明码教程

在数据校验中，海明码绝对是一个非常关键的主题喵。你可能听说过它，和「奇偶校验」这种只能检查出错误的校验码不同，「海明码」不仅可以检查错误，还可以确认错在哪里，并进行修正。

但是它到底是怎么计算的，原理又究竟是什么？为什么可以查错并修正？这篇文章就从头开始来聊聊海明码，让你和你家的猫娘看了之后都能绝对通透喵。

奇偶校验

在开始之前，我们得先理解一下什么是奇偶校验，它是海明码的基础。

我们都知道计算机用的是二进制 0 和 1 进行数据保存和传输。奇偶校验其实就一句话：

增加校验位，把数据中的 1 的数量补全。

也就是说：

• 奇校验：用校验位把 1 的数量补充到奇数。也就是说，数据中有奇数 1 就补 0，否则补 1。
• 偶校验：用校验位把 1 的数量补充到偶数。也就是说，数据中有奇数 1 就补 1，否则补 0。

是的，增加校验位之后，我们就可以按照进行校验的方式来验证数据的合法性了。比如偶校验收到的数据里面只有奇数个 1，那么绝对发生错误了喵。

创建海明码

我们提到过，海明码需要查错+修正错误。

校验位数量

前者用奇偶校验就可以了，只需要一位校验位。但是要修正错误，一位肯定是不够的。那问题来了，要让海明码有改错功能，需要多少位数呢？

海明码的设计者非常聪明，先直接告诉你结论吧：

假设数据位有 $M$ 位数，则需要 $N$ 位校验位，使得以下式子满足——

你肯定在想，这是怎么得出来的？你先别急，我们来稍微计算一下，你就明白了喵。

让我们来想想，数据从一端传送到另一端，一位出错有几种可能呢？

• 完全不出错
• 第一位出错
• 第二位出错
• 第三位出错
• ……
• 第 $N$ 位出错

那我问你，上面有几种情况？小猫猫都知道，$N+1$ 种。

那我再问你个事儿，需要多少位二进制数字才能表示至少 $N+1$ 种错误呢？简单，只要 $M$ 位，满足 $2^M \ge N + 1$ 即可。

而校验位只需要能表示出所有的出错状态，我们就可以根据校验位来确定错在什么地方了。所以需要 $M$ 位的校验位。

但是等等，当你真正把校验位加入进去的时候，问题又来了——校验位也可能出错！也就是说，我们现在错误的情况增加了：

• $M$ 位校验位出错，共 $M$ 种情况
• $N$ 位数据位出错，共 $N$ 种情况
• 完全不出错，1 种情况

那么，我们稍微改一下公式就好啦：

安插校验来找到出错的位数

好了，我们已经知道校验位有多少了。现在面临一个巨大难题：怎么让它们检查错误，并且找出出错在哪里呢？

我们先把二进制什么的忘了，考虑一个类似「海龟汤」的小游戏。

现在有一只猫娘藏到了排队的队列中。假设队列有 8 个完全一致的生物（猫娘把自己隐藏得和其它人类完全一致），你只能通过「是/否」提问来找出猫娘的位置。那么，从数学的角度上来讲，如何最快找出猫娘呢？

如果你听说过一点算法，并且玩过「猜数字游戏」，那么你可能很容易想到一个叫作二分查找的东西。它的原理是，在数组中每次查找二分之一，确定目标在切开来的那一半，然后缩小范围。重复操作，直到锁定目标。

比如，你可以这么问，假设得到了如下的回答：

1. 猫娘在前 4 位吗？「是的」-> 1-4
2. 猫娘在前 2 位吗？「不是」-> 3-4
3. 猫娘在第 3 位吗？「不是」-> 4 找到了！

看起来，我们只需要三次就能找到目标了。

等等，是不是有些熟悉？$2^3 = 8$ 不就是整个队列的长度吗？

恭喜你，你找到关键点了！二分查找告诉我们最少需要三次，实际上本质就是三位二进制编码的组合！

现在捡起二进制，让我们扮演 CPU，像计算机一样思考吧！把下标从 0 开始的项根据编号写出其二进制编码：

还记得二分查找的三个问题吗？现在，我们要确定一个编号，那么只需要问三个问题（假设是如下的回答）：

• 第一位是 1 还是 0？-> 是 1，确定是 4-7
• 第二位是 1 还是 0？-> 是 1，确定是 6-7
• 第三位是 1 还是 0？-> 是 0，确定是 6

问完这个问题，你就必然能确定一个数据编号了。

这就是二分查找在二进制下的表示，实际上做的是同一件事情~

现在我们回到海明码，你应该能看出一点门道了。这 8 位二进制数（包含校验位），我们只需要让每一个校验位负责一个问题，就可以确定是哪一位出错了：

• 第一个校验位出错了吗？-> 是，确定错在 4-7
• 第二个校验位出错了吗？-> 是，确定错在 6-7
• 第三个校验位出错了吗？-> 没有，确定错在 6

根据这个原理，是不是发现了一个由神奇的二进制创造的规律呢？

你仔细品一品，第一个校验位出错 = 错在 4-7？这是个什么规律？

聪明的猫猫一定已经发现了，4-7 的二进制数位，左数第一位（从低到高第三位），都是 1。也就是说，第一个校验位出错，说明出错在：

• 4=100
• 5=101
• 6=110
• 7=111

哦！好像发现了什么不得了的事情喵。再来看看，第二位也出错了，所以剩下这两种可能性：

• 6=110
• 7=111

第三个校验位，如果它出错：

• 7=111

所以，如果它没有出错（排除掉 7）：

• 6=110

现在忘掉二分查找——

如果第一个校验位出错，则可能错在：

• 4=100
• 5=101
• 6=110
• 7=111

第二个校验位：

• 2=010
• 3=011
• 6=110
• 7=111

第三个校验位：

• 1=001
• 3=011
• 5=101
• 7=111

哦我的上帝，我好像找到规律了。我们之前已经得出了结论，如果某一个校验位校验的数出错了，那么出错的位置对应的数（也就是位置下标），其对应校验位的二进制数位必然是 1。否则，说明出错位置对应的下标，其对应校验位的二进制数位为 0。

也就是说，三个监测位「是否出错」可以编码为三位二进制数，出错 = 1，没有出错 = 0。上面的校验位的出错状况是 110，转换为二进制就是 6 啦，所以是第六位出错了。

哦！从二分查找出发，现在我们有了一种「编码方式」，能够用二进制表示所有的出错可能性。

实际上，这就是二进制的一些基本性质而已，我这里也只是把它们重新讲了一遍。

海明码的生成

我们刚才一直在提「是否出错」，但是到底如何判断有没有出错呢？欸，这就是海明码的巧妙之处了喵——只要你彻底搞懂了上面的解释，那么下面的结论只是一些推论而已。

我们需要解决两个问题：第一，每个校验位检查的是哪几位的错误？第二，这几个位数，什么情况下才算出错？

第二个问题很简单先放着，先来趁热打铁解决第一个问题。

我相信超级聪明的猫猫们已经找到答案了，我把上一节原封不动地抄过来。

如果第一个校验位出错，则可能错在：

• 4=100
• 5=101
• 6=110
• 7=111

如果第二个校验位出错，则可能错在：

• 2=010
• 3=011
• 6=110
• 7=111

如果第三个校验位出错，则可能错在：

• 1=001
• 3=011
• 5=101
• 7=111

噢我的上帝，我真的没想到同样的东西还能得出第二个结论：海明码的每一个校验位，检查的就是用二进制表示时，校验位对应数位为 1 所组成的所有下标。

也就是说，第一位检查的数位的下标为 1**，第二位检查的数位的下标为 *1*，第三位检查的数位的下标为 **1。其中，* 可以是任意数字。

好了，轮到你了。

既然已经知道海明码每个校验位检查的是哪几个数位（这几个数位，也叫作「一个校验分组」），现在来看看另一个重要问题——校验位随数据一起发送，那它们应该放在哪几位上喵？

先给你结论吧：

第 i 位校验位（从低到高的 i 位），应该放在 $2^i$ 位置上（从低到高数）。

你先把结论记一下喵，我们要用它了。而要真正理解并解决这个问题，我们得先解决之前提到的「什么情况下才算出错」。

聪明的喵肯定很快就想到了，这不就是奇偶校验问题嘛。通过补全为偶/奇，来判断几个数位是否发生了改变。来看实际例子：

假设我们要传递数据 1010，使用偶校验：

1. 根据公式 $2^N \ge M + N + 1$，计算出需要 3 位校验位。
2. 根据上述规律，校验位应放在第 1 2 4 位上。现在的数据：? ? 1 ? 0 1 0，其中问号为校验位
3. 根据校验位检查的数位规律，计算出第一位检查 1 3 5 7，也就是 ? 1 0 0，偶校验，第一个校验位为 1。 1 ? 1 ? 0 1 0
4. 根据校验位检查的数位规律，计算出第二位检查 2 3 6 7，也就是 ? 1 1 0，偶校验，第二个校验位为 0。 1 0 1 ? 0 1 0
5. 根据校验位检查的数位规律，计算出第三位检查 4 5 6 7，也就是 ? 0 1 0，偶校验，第三个校验位为 1。 1 0 1 1 0 1 0

你做到了！得到的海明码是 1011010。

现在我们可以回答为什么校验码放在 $2^i$ 位了。

这是因为，添加的校验码必须仅影响一个校验分组的奇偶性。根据二进制表示的逻辑，如果你把校验位放在 $2^i$ 这一位上，那么它的二进制码必然只有一个 1，其余都是 0（例如，第一个校验位 001，第二个校验位 010）。因此，它必不可能出现在别的校验分组中，因为别的校验分组必然有其它位数是 1。

问题来了，为什么只能影响一个校验分组的奇偶呢？

这个问题就很简单了——试想一下，如果你的校验位会影响多个分组，那么你该怎么确定校验位的奇偶呢？A 分组填好变成偶校验了，结果 B 分组又变成奇数个 1……这也太麻烦了，根本没法确定！所以，校验位放在 $2^i$ 位，是必须的，要牢牢记住这个结论喵~

海明码的检错纠错

既然我们已经写出了海明码，是时候来点纠错实战了。继续用上面的例子——数据 1010，偶校验海明码 1011010。

假设经过传输过程中宇宙射线某些因素的影响，接收方实际接收到的是 1011000（注意第六位出错了），我们来走一遍流程喵：

1. 确定校验位为 1 2 4 位，也就是 1011000。
2. 第一个校验位检查 1 3 5 7 位，它们是 1100，没问题，分组没有出错。
3. 第二个校验位检查 2 3 6 7 位，它们是 0100，不符合偶校验，说明这个分组出错了。先记下来。
4. 第三个校验位检查 4 5 6 7 位，它们是 1000，不符合偶校验，说明这个分组出错了。先记下来。
5. 将校验位是否出错从低到高拼出来，出错的记作 1，没有出错记作 0，得到校验结果 110（注意，第一个校验位是低位，写在最后。注意顺序！）
6. 将结果转换为十进制数字，110 = 6。说明第十位出错了，准备修正
7. 修正海明码 1011010，去除校验位得到数据 1010。

怎么样，是不是已经完全理解原理了？

后记

海明码是一个非常神奇的检错机制，它的本质依旧是二进制树的表示。只要理解了校验位要多少、校验位在查哪几位、怎么通过校验分组状态拼出错误位数、校验位应该放在什么地方，就自然能够理解它的工作原理，以后来再多的题目都可以做了。

那么，本文就到这里了，祝各位猫猫有所收获！

练习答案

答案：

第一位检查 **1，也就是 001 011 101 111，转换为十进制，说明检查的是第 1 3 5 7 位数。

第二位检查 *1*，也就是 010 011 110 111，第 2 3 6 7 位数。

第三位检查 1**，也就是 100 101 110 111，第 4 5 6 7 位数。

版权声明

作者：Sam Hou

原文链接：https://blog.samhou.moe/cs-with-neko-hamming/

本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请保留此版权声明，注明来源 SamHou's Blog！