1. 简介
汉明校验码又名海明码。作用是在一定程度上能校验是否有传输出错，如果仅有一位出错，还能纠错。
2. 需求
对于原信息串一共 \(k\) 位，内容为: \([A_k,A_{k-1},A_{k-2},…,,A_{1}]\) ,且为二进制，每一位非 0 则 1 .
先考虑最简单的情况集：S={仅某一位出错，都没出错}
- 如果没出错能基于校验码得知没出错
- 如果出错能基于校验码发现是哪一位出错，并纠错（当情况集仅限于S）
3. 要求
要做到上述两点我们需要多少比特的信息呢？
很简单，数一下有多少种状态再取 \(log_2\) 即可。没有出错为 \(1\) 个状态，每一位分别出错，一共 \(k\) 个状态，总计 \(1+k\) 个状态，那至少需要 \(log_2(1+k)\) 位额外的验证位才可能承载这样的需求。
而且当引入了额外验证位后，通常要把验证位本身出错的情况也考虑进去。假设最后使用了 \(m\) 位验证位。则
\begin{align}
m \geq log_2(1+k+m)
\end{align}
整理一下，得到
\begin{align}
2^m – m \geq 1 + k
\end{align}
即可以以此考察 \(m\) 最低的要求。
3. 计算方式
如何用 \(log_2 (k+m+1)\) 的二进制位去指针哪一位有问题呢？
借鉴10头猪的试1000瓶毒药问题，我们或许可以使用二进制的思路：一个目标位会影响多个结果位，且影响方式尽可能正交。
其实最简单的就是二进制编码。
假设传输的信息是 111111 ,但第 5 位传输错误，希望能配合校验码通过一个运算得到 “(前面m-3个零)101” ，即二进制的 5 即能指示出出错的位。
但与此同时别忘了还有一个重要状态是 “都没出错” 。好在我们如果下标编号是从 1 开始，则可以令为 0 的结果代表正确。
由此，需求被进一步细化为
- 正确的情况下，可以通过一个校验运算，输入获得的信息，得到 0
- 有一位错误的情况下，可以通过同种校验运算，得到错误的位置
那怎么做到这一点呢？
继续借鉴10头猪的试1000瓶毒药的问题。毒药问题中，有毒和无毒是两种绝对的状态，所以可以用绝对的 0 和 1 进行表示，于是可以直接构建二进制。
而在这里，结果并非绝对的 0 和 1 ，而是相对于初始值是否相异的问题。
有什么运算能帮我们判断相异呢？巧了～那就是“异或”
同时异或还有一个很好的性质：
- 不仅可以判断两个位是否相同。如果把 n 个位相继异或运算得到的值，和任意一位取反后的值刚好相反。
（哈哈哈，是不是有点像逆序数的奇偶性）
基于此可以照搬毒药的方式生成校验码序列,假设 \(m\) 位汉明码序列为:
\begin{align}
[A_{k+m},A_{k-1+m},A_{k-2+m},…,,A_{1+m},V_m,V_{m-1},V_{m-2},…,,V_{1}]
\end{align}
则 \(V_i\) = 按序异或(所有序号二进制第 i 位为 1 的位)
这样似乎就可以在获取信息后用相反的方式按异或得到理论校验码，并且再和接受的校验码异或得到 0（正确）或者 x （第x位错误）
但事实上这样还有问题：
- 计算一个校验码位时，可能运算内容参杂了其他校验码位，比如在计算 第 2 位校验码时，需考虑第 7 位（如果存在）校验码的值，那到底应该先计算谁呢？会互锁吗？
- 事实上上个问题还是小问题，更重要的是当得到一个校验码的值为 100 (m=3)，那到底是第三位校验码出错还是第四位信息位出错呢？这产生了歧异。
当然，解决方法并不困难，即把校验码的 \(V_i\) 放在整个序列的第 \(2^i\) 位置，使 0010、0100、1000、0001 等等都刚好指向自己。这样消除了歧异。且在计算时不会相互交叉。
于是便得到了汉明码。
\begin{align}
[…A_5,V_4,A_4,A_3,A_2,V_3,A_1,V_2,V_{1}]
\end{align}
4. 示例
4.1 计算汉明码
比如我们有一个信息长为 4 内容为”1010″，需要求其汉明码。
首先确定校验码需要的位数，根据
\begin{align}
2^m \geq 1+k+m
\end{align}
将 \(k = 4\) 代入，可以发现满足条件的 \(m\) 最小的正整数为 \(3\)
于是结果的形式应为：\([1,0,1,V_3,0,V_2,V_1]\)
再求每一位校验码，根据\(V_i\) = 按序异或(所有序号二进制第 i 位为 1 的位)
\begin{align}
V_1 &= 1 xor 1 xor 0 = 0 \\
V_2 &= 1 xor 0 xor 0 = 1\\
V_3 &= 1 xor 1 xor 1= 1
\end{align}
于是得到汉明码 \([1,0,1,1,0,1,0]\)
4.2 纠错示例
如果我们在传输汉明码 \([1,0,1,1,0,1,0]\) 时，第 3 位传错了，获得 \([1,0,1,1,1,1,0]\) ，则接收方重新计算
\begin{align}
V_1 &= 1 xor 1 xor 1 = 1 \\
V_2 &= 1 xor 0 xor 1 = 0 \\
V_3 &= 1 xor 1 xor 1= 1
\end{align}
将计算得到的校验序列 101 与接受的校验序列 110 取异或，得到011，即十进制的3，即第 3 位有问题。
4.3 多位出错
如果有多位传输出错会有什么情况呢，比如两位出错，使 \([1,0,1,1,0,1,0]\) 传错为 \([1,0,1,1,1,1,1]\)，计算后得到 010 ，这显然不能再用于纠错，但依旧可以根据其不等于 0 得知有错。
再尝试多出错一位，使 \([1,0,1,1,0,1,0]\) 传错为 \([1,0,1,1,1,0,1]\)，得到 000 ，则是否错误的信息也无法判断了。
由此可知这样的方式产生的汉明码仅足够一位的纠错，如果要更多位则需要其他方式增强。
5. 全校验
当
\begin{align}
2^k-k>n+1
\end{align}
时，由于信息还有富余，可以选在首部再加一位全校验位，值等于后续所有位的异或结果。进一步增强识别能力。
6. 参考资料
https://www.zhihu.com/question/29169628/answer/837787585