汉明(海明)码编码规则和纠错原理

信息安全 TOMORROW 4个月前 (08-05) 434次浏览 2个评论 扫描二维码

汉明(海明)码是广泛采用的一种有效的校验码,它实际上是一种多重奇偶校验码。其实现原理是有效信息位中加入几个校验位形成汉明(海明)码,并把汉明(海明)码的每个二进制位分配到几个奇偶校验组中。当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现错误,还可以找到错误的位置,为自动纠错提供了依据。

汉明(海明)码的编码规则

用一个求汉明码的实例来讲述其编码的规则。

信息位数据为 1010,求其汉明码

确定汉明码的位数

设 n 为信息位的位数,k 为汉明码的位数,那么 n,k 要满足:n+k≤2^k-1

由题可知,n=4,因此可得 k=3,

信息位表示为 D4 D3 D2 D1

校验码表示为 P3 P2 P1

对应的汉明码可以表示为 H7 H6 H5 H4 H3 H2 H1

确定校验位的位置

汉明码校验位 Pi 规定在位置 2^(i-1)上,其余位为信息位:

P1 的位置为 2^(1-1)=1,即 P1 在 H1 位置上;

P2 的位置为 2^(2-1)=2,即 P2 在 H2 位置上;

P3 的位置为 2^(3-1)=4,即 P3 在 H4 位置上;

将原来的信息位按顺序插入,得到汉明码的分布如下:

汉明(海明)码编码规则和纠错原理

分组形成校验关系

每个数据位用多个校验位进行校验,但要满足:

被校验的数据位的汉明码位号=校验该数据位的各校验位汉明位号之和,且,校验位不需要再被校验。

汉明(海明)码编码规则和纠错原理

校验位取值

校验位 Pi 的值为第 i 组(由该校验位校验的数据位)所有位求异或

根据上图的分组有:

汉明(海明)码编码规则和纠错原理

所以,1010 对应的汉明码为 1010010

汉明码的校验原理

汉明(海明)码编码规则和纠错原理

 

 

 

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:汉明(海明)码编码规则和纠错原理
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
虚心的爆米花发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到
(2)个小伙伴在吐槽
  1. 数学不好的人看起来好头疼。 :!:
    cindy2018-08-05 22:31 回复 Windows 7 | Chrome 55.0.2883.87
  2. 数学不好的人看起来好头疼。 :!:
    大胆的缘分2018-08-05 22:30 回复 Windows 7 | Chrome 55.0.2883.87