教你如何计算海明码

灰太狼 2022-06-10 10:44 729阅读 0赞

以下是笔者一节视频课程中的PPT内容，细致而又非常通俗地讲解了海明码的编码计算、检测错和纠错原理，如果因为PPT比较简洁看不明白，可结合我的视频来看，本节课程的视频链接如下（**可免费观看，我全部课程5折抢购中！**）：http://edu.51cto.com/lesson/id-21540.html  
一、海明码检错/纠错基本思想  
  海明码（Hamming Code）是一个可以有多个校验位，具有检测并纠正一位错误代码的纠错码，所以也仅用于信道特性比较好的环境中，如以太局域网。它的检错、纠错基本思想如下：

（1）将有效信息按某种规律分成若干组，每组安排一个校验位通过异或运算进行校验，得出具体的校验码

（2）在接收端同样通过异或运算看各组校验结果是否正确，并观察出错的校校组，或者多个出错的校验组的共同校验位，得出具体的出错比特位

（3）对错误位取反来将其纠正  
 二、海明码计算  
  海明码计算要按以下步骤来进行：计算校验码位数→确定校验码位置→确定校验码

1. 计算校验码位数

假设用N表示添加了校验码位后整个传输信息的二进制位数，用K代表其中有效信息位数，r表示添加的校验码位数，它们之间的关系应满足：N=K＋r≤2r－1（是为了确保r位校验码能校验全部的数据位，因为r位校验码所能表示的最大十进制数为2r-1，同时也确保各位码本身不被其他校验码校验）

<table style="word-wrap:break-word; width:646pt"> 
 <tbody style="word-wrap:break-word"> 
 <tr style="word-wrap:break-word"> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 信息码位数 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 1 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 2~4 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 5~11 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 12~26 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 27~57 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 58~120 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 121~247 </td> 
 </tr> 
 <tr style="word-wrap:break-word"> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 校验码位数 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 2 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 3 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 4 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 5 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 6 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 7 </td> 
 <td style="word-wrap:break-word; margin:0px; padding:0px"> 8 </td> 
 </tr> 
 </tbody> 
</table>

2. 确定校验码位置

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

3. 确定校验码

*  校验位置选择原则：第i位校验码从当前校验码位开始，每次连续校验i位后再跳过i位，然后再连续校验i位，再跳过i位，以此类推。确定每个校验码所校验的比特位：

P1校验码位校验的码字位为：第1位（也就是P1本身）、第3位、第5位、第7位、第9位、第11位、第13位、第15位，……。

*  P2校验码位校验的码字位为：第2位（也就是P2本身）、第3位，第6位、第7位，第10位、第11位，第14位、第15位，……。
 *  P3校验码位校验的码字位为：第4位（也就是P4本身）、第5位、第6位、第7位，第12位、第13位、第14位、第15位，第20位、第21位、第22位、第23位，……。
 *  Pn校验码位校验的码字位为：第2n-1位（也就是Pn本身）、第2n-1+1位、第2n-1+2位、第2n-1+3位、……、第2n-1位，第3×2n-1位、第3×2n-1+1、……、第2×2n-1位，第5×2n-1位、第5×2n-1+1位、第3×2n-1位，……、第7×2n-1位、第7×2n-1+1位、……、第4×2n-1位，……，第(2m-1) 2n-1位、……第m×2n-1位

最后每组通过异或逻辑运算（与偶校验原理一样），使每组的运算结果为0，即可得出第i位校验码的值

4. 实现校验和纠错

把以上这些校验码所校验的位分成对应的组，则在接收端的对各校验位再进行逻辑“异或运算”，如果采用的是偶校验，正常情况下均为0。

如果最终发现只是一个校验组中的校验结果不符，则直接可以知道是对应校验组中的校验码在传输过程中出现了差错，因为所有校验码所在的位是只由对应的校验码进行校验；  
如果发现多组校验结果不正确，则查看这些组中公共校验的数据位（只有数据位才可能被几个校验码进行校验），以最终确定是哪个数据位出了差错（海明码只能检查一位出错）；  
最后，对所找到的出错数据位取反即可实现纠错。

![10659021_14040812790BuP.png][]

三、海明码计算示例

原信息码：10011101

（1）确定校验码位数

原始信息码一共8，根据前面的表可得知校验码位数为4

（2）确定校验码位置

？？1？001？1101

（2）计算机各位校验码

Pn校验码位校验的码字位为：第2n-1位（也就是Pn本身）、第2n-1+1位、第2n-1+2位、第2n-1+3位、……、第2n-1位，第3×2n-1位、第3×2n-1+1、……、第2×2n-1位，第5×2n-1位、第5×2n-1+1位、第3×2n-1位，……、第7×2n-1位、第7×2n-1+1位、……、第4×2n-1位，……，第(2m-1) 2n-1位、……第m×2n-1位  
P1(n=1):1、3、5、7、9、11   \#----检验的bit位，下同

1    1    0    1   1    0     \#----对应位的值，下同

P2(n=2):2、3、6、7、10、11

1    1     0    0   1     1

P3(n=3):4、5、6、7、12

0   0    0    1    1

P4(n=4):8、9、10、11、12

1    1    1     0      1

最终得出插入校验码后的信息码为：111000111101

[10659021_14040812790BuP.png]: http://blog.chinaunix.net/attachment/201406/30/10659021_14040812790BuP.png