文章目录
引言
奇偶校验码、CRC循环校验码：只能告诉“我错了”。【校验码也被称为检错码（Error Detecting Code）】
我们需要 纠错码：不仅告诉我们“我错了”，还能告诉我们“错哪儿了”。【不仅可以知道哪里的数据错了，还能直接把数据给改对】
一、海明码：我们需要多少信息冗余？
【历史】
最知名的纠错码：海明码（Hamming Code）
发明人：Richard Hamming（理查德·海明）
发明时期：上世纪四十年代
应用：上一讲所说到的 ECC 内存，也还在使用海明码来纠错。
【7-4海明码】
最基础的海明码：7-4海明码
“7”指实际有效的数据，一共是7位（Bit）。
“4”指的是额外存储了4位数据，用来纠错。
说明：纠错码的纠错能力是有限的。（不是说不管错了多少位，我们都能给纠正过来。不然我们就不需要那 7 个数据位，只需要那 4 个校验位就好了，这意味着我们可以不用数据位就能传输信息了。这就不科学了。）事实上，在 7-4 海明码里面，我们只能纠正某 1 位的错误。
4位校验码，一共可以表示2^4=16个不同的数。
根据数据位计算出来的校验值，一定是确定的。
所以，如果数据位出错了，计算出来的校验码，一定和确定的那个校验码不同。
那可能的值，就是在 2^4 - 1 = 15 那剩下的 15 个可能的校验值当中。
【新的疑问】
15 个可能的校验值，其实可以对应 15 个可能出错的位。这个时候你可能就会问了，既然我们的数据位只有 7 位，那为什么我们要用 4 位的校验码呢？用 3 位不就够了吗？2^3 - 1 = 7，正好能够对上 7 个不同的数据位啊！
【解答】
你别忘了，单比特翻转的错误，不仅可能出现在数据位，也有可能出现在校验位。校验位本身也是可能出错的。所以，7 位数据位和 3 位校验位，如果只有单比特出错，可能出错的位数就是 10 位，2^3 - 1 = 7 种情况是不能帮我们找到具体是哪一位出错的。
【数据位和校验位的对照表】
事实上，如果我们的数据位有 K 位，校验位有 N 位。那么我们需要满足下面这个不等式，才能确保我们能够对单比特翻转的数据纠错。这个不等式就是：
K + N + 1 <= 2^N
在有 7 位数据位，也就是 K=7 的情况下，N 的最小值就是 4。4 位校验位，其实最多可以支持到 11 位数据位。我在下面列了一个简单的数据位数和校验位数的对照表，你可以自己算一算，理解一下上面的公式。
二、海明码的纠错原理
1、4-3 海明码（4 位数据位，3 位校验位）
我们把 4 位数据位，分别记作 d1、d2、d3、d4。这里的 d，取的是数据位 data bits 的首字母。我们把 3 位校验位，分别记作 p1、p2、p3。这里的 p，取的是校验位 parity bits 的首字母。
从 4 位的数据位里面，我们拿走 1 位，然后计算出一个对应的校验位。这个校验位的计算用之前讲过的奇偶校验就可以了。比如，我们用 d1、d2、d4 来计算出一个校验位 p1；用 d1、d3、d4 计算出一个校验位 p2；用 d2、d3、d4 计算出一个校验位 p3。就像下面这个对应的表格一样：
这个时候，你去想一想，如果 d1 这一位的数据出错了，会发生什么情况？我们会发现，p1 和 p2 和校验的计算结果不一样。d2 出错了，是因为 p1 和 p3 的校验的计算结果不一样；d3 出错了，则是因为 p2 和 p3；如果 d4 出错了，则是 p1、p2、p3 都不一样。你会发现，【当数据码出错的时候，至少会有 2 位校验码的计算是不一致的】。
那我们倒过来，如果是 p1 的 【校验码出错了】，会发生什么情况呢？这个时候，只有 p1 的校验结果出错。p2 和 p3 的出错的结果也是一样的，【只有一个校验码的计算是不一致的】。
所以校验码不一致，一共有 2^3-1=7 种情况，正好对应了 7 个不同的位数的错误。我把这个对应表格也放在下面了，你可以理解一下。
可以看到，海明码这样的纠错过程，有点儿像电影里面看到的推理探案的过程。通过出错现场的额外信息，一步一步条分缕析地找出，到底是哪一位的数据出错，还原出错时候的“犯罪现场”。
2、海明码编码方案的实现
看到这里，相信你一方面会觉得海明码特别神奇，但是同时也会冒出一个新的疑问，我们**怎么才能用一套程序或者规则来生成海明码呢？**其实这个步骤并不复杂，接下来我们就一起来看一下。
首先，我们先确定编码后，要传输的数据是多少位。比如说，我们这里的 7-4 海明码，就是一共 11 位。
然后，我们给这 11 位数据从左到右进行编号，并且也把它们的二进制表示写出来。
接着，我们先把这 11 个数据中的二进制的整数次幂找出来。在这个 7-4 海明码里面，就是 1、2、4、8。这些数，就是我们的校验码位，我们把他们记录做p1～p4。如果从二进制的角度看，它们是这 11 个数当中，唯四的，在 4 个比特里面只有一个比特是 1 的数值。
那么剩下的 7 个数，就是我们 d1-d7 的数据码位了。
然后，对于我们的校验码位，我们还是用奇偶校验码。但是每一个校验码位，不是用所有的 7 位数据来计算校验码。而是 p1 用 3、5、7、9、11 来计算。也就是，在二进制表示下，从右往左数的第一位比特是 1 的情况下，用 p1 作为校验码。
剩下的 p2，我们用 3、6、7、10、11 来计算校验码，也就是在二进制表示下，从右往左数的第二位比特是 1 的情况下，用 p2。那么，p3 自然是从右往左数，第三位比特是 1 的情况下的数字校验码。而 p4 则是第四位比特是 1 的情况下的校验码。
这个时候，你会发现，任何一个数据码出错了，就至少会有对应的两个或者三个校验码对不上，这样我们就能反过来找到是哪一个数据码出错了。如果校验码出错了，那么只有校验码这一位对不上，我们就知道是这个校验码出错了。
上面这个方法，我们可以用一段确定的程序表示出来，意味着无论是几位的海明码，我们都不再需要人工去精巧地设计编码方案了。
三、海明距离：形象理解海明码的作用
其实，我们还可以换一个角度来理解海明码的作用。【对于两个二进制表示的数据，他们之间有差异的位数，我们称之为海明距离】。
比如 1001 和 0001 的海明距离是 1，因为他们只有最左侧的第一位是不同的。而 1001 和 0000 的海明距离是 2，因为他们最左侧和最右侧有两位是不同的。
于是，你很容易可以想到，所谓的进行一位纠错，也就是所有和我们要传输的数据【这里指：数据位+校验位 的数】的海明距离为 1 的数，都能被纠正回来。
而任何两个实际我们想要传输的数据【数据位+校验位】，海明距离都至少要是 3。
你可能会问了，为什么不能是 2 呢？因为如果是 2 的话，那么就会有一个出错的数，到两个正确的数据的海明距离都是 1。当我们看到这个出错的数的时候，我们就不知道究竟应该纠正到那一个数了。
在引入了海明距离之后，我们就可以更形象地理解纠错码了。在没有纠错功能的情况下，我们看到的数据就好像是空间里面的一个一个点。这个时候，我们可以让数据之间的距离很紧凑，但是如果这些点的坐标稍稍有错，我们就可能搞错是哪一个点。
在有了 1 位纠错功能之后，就好像我们把一个点变成了以这个点为中心，半径为 1 的球。只要坐标在这个球的范围之内，我们都知道实际要的数据就是球心的坐标。
而各个数据球不能距离太近，不同的数据球之间要有 3 个单位的距离。
四、总结【个人总结的重点】
- 海明码：是一种纠错码。由海明发明。
- 海明码纠错能力有限：在 7-4 海明码里面，我们只能纠正某 1 位的错误。
- 海明距离理解：在有了纠错功能（1位纠错）后，不同的数据球（数据位+校验位）之间至少要有 3 个单位的距离，这样，当数据（数据位+校验位）错误时，就可以找到海明码距离最近（海明距离为1）的那个数据，即为正确要传输的数据。【理解可能有误！个人当前理解不是很透彻！】
- 海明码个人举例理解【下边用的是偶校验-（偶数个1的校验位为0）】：
- 上图错误分析，用下图规则：
- 【重点！！！】上边示例（1）分析：
传输方发送：1111 111
传输出错(比特位翻转),传成了：1111 110
接收方接收到：1111 110
接收方进行海明码校验：发现1111计算的校验码应该为111，但实际收到的是110
那么接收方认为传输出错。
根据海明码编码，发现只有一个校验码不同，那么推断，只有校验p3校验码进行了比特翻转。
最后，纠错后，得出正确的信息应该是：1111 111。
五、精选留言
