计算机知识回顾：海明码
2017-04-16 本文已影响196人
Angels_安杰
- 海明码，又名汉明码，是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。海明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于海明编码简单，它们被广泛应用于内存（RAM）。
校验原理：
- 错误校验码有多种，海明码也利用了奇偶校验位的概念，通过在数据位后面增加一定的比特，可以验证数据的有效性。利用一个以上的校验位，海明码不仅可以验证数据是否有效，还能在数据出错的情况下校验得出错误的明确位置。
注：奇偶校验概念补充：
- 偶校验：如果给定的数据1的个数是奇数，那么偶校验位为1，使数据的1保持偶数，否则位0；
- 奇校验：如果给定的数据1的个数是偶数，那么奇校验位为1，使数据的1保持奇数，否则为0；
- 奇偶校验的选择都是事先规定的。
- 优点：开销低，只需要增加1为比特就可以得出数据的正确性，但是不能得出出错的数据位置，即不能矫正，只能丢弃重发，而且数据也有可能两个比特同时出错，此时奇偶校验可能是检测不出来的，但在普通微型计算机中这个概率是微乎其微的。
纠错原理：(来自http://bbs.51cto.com/thread-889899-1.html)写的很好。
假设要传输的数据是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:校验码位数；
