海明码检错与纠错，经典例子讲解~

刺骨的言语ヽ痛彻心扉 2022-12-23 15:25 239阅读 0赞

平凡也就两个字: 懒和惰;  
成功也就两个字: 苦和勤;  
优秀也就两个字: 你和我。  
跟着我从0学习JAVA、spring全家桶和linux运维等知识，带你从懵懂少年走向人生巅峰，迎娶白富美！  
关注微信公众号【**IT特靠谱**】，每天都会分享技术心得~

# 海明码纠错与检错 #

海明码（Hamming Code）是一个能够有多个校验位。具有检测并纠正一位错误数据的纠错码。

## 1 海明码理论计算 ##

假设数据位是n位，海明码的校验位是r位，则n和r必须满足关系：**2^r-1>=n+r**，为了确保r位校验码能校验所有的数据位，由于r位校验码所能表示的最大十进制数为2r-1，同一时候也确保各位码本身不被其它校验码校验，r取满足条件的最小值即可！

海明码的校验码位置：必须是在2^n次方位置（n从0 开始，分别代表从右边数起各自是第1、2、4、8、16……海明码位）。数据位也就是在非2^n次方的位置。

假设数据位为8位，校验位长度未知（假设为r位），那么 2^r-1>=8+r，可以推测出校验位长度r应该为4（满足2^4 - 1 = 15 >= 8 + 4 =12），即这个海明码长12位（8数据位 + 4校验位）。

令校验位为P3，P2，P1和P0，校验位占据的海明码位置为P0=2⁰=1，P1=2¹=2，P2=2²=4，P3=2³=8；令数据位为D7，D6，D5，D4，D3，D2，D1和D0，数据位从高往低占据海明码空余编码位。最后形成的海明码如下所示：

校验码校验的数据位对应海明码位置方法：第i位校验码从当前校验码位（包含当前校验码的位置）开始，每次连续校验i位后再跳过i位。然后再连续校验i位。再跳过i位。以此类推....

也就是说：第一组：P0校验码位校验的数据码位为：第1位（也就是P0本身）、第3位、第5位、第7位、第9位、第11位.....

第二组：P1校验码位校验的数据码位为：第2位（也就是P1本身）、第3位、第6位、第7位、第10位、第11位.....

第三组：P2校验码位校验的数据码位为：第4位（也就是P2本身）、第5位、第6位、第7位、第12位.....

第四组：P3校验码位校验的数据码位为：第8位（也就是P3本身）、第9位、第10位、第11位、第12位.....

最后每组通过异或逻辑运算。使每组的运算结果为0（偶校验），就可以得出每组校验码的值。

## 2 举例计算海明码 ##

问：已知二进制码为：10110110，求它的海明编码？

答：（1）二进制码的长度为8（即：n=8），需要满足公式：2^r - 1 >= n + r，则r值应该取4。因此将数据位（D7~D0）和校验位（P3~P0）填入如下表格：

（2）根据校验码校验的数据位方法得出：

P0校验位校验了P0、D0、D1、D3、D4、D6位 ====》P0⊕0⊕1⊕0⊕1⊕0应当满足偶数个1，因此P0=0

P1校验位校验了P1、D0、D2、D3、D5、D6位 ====》P1⊕0⊕1⊕0⊕1⊕0应当满足偶数个1，因此P1=0

P2校验位校验了P2、D1、D2、D3、D7位 ====》P2⊕1⊕1⊕0⊕1应当满足偶数个1，因此P2=1

P3校验位校验了P3、D4、D5、D6、D7 ====》P3⊕1⊕1⊕0⊕1应当满足偶数个1，因此P3=1

将得到的校验位（P3~P0）填入表格，如下：

（3）因此得到海明码为：101110111000，其中红色位为校验位的值！

（4）扩展：接收端获取到海明码后，通过相同的方式计算出P3~P0，然后与海明码对应的校验位值进行比较，只要有校验位的值不对，则数据传输出现错误，也就说明海明码具有检错能力。

## 3 举例海明码纠错 ##

依然根据上面的例子，我们将第6位（D2）的值改为0。也就是接收端接收到的海明码为：101110011000，其中黄色位为错误数据位！如何找出并纠正错误的数据位呢？

答：（1）已知海明码长度为12位，由于校验位占据2^0、2^1、2^2、2^3、2^4，.....2^n位置，可以推断出，校验位为：第1位、第2位、第4位、第8位，也就是P3~P0。剩余的位置都是数据位了（D7~D0）。分别填入下表：

（2）用上面同样的方法计算出收到的海明码的校验位值。

根据校验码校验的数据位方法得出：

P0校验位校验了P0、D0、D1、D3、D4、D6位 ====》P0⊕0⊕1⊕0⊕1⊕0应当满足偶数个1，因此P0=0

P1校验位校验了P1、D0、D2、D3、D5、D6位 ====》P1⊕0⊕0⊕0⊕1⊕0应当满足偶数个1，因此P1=1

P2校验位校验了P2、D1、D2、D3、D7位 ====》P2⊕1⊕0⊕0⊕1应当满足偶数个1，因此P2=0

P3校验位校验了P3、D4、D5、D6、D7 ====》P3⊕1⊕1⊕0⊕1应当满足偶数个1，因此P3=1

通过对比海明码的校验位值发现：P2和P1两个校验位值是错误的。首先说明了海明码在传输过程中出现了错误！然后我们要找出并纠正错误的数据位！

（3）出错位数应该是错误的校验位之和，即：P2的位置 + P1的位置 = 4 + 2 = 6位，也就是海明码的第6位数据是错的。那么我们将第6位取反，即可纠正错误！纠正后的海明码为：101110111000

（1） **商务合作微信号**：M9392W

（2） **购物商城**： **扫码即可进入博主开发的****小程序购物商城****，享超大优惠购物，支持一下博主吧~**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUX01vc3Q_size_16_color_FFFFFF_t_70][]

（3） **博主微信公众号**：**IT特靠谱**，学习更多开发实战技巧！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUX01vc3Q_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUX01vc3Q_size_16_color_FFFFFF_t_70]: /images/20221120/2172b8f2cf4e4393867150320a7a6f1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUX01vc3Q_size_16_color_FFFFFF_t_70 1]: /images/20221120/61ada1bbd96a4ded9429e9fe60115e1d.png