忘记前一段时间某个时候提到某个事情了，想起来纠错这回事，大概回忆了一下是一个挺有意思的过程，索性重新搜索了一下复习了一遍，把大概原理在这里写一写，权当记录
从小时候说起
小时候妈妈教导我……咳咳，打开方式不太对。
小的时候我的娱乐活动比较少，空闲时间基本上都是在看书中度过的，其中有一本书我记得很清楚，叫做《数学游戏》，里面是各种数学题，很多有趣很多有意思的题目，直到现在仍然对其中的题目印象非常深刻，还有再读一遍的冲动。
好，进入正题，这本书中有这样一个题目：
国王为10天后的生日宴会准备了1000桶酒，不幸的是，其中一桶被下了毒。为了确定哪桶是毒酒，有人提议用死刑犯试毒。毒的潜伏期为10天。问：至少需要多少个死刑犯才能确保找出毒酒？方案如何实行？
以我小学生的智力水平，书中的题目大部分都是这个难度，我也都是直接放弃看答案了，这里我们还是稍微给自己一点时间稍微思考一下：
好的！还是不会！
答案这里使用简单一点的举个例子，比如我们有八桶酒，分别编号0-7，需要几个死刑犯才能试出毒酒呢？
三个
一号罪犯喝 4 5 6 7 四桶
二号罪犯喝 2 3 6 7 四桶
三号罪犯喝 1 3 5 7 四桶
（三个罪犯都撑死了
然后用0和1代表罪犯生存或者死亡，生死和毒酒之间的关系如下
| 一号罪犯 | 二号罪犯 | 三号罪犯 | 毒桶 | 解释 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 三个罪犯都没死，0号都没喝 |
| 0 | 0 | 1 | 1 | 只有三号喝了1号 |
| 0 | 1 | 0 | 2 | 只有二号喝了2号 |
| 0 | 1 | 1 | 3 | … |
| 1 | 0 | 0 | 4 | … |
| 1 | 0 | 1 | 5 | … |
| 1 | 1 | 0 | 6 | 三号没死 1357 是好的 除此之外只有 6 号一二号都喝了 |
| 1 | 1 | 1 | 7 | 都死了，有且只有7三个罪犯都喝了 |
哇，这东西看上去好熟悉，这不就是二进制么！这样三个罪犯就可以通过这样的方法，最大检查 $2^3 = 8$ 桶酒的是否有毒。以此类推的话，1000桶酒需要 $2^{10} = 1024 > 1000$ 也就是十个罪犯来检验。done，问题解决
纠错
这个时候明眼人已经看出来了，为什么举上面这个栗子呢，这个例子实际上就是一个纠错的过程，在1000位数据中找到错误的一位数据，找到了就可以纠正这位数据，支付的代价就是对于1000位数据而言，还需要10位数据（罪犯）的状态去进行验证。
我们来看一下一般情况下的汉明码是怎么去实现的。
例如我们需要传输4个bit的数据 1101 。这里出现了第一个与上面例子不同的地方，就是我们验证的校验位也是需要随同数据一同发送出去的，校验位同样有发送错误的可能性，所以校验位也需要能够对其本身进行校验。假设需要传输的位数为 n ，校验位为 k 的话，我们需要通过这个公式来确定校验位的个数，也就是 k 的大小。
$$ 2^k >= n+k $$
so easy。这个公式的意思就是校验位总共能够校验的位数要大于数据位加上校验位之和。这样对于我们的例子而言 n = 4 ，所以 k 取3，这样校验位的位数就能够满足我们验证一位错误的需求。具体操作如下：
首先我们需要发送的总数据位数为 $n + k = 7$ 位
| 圈 | 圈 | 圈 | 圈 | 圈 | 圈 | 圈 |
|---|---|---|---|---|---|---|
| - | - | - | - | - | - | - |
（圈是占地方的
把所有2的幂次位作为校验位，也就是1、2、4、8、16这些位置，这里我们用 C 表示
| C0 | C1 | 圈 | C2 | 圈 | 圈 | 圈 |
|---|---|---|---|---|---|---|
| - | - | - | - | - | - | - |
其他位置填充数据，这里我们用D表示
| C0 | C1 | D0 | C2 | D1 | D2 | D3 |
|---|---|---|---|---|---|---|
| - | - | 1 | - | 1 | 0 | 1 |
然后我们给每一位校验位（罪犯）分配各自校验的数据位（毒酒）
这里用 A 代表整个7位数据
C0： A0 A2 A4 A6 也即 C0 D0 D1 D3
C1： A1 A2 A5 A6 也即 C1 D0 D2 D3
C2： A3 A4 A5 A6 也即 C2 D1 D2 D3
规则如下：第一位校验位校验所有能够整除2的位数，也就是二进制表示中最低位为1的。第二位校验位校验所有能够整除4的，也就是二级制表示中次低位为1的。
因为校验位同时也需要校验自己，是2的幂次，所以也可以这样表示：校验位校验与其按位求与结果为1的。
然后我们根据配偶原则，让校验位与其所校验的数据位1的个数为偶数，也即加和的最低位为0。
对于 C0 将其校验的数据，除掉自身都写出来： 1 1 1 奇 C0 取 1
同样对于 C1： 1 0 1 偶 C1 取 0
同样对于 C2： 1 0 1 偶 C2 取 0
这样拼出我们最终的总数据
| C0 | C1 | D0 | C2 | D1 | D2 | D3 |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
That‘s it！，这样我们最后传输的数据为 1 0 1 0 1 0 1 ，可以纠错的位数为1
试验
试验一下纠错，例如在数据传输的过程中有一位发生了错误 变成了 1 0 1 0 1 1 1
将其中2的幂次位的校验位对应校验的数据提出来，求其和，看奇偶
| 数据位 | 值 | 奇偶 |
|---|---|---|
| A0 A2 A4 A6 | 1 1 1 1 | 0 |
| A1 A2 A5 A6 | 0 1 1 1 | 1 |
| A3 A4 A5 A6 | 0 1 1 1 | 1 |
哇，是不是又好熟悉，和第一节中的例子一样，所以我们把这三位拼起来 1 1 0 （倒过来），二进制表示是6， 也即第六位是错误的数据位！
哇，好厉害。 这样就完成了
回顾与分析
了解了汉明码的使用和纠错的过程，我们来仔细回顾看一下其中一些细节的问题
- 汉明码纠错能力只有一位，不管数据长度是多少，根据数据长度使用对应长度的纠错码，可以校验并具备一位的纠错能力。同时可以推想，在实际应用中不适宜对太长的数据直接使用汉明码处理纠错，应该分割为小块分别使用，增加纠错能力。实际上正是因为如此，汉明码也被称为是一种线性分组码，将长数据划分为小块分别编码。
- 中间我们在确定校验位的0或1时，使用的是配偶原则。同样，存在着配奇原则，使其对应位数数据相加为奇数，实际使用中两种方法并无区别。
- 汉明码数据中所有2的幂次位置都被校验位占据，所以如果校验码中只有一位为1，其余为0的情况的话，是校验码出错，可以直接读数据，结果是正确的。如果是数据位出错的话，则校验码中至少有两位是1。
- 数据共有n位，我们至少需要k位进行校验，其满足这样的关系：
$$ 2^k >= n+k $$
- 以上说的情况的前提都是只有一位出错的情况。那么如果出现两位错误，仍然举上面的例子，我们获得的数据为 1 0 0 1 1 0 1 这种情况下：
| 数据位 | 值 | 奇偶 |
|---|---|---|
| A0 A2 A4 A6 | 1 0 1 1 | 1 |
| A1 A2 A5 A6 | 0 0 0 1 | 1 |
| A3 A4 A5 A6 | 1 1 0 1 | 1 |
可以看到仍然认为数据是错误的，但是已经不具备纠错的能力了。在普遍意义下，汉明码是能够具备2位的检测能力的，也即，知道数据有错误，但是并不具备2位的纠错能力。
除此之外，想要对汉明码进一步了解的话，可以再搜索一下这些关键字：汉明码的纠错能力和检测能力 最小码距 汉明距离
