计算机知识回顾：海明码

• 海明码，又名汉明码，是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。海明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于海明编码简单，它们被广泛应用于内存（RAM）。

校验原理：

• 错误校验码有多种，海明码也利用了奇偶校验位的概念，通过在数据位后面增加一定的比特，可以验证数据的有效性。利用一个以上的校验位，海明码不仅可以验证数据是否有效，还能在数据出错的情况下校验得出错误的明确位置。

  注：奇偶校验概念补充：

  • 偶校验：如果给定的数据 1 的个数是奇数，那么偶校验位为 1，使数据的 1 保持偶数，否则位 0；
  • 奇校验：如果给定的数据 1 的个数是偶数，那么奇校验位为 1，使数据的 1 保持奇数，否则为 0；
  • 奇偶校验的选择都是事先规定的。
  • 优点：开销低，只需要增加 1 为比特就可以得出数据的正确性，但是不能得出出错的数据位置，即不能矫正，只能丢弃重发，而且数据也有可能两个比特同时出错，此时奇偶校验可能是检测不出来的，但在普通微型计算机中这个概率是微乎其微的。

纠错原理：(来自 http://bbs.51cto.com/thread-889899-1.html)写的很好。%E5%86%99%E7%9A%84%E5%BE%88%E5%A5%BD%E3%80%82)

假设要传输的数据是 a4a3a2a1，数据位长度为 4 位，设校验位长度为 m，那么应该满足 2m-1>=m+4。解出，m=3。这个不等式要解释吗？好吧，我给大家解释下，校验位为 m 位，那么，校验码可以表示的最大十进制数字为 2m-1，去掉一位的原因是全 0 表示传输的数据没有错误！校验码表示能够纠正的二进制数字位数，为了保证能够纠正数据位最高位。那么 2m-1 至少应该大于等于数据位和校验位长度的总和！好了，设校验码为 r3r2r1。根据海明码规定，校验位应放在数据位的 2i-1 的位置，整理好后设为 M7M6M5M4M3M2M1。
好了，最后的问题，怎么计算校验码呢？它怎么纠错呢？这里我们设海明码的监督关系式为 S3S2S1。请大家仔细想一想，S1 是不是代表三位二进制校验码的最低位，让我们看看有多少位数字参与了 S1 的运算，很容易看出 M1、M3、M5、M7，所以 S1=M1⊕M3⊕M5⊕
M7（为什么是这样呢？这里也给大家说明一下。我们看 M 的下标，它代表什么呢？明白吗？它代表的是数字在传输数据的第几位。7=4+2+1,5=4+1,3=2+1,1=1。可见，这几位数字均参与了第一位的运算，这样，S1=1 就能代表数据位的第一位出错了！），同理，S2=M2⊕M3⊕M6⊕M7，S3=M4⊕M5⊕M6⊕M7。我们再来看这三个监督关系式上面我们说到，要想数据位没有错误，S3S2S1=000，通过这可以计算出 r3r2r1，因为 S1=0，根据异或运算，将 M3⊕M5⊕M7 看作一个整体，M1=M3⊕M5⊕M7，r1=M1。同理可以计算出 r2r1。那么纠错到底是怎么实现的呢？请大家睁大眼睛仔细看上面三个监督表达式。正常情况下，S3S2S1 均为 0，我们假设 M3 出现了错误，发生了跳变，那么 S2S1 将变成什么呢？如果你不知道的话请往回去看看我说的关于异或运算的知识。由上面的监督关系式发现 M3 参与了 S2S1 的运算，所以在 M3 发生跳变的情况下 S2S1 也将发生跳变，由 0 变为 1，但由于 S3 未参与 M3 的运算，其值不变，仍为 0。所以监督关系式 S3S2S1=011=3，所以在传输数据的第三位出现了错误。同理，可发现 M6 参与了 S3S2 的运算，当运算出错时，监督关系式为 110=6，也刚好可以判断出是传输数据的第六位出错了。其它的数据位我就不一一举例了

小结：

N=K＋r≤2^r－1

• N:包含校验码的数据总位数；
• K:数据位数；
• r:校验码位数；