海明码 可以 发现 双比特错误 , 但只能纠正 单比特错误 ;
海明码 工作原理 :
① 添加校验码 : 发送数据 , 在数据中加入 冗余信息 ( 冗余码 / 校验码 ) ;
② 校验码作用 : 每个 校验码 不仅可以校验本身的信息 , 还可以同时校验多为信息 ;
③ 比特位 多重校验 : 某些 比特位 可以 同时被多个校验码校验 ;
④ 检查差错 : 如果这个被多位校验码校验的比特位 出现错误 , 那么多个校验码校验时 , 就会知道数据 出现差错 ;
⑤ 定位差错 : 每个校验码逐个校验 , 最终能 定位出是哪个比特位出现了差错 , 从而将其纠正 ;
"海明码" 工作流程 :
海明不等式 :
是冗余信息位
是信息位
根据信息位位数 , 求出满足 海明不等式 最小的 r ;
确定校验码位数示例 : 发送数据
, 求海明码位数 ;
① 数据位数 :
;
② 将数据位数代入海明不等式 :
③ 满足海明不等式最小
计算 :
, 依次从
开始代入 , 获取满足不等式最小的
的值为
;
④ 发送数据 : 发送的数据 海明码 是
位 , 其中 原始数据有
位 , 校验码有
位 ;
确定校验码和数据位置 : 发送数据
, 海明码位数 为
位 ;
① 校验码
位 :
,
,
,
;
② 数据位
位 :
,
,
,
,
,
;
③ 校验码位置 : 校验码 只能放在
的幂次方位置 , 如
,
,
,
,
等位置 ;
④ 数据位置 : 数据位 按照顺序依次 放在 非校验码位置上 ;
⑤ 最终生成的数据位 :
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 P_1 P1 | P 2 P_2 P2 | 1 1 1 | P 3 P_3 P3 | 0 0 0 | 1 1 1 | 1 1 1 | P 4 P_4 P4 | 0 0 0 | 1 1 1 |
实际值
求校验码值 :
在表格中引入二进制位 : 二进制的位数 就是 以 能代表 最大的序列索引的位数为准 , 如 该 数据 有
位 , 最大索引值是
, 对应二进制时
, 需要
位二进制数表示 , 这里的二进制位数是
;
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 P_1 P1 | P 2 P_2 P2 | 1 1 1 | P 3 P_3 P3 | 0 0 0 | 1 1 1 | 1 1 1 | P 4 P_4 P4 | 0 0 0 | 1 1 1 |
实际值
校验的位 计算 :
对应的二进制位是
, 第一位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
令所有要校验的位 异或 (
) 计算后为
;
异或计算
: 同
, 异
, 两个位不同时为
, 两个位相同时为
;
才能使上述式子成立 , 因此 校验位
;
校验的位 计算 :
对应的二进制位是
, 第二位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
才能使上述式子成立 , 因此 校验位
;
校验的位 计算 :
对应的二进制位是
, 第
位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
才能使上述式子成立 , 因此 校验位
;
校验的位 计算 :
对应的二进制位是
, 第
位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
才能使上述式子成立 , 因此 校验位
;
计算出的四个校验码 :
将上述校验码填写到表格中 :
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 = 0 P_1 = 0 P1=0 | P 2 = 0 P_2 = 0 P2=0 | 1 1 1 | P 3 = 0 P_3=0 P3=0 | 0 0 0 | 1 1 1 | 1 1 1 | P 4 = 1 P_4=1 P4=1 | 0 0 0 | 1 1 1 |
实际值
最终海明码为 :
, 蓝色是数据位 , 红色是校验位 ;
发送的正确的海明码数据是 :
, 蓝色是数据位 , 红色是校验位 ;
海明码数据表格是 :
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 = 0 P_1 = 0 P1=0 | P 2 = 0 P_2 = 0 P2=0 | 1 1 1 | P 3 = 0 P_3=0 P3=0 | 0 0 0 | 1 1 1 | 1 1 1 | P 4 = 1 P_4=1 P4=1 | 0 0 0 | 1 1 1 |
实际值
假设 海明码 第
位出现错误 ,
数据原来是
, 出现错误变成
;
正确海明码 :
错误海明码 :
, 第
位 的
变成了
;
检错过程 :
个检验位 , 每个检验位 , 令所有要校验的位进行异或
运算 ;
错误海明码数据表格是 :
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 = 0 P_1 = 0 P1=0 | P 2 = 0 P_2 = 0 P2=0 | 1 1 1 | P 3 = 0 P_3=0 P3=0 | 1 1 1( 错误位 ) | 1 1 1 | 1 1 1 | P 4 = 1 P_4=1 P4=1 | 0 0 0 | 1 1 1 |
实际值
( 错误位 )
校验的位 计算 :
对应的二进制位是
, 第一位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第一位是
, 红色部分 ; 对应数据位
位 , 值为
;
令所有要校验的数据位 和 校验位 , 异或 (
) 计算后为
;
异或计算
: 同
, 异
, 两个位不同时为
, 两个位相同时为
;
校验位 校验出错 ;
位中 , 有错误出现 ;
校验的位 计算 :
对应的二进制位是
, 第二位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
校验位 校验正确 ;
位数据正确 ;
校验的位 计算 :
对应的二进制位是
, 第
位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
校验位 校验出错 ;
位中 , 有错误出现 ;
校验的位 计算 :
对应的二进制位是
, 第
位是
, 查看 哪些 二进制位 的数据位 第
位是
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
:
, 二进制的第
位是
, 红色部分 ; 对应数据位
位 , 值为
;
校验位 校验正确 ;
位数据正确 ;
校验结果 :
校验位 校验出错 ;
位中 , 有错误出现 ;
校验位 校验正确 ;
位数据正确 ;
校验位 校验出错 ;
位中 , 有错误出现 ;
校验位 校验正确 ;
位数据正确 ;
综合上面
次校验结果 , 发现
数据错误 , 将下面的表格中的
错误纠正 , 由
纠正成
即可 ;
错误海明码数据表格是 :
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 = 0 P_1 = 0 P1=0 | P 2 = 0 P_2 = 0 P2=0 | 1 1 1 | P 3 = 0 P_3=0 P3=0 | 1 1 1( 错误位 ) | 1 1 1 | 1 1 1 | P 4 = 1 P_4=1 P4=1 | 0 0 0 | 1 1 1 |
实际值
( 错误位 )
正确海明码数据表格是 :
二进制位 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
---|---|---|---|---|---|---|---|---|---|---|
数据位索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
名称 | P 1 P_1 P1 | P 2 P_2 P2 | D 1 D_1 D1 | P 3 P_3 P3 | D 2 D_2 D2 | D 3 D_3 D3 | D 4 D_4 D4 | P 4 P_4 P4 | D 5 D_5 D5 | D 6 D_6 D6 |
实际值 | P 1 = 0 P_1 = 0 P1=0 | P 2 = 0 P_2 = 0 P2=0 | 1 1 1 | P 3 = 0 P_3=0 P3=0 | 0 0 0( 纠错后的结果 ) | 1 1 1 | 1 1 1 | P 4 = 1 P_4=1 P4=1 | 0 0 0 | 1 1 1 |
实际值
( 纠错后的结果 )
最终将错误的海明码
( 第
位 的
变成了
) , 纠正 为 正确的海明码
;