概述
文章目录
- 汉明码(海明码)
- 为什么有汉明码?
- 分组校验
- 汉明码的原理
- 添加检测位数
- 检测位置
- 分组原理
- 如何编码?
- 检测取值
- 如何校验?
汉明码(海明码)
为什么有汉明码?
在计算机存储中,可能受其它原因,导致存储出现错误,0变成1,1变成0,存放数据以汉明码的方式存储,可以进行数据的校正,具有一位纠错能力。
分组校验
在介绍汉明码之前举一个例子说明一下分组校验:比如有一个字节的数据 1000 0101
黄色为检验位
数据 | 说明 |
---|---|
1 1010 0001 | 该数据1的个数为奇数,则可以得知1010 0001里面某一位出现错误 |
01010 1 0001 | 该数据1的个数为奇数,则可以得知1010 或0001里面某一位出现错误 |
从表格中可以看出如果添加的检测位越多可以找到出错的范围越精确,当然这种分组校验组和组之间是不重复的,而海明码的组和组之间是重复的,很巧妙的重复能够精确的找到哪一位出现了错误。
汉明码的原理
将要进行检测的二进制代码为n位,为使其具有纠错能力,需要再加上k位的检测位,组成n+k位的代码。那么,新增加的检测位数k应满足:2k≥n+k+1
添加检测位数
2
k
⩾
n
+
k
+
1
2^k geqslant n+k+1
2k⩾n+k+1
比如:二进制数据有4位 1011匿名检测位需要3位,因为23 = 4+3+1
检测位置
位
置
序
号
=
2
i
(
i
=
0
,
1
,
2
,
3
,
4
,
.
.
.
)
位置序号=2^i(i=0,1,2,3,4,...)
位置序号=2i(i=0,1,2,3,4,...)
如果有3个检测位,参考下面表格
位置序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
二进制数据 | 1 | 0 | 1 | 1 | |||
说明 | 检测位 | 检测位 | 数据位 | 检测位 | 数据位 | 数据位 | 数据位 |
分组原理
3个检测位,每个检测位划分一个组,第1组有1,3,5,7位;第2组有2,3,6,7位;第3组有4,5,6,7位。
位置序号 | 用2i (i=0,1,2)分解 | 包含二进制形式 | 所属组 |
---|---|---|---|
3 | 1+2 | xx1,x1x | 1,2 |
5 | 1+4 | xx1,1xx | 1,3 |
6 | 2+4 | x1x,1xx | 2,3 |
7 | 1+2+4 | xx1,x1x,1xx | 1,2,3 |
分组 | 检测位序号 | 二进制形式 | 转换成十进制的位置序号 |
---|---|---|---|
1 | 1(20) | xx1 | 1,3,5,7 |
2 | 2(21) | x1x | 2,3,6,7 |
3 | 4(22) | 1xx | 3,5,6,7 |
… | … | … | … |
如何编码?
检测取值
检测位的取值和该位所在的检测组的奇偶校验方式有关。
- 偶校验:该检测组的1的个数(不包括检测位)为偶数时,检测位为0,为奇数时检测位为1
- 奇校验:该检测组的1的个数(不包括检测位)为偶数时,检测位为1,为奇数时检测位为0
偶校验
位置序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
二进制数据 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
说明 | 检测位 | 检测位 | 数据位 | 检测位 | 数据位 | 数据位 | 数据位 |
奇校验
位置序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
二进制数据 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
说明 | 检测位 | 检测位 | 数据位 | 检测位 | 数据位 | 数据位 | 数据位 |
如何校验?
给出一段7位奇校验海明码,在上面数据基础上把6号位的1变为0
位置序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
二进制数据 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
说明 | 检测位 | 检测位 | 数据位 | 检测位 | 数据位 | 数据位 | 数据位 |
开始校验
位置 | 相应检测位和数据位 | 1的个数(包含检测位) | 结果 |
---|---|---|---|
p4 | 4,5,6,7 | 2(偶) | 1 |
p2 | 2,3,6,7 | 2(偶) | 1 |
p1 | 1,3,5,7 | 3(奇) | 0 |
把位置从大到小排列并写出相应的结果 110 转换成10进制就是6,所以6号位置的数据出错,不同的结果以此类推。
注意:
把3个位置从大到小排列并写出相应的结果
在校验过程中,可以有3种判断方法:
1.查找相应检测位和数据位1的个数找奇偶,如果个数为偶,在偶校验里面为0,奇校验中为1;如果个数为奇,在偶校验里面为1,奇校验中为0
2.直接相加相应检测位和数据位看数值的奇偶,如果个数为偶,在偶校验里面为0,奇校验中为1;如果个数为奇,在偶校验里面为1,奇校验中为0
3.相应检测位和数据位进行异或运算,偶校验直接是异或运算结果,奇校验还要对结果取反。
最后
以上就是精明豌豆为你收集整理的汉明码(海明码)你了解多少?带你探秘背后秘密汉明码(海明码)的全部内容,希望文章能够帮你解决汉明码(海明码)你了解多少?带你探秘背后秘密汉明码(海明码)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复