史上最通俗的海明码编码计算、检错和纠错原理解析

下面是笔者一节视频课程中的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,同一时候也确保各位码本身不被其它校验码校验)

息码位数

1

2~4

5~11

12~26

27~57

58~120

121~247

校验码位数

2

3

4

5

6

7

8

   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。

    假设终于发现仅仅是一个校验组中的校验结果不符。则直接能够知道是相应校验组中的校验码在传输过程中出现了差错。由于所有校验码所在的位是仅仅由相应的校验码进行校验;
假设发现多组校验结果不对,则查看这些组中公共校验的数据位(仅仅有数据位才可能被几个校验码进行校验),以终于确定是哪个数据位出了差错(海明码仅仅能检查一位出错);
最后,对所找到的出错数据位取反就可以实现纠错。


三、海明码计算演示样例

原信息码:10011101

(1)确定校验码位数

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

(2)确定校验码位置

??10011101

(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



我的视频课程所有5折秒杀中。7月1号晚24点前有效!】

我的视频课程主页
http://edu.51cto.com/pack/view/id-3.html 


购终身会员。享所有课程加入本人微信公众帐号“王达大讲堂了解详情

posted @ 2017-05-23 09:53  claireyuancy  阅读(11885)  评论(0编辑  收藏  举报