总结一下Hamming距离，奇偶校验码，Hamming码的知识

主要参考：《计算机网络》——Tanenbaum

Hamming码

在数据链路层的差错控制中，为了使接收方能够有一定程度的对传输的检错或纠错能力，并不是直接传输原始的位串，而是需要采用一些特殊的编码方式，传输经过编码后的信息。编码，就是将原本需要传输的位串增加一些冗余位，构成一个新的位串。

Hamming距离

一个编码方案的检错和纠错能力，和编码方案Hamming距离有关，以下先定义位串的Hamming距离和编码方案的Hamming距离。

位串的Hamming距离：两个相同位数的位串中不同位的个数称为Hamming距离

编码方案的Hamming距离：设\(X\)是一个编码方案，\(Y\subset X\)是原本需要传输的原始位串经过编码后形成的合法位串的集合，\(Y\)中两个不同位串的最小Hamming距离称为\(X\)的Hamming距离

下面两个定理给出了编码方案的Hamming距离和检错纠错能力的关系。

定理1：在一个至多出现\(d\)个错误的传输中，至少需要一个Hamming距离为\(d+1\)的编码方案，才能保证接收方检查出传输错误

证明：\(d\)个错误至多使一个合法位串变成另一个和它Hamming距离不超过\(d\)的，错误位串，但Hamming距离为\(d+1\)的编码方案中，任意两个合法位串的Hamming距离\(\ge d+1\)，因此可以检查出来这个传输错误的位串不合法。

定理2：在一个至多出现\(d\)个错误的传输中，至少需要一个Hamming距离为\(2d+1\)的编码方案，才能保证接收方纠正传输错误

证明：\(d\)个错误至多使一个合法位串变成另一个和它Hamming距离不超过d的错误位串，这样能保证错误位串与其他的合法位串的Hamming距离\(\ge d+1\)，但与原位串的Hamming距离\(\le d\)，接收方只需在合法位串中找到与该错误位串Hamming距离最小的合法位串，就可以纠正错误。

• 注：Hamming距离也可以用异或运算来定义，即两个位串异或得到的新位串再按位求和
• 这里挖个坑：Hamming距离应该是定义在\(\{0,1\}^n\)上的一个距离

奇偶校验码

最简单的具有检错能力的编码方案，就是能够检查至多1位错误的编码方案，下面将看到，奇偶校验码就是这样的编码方案。

奇偶校验码：对一个原始位串增加一位冗余位，使得新位串中1的个数是(奇)偶数，这种编码称为奇偶校验码。

定理3：奇偶校验码是一种能检查至多1位错误的编码方案

证明：由定理1，只需证明奇偶校验码的Hamming距离\(\ge 2\)即可。任取两个不同的合法位串，假设其Hamming距离为1，说明这两个位串中的第\(k\)位一个是0，一个是1。

• Case1：第\(k\)位是冗余位。则这两个位串的消息位相同，按奇偶校验码的定义，消息位相同冗余位也必定相同，矛盾。

• Case2：第\(k\)位不是冗余位。则这两个位串中1的总个数不相同，其冗余位必定也不相同，这样这两个合法位串的Hamming距离是2，矛盾。

这说明不存在Hamming距离为1的两个合法位串，所以奇偶校验码的Hamming距离\(\ge 2\)。

Hamming码

最简单的具有纠错能力的编码方案，就是能够纠正至多1位错误的编码方案，Hamming码是基于奇偶校验码提出的，它在原\(m\)位消息位上增加了\(r\)个冗余位，编码后的位串一共有\(n=m+r\)位，下面将证明，Hamming码能够纠正至多1位错误。

可想而知，一个编码方案的冗余位越多，其Hamming距离应该越大，但冗余位越多传输消息的效率就越低，所以应当使用尽可能少的冗余位。

定理4：若消息位的位数为\(m\)，一个\(r\)位冗余位的能纠正至多1位错误的编码方案，需要满足以下不等式， \[ m+r+1\le 2^r\]

这个定理实际上给出了能纠正至多1位错误的编码方案所需要的冗余位的下界

证明：\(m\)位的消息位总共可表达\(2^m\)条消息，每条消息经过编码后对应了编码方案中的\(2^m\)个位串。每个经过编码后的正确位串是\(n\)位，一个正确位串出现\(1\)位错误后产生的错误位串有\(n\)个，因此这个编码方案应该包括\(2^m\)个正确位串，以及\(n\times 2^m\)个错误位串。 两个不同的消息所对应的正确位串一定是不同的，而且错误位串也不能够有相同，否则就存在一个位串和两个正确的位串Hamming距离都是1，这个位串就无法纠错了。 \(n\)位的编码总共有\(2^n\)个位串，所以有\((n+1)2^m\le 2^n\)，带入\(n=m+r\)整理即可得到不等式$ m+r+1^r$。

• 注1：同样的思路可以给出能纠正至多\(k\)位错误的编码方案的冗余位下界
• 注2：对于检错码，检查至多\(1\)位错误只需要\(1\)位冗余位，奇偶校验码就是一个构造性的证明
• 这里再挖个坑：检查至多\(k\)位错需要多少位冗余位，暂时没想到

Hamming码：(下标从1开始，下标都用二进制表示)下标只有一个\(1\)的位是冗余位，其他是消息位。若消息位的下标中第\(k\)个位是\(1\)，则该消息位属于第\(k\)组。第\(k\)个冗余位的值要使第\(k\)组中\(1\)的个数为偶数，换句话说第\(k\)个冗余位就是第\(k\)组的奇偶校验位。

Hamming码的描述有些绕，下面给出一个具体例子。

例：(11,7)Hamming码 原7位消息为1000001，每位分别记为m1,m2,m3,m4,m5,m6,m7 采用11位的Hamming码，其中第0001，0010，0100，1000位是校验位，每位分别记为P1,P2,P3,P4。其他位按顺序插入消息位。

先分组：m1位实际上是第0011位，因此属于0001组和0010组，m2位是第0101位，属于0001组和0100组。依次类推将消息位分好组。

求校验码的值：属于0010组的有第0010，0011，0110，0111，1010，1011位，也就是P2,m1,m2,m3,m4,m6,m7，使组1的个数为偶数可算出P2为0，以此类推算出其他校验位的值，可得到编码后的位串是10111001001 下标 1 2 3 4 5 6 7 8 9 10 11 P1 P2 m1 P3 m2 m3 m4 P4 m5 m6 m7 值 1 0 1 1 1 0 0 1 0 0 1

纠错方法：假设m5因为传输错误变成1，计算各组可发现0001组和1000组中1的个数不是偶数，这说明同时属于0001组和1000组的位(也就是m5)传输错误，将其取反就可恢复到正确的消息。

• 注：Hamming码也可用整数拆分的语言来描述，实际上是一回事

定理5：Hamming码的Hamming距离\(\ge 3\)

证明：只需证明不存在Hamming距离为\(1\)和\(2\)的两个正确位串即可。 由于每个消息位至少属于两组，如果两个正确位串只有\(1\)位数据位不同，必定导致两个校验码不同，Hamming距离为3。如果两个正确位串只有\(1\)位校验码不同，必定有其一不符合Hamming码的编码规则。因此不存在Hamming距离为\(1\)的正确位串。分类讨论还可以证明其他情况。

这说明Hamming码确实可以纠正至多\(1\)位错误的传输