海明码

海明码

海明码是一种用于错误检测和纠正的编码方法。它通过在数据中加入冗余位来检测和纠正单个位错误。

海明码的计算

假设数据为 1011

1. 确定校验位的数量
   • 设数据位长度为m, 校验位数量为r;
   • 对于一个 n 位数据，海明码通过增加 r 个冗余位，使得 m+𝑟+1≤2^𝑟。 也就是4+r+1<=2^r,算出r=3，也就是需要3个校验位
2. 插入校验位：
   • 校验位：插入在位置2^1, 2^2, 2^3
   • 所以海明码应该为：p1 p2 1 p3 0 1 1
3. 计算覆盖的位置
   每一位校验位都要负责指定数据位的偶校验，要计算每位校验位和他所负覆盖的位置，首先要记得0 - n的二进制表示，p1覆盖所有第2位的位数二进制是1的位，p2覆盖所有第2位的位数二进制是1的位,p3覆盖所有第3位的位数二进制是1的位....依此类推。以p2为例, 它需要覆盖第0010(2),0011(3),0110(6),0111(7)位的数据，其中0010(2)是它自己。
   • 2^0: 0001
   • 2^1: 0010
   • 2^2: 0011
   • 2^3: 0100
   • 2^4: 0101
   • 2^5: 0110
   • 2^6: 0111
4. 计算校验位
   • p1: 需要p1, 3, 5, 7 累加和为偶数，也就是p1+1+0+1 = 偶数， 所以p1为0
   • p2: 需要p2, 3, 6, 7 累加和为偶数，也就是p2+1+1+1 = 偶数， 所以p2为1
   • p3: 需要p3, 5, 6, 7 累加和为偶数，也就是p3+0+1+1 = 偶数， 所以p2为0
5. 得出结果
   数据1011的海明码是0110011

检查错误

对检查位以及它所对应的覆盖位进行奇偶校验，若为偶数，则证明正确

纠错

假设原始数据为1011，经过海明码编码后为0110011。收到0110111：

• 计算各检查位的偶校验：发现p1和p3错误
• 错误位置为（p1的位置+p3的位置）：1+4=5
• 翻转第5位，纠正为0110011