文章目录

一、 "海明码" 工作原理
二、 "海明码" 工作流程
三、确定校验码位数
四、确定校验码和数据位置

0、确定校验码位置
1、引入二进制位
2、 P1 校验位计算
3、 P2 校验位计算
4、 P3 校验位计算
5、 P4 校验位计算
6、最终海明码结果

五、检错纠错

1、 P1 校验位校验
2、 P2 校验位校验
3、 P3 校验位校验
4、 P4 校验位校验
5、纠错

一、 “海明码” 工作原理

海明码 可以发现双比特错误 , 但只能纠正单比特错误 ;

海明码工作原理 :

① 添加校验码 : 发送数据 , 在数据中加入冗余信息 ( 冗余码 / 校验码 ) ;

② 校验码作用 : 每个校验码不仅可以校验本身的信息 , 还可以同时校验多为信息 ;

③ 比特位多重校验 : 某些比特位可以同时被多个校验码校验 ;

④ 检查差错 : 如果这个被多位校验码校验的比特位出现错误 , 那么多个校验码校验时 , 就会知道数据出现差错 ;

⑤ 定位差错 : 每个校验码逐个校验 , 最终能定位出是哪个比特位出现了差错 , 从而将其纠正 ;

二、 “海明码” 工作流程

"海明码" 工作流程 :

确定校验码位数
确定校验码位置和数据位置
求校验码值
检错纠错

三、确定校验码位数

海明不等式 : $2^r \geq k+r+1$

$r$ 是冗余信息位
$k$ 是信息位

根据信息位位数 , 求出满足海明不等式最小的 r ;

确定校验码位数示例 : 发送数据 $101101$ , 求海明码位数 ;

① 数据位数 : $k = 6$ ;

② 将数据位数代入海明不等式 : $2^r \geq 6+r+1$

③ 满足海明不等式最小 $r$ 计算 : $2^r \geq 7+r$ , 依次从 $1$ 开始代入 , 获取满足不等式最小的 $r$ 的值为 $4$ ;

④ 发送数据 : 发送的数据海明码是 $10$ 位 , 其中原始数据有 $6$ 位 , 校验码有 $4$ 位 ;

四、确定校验码和数据位置

0、确定校验码位置

确定校验码和数据位置 : 发送数据 $101101$ , 海明码位数为 $10$ 位 ;

① 校验码 $4$ 位 : $P_1$ , $P_2$ , $P_3$ , $P_4$ ;

② 数据位 $6$ 位 : $D_1$ , $D_2$ , $D_3$ , $D_4$ , $D_5$ , $D_6$ ;

③ 校验码位置 : 校验码只能放在 $2$ 的幂次方位置 , 如 $2^0 = 1$ , $2^1 = 2$ , $2^2 = 4$ , $2^3 =8$ , $2^n$ 等位置 ;

④ 数据位置 : 数据位按照顺序依次放在非校验码位置上 ;

⑤ 最终生成的数据位 :

数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1$	$P_2$	$1$	$P_3$	$0$	$1$	$1$	$P_4$	$0$	$1$

1、引入二进制位

求校验码值 :

在表格中引入二进制位 : 二进制的位数就是以能代表最大的序列索引的位数为准 , 如该数据有 $10$ 位 , 最大索引值是 $10$ , 对应二进制时 $1010$ , 需要 $4$ 位二进制数表示 , 这里的二进制位数是 $4$ ;

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1$	$P_2$	$1$	$P_3$	$0$	$1$	$1$	$P_4$	$0$	$1$

2、 P1 校验位计算

$P_1$ 校验的位计算 : $P_1$ 对应的二进制位是 $0001$ , 第一位是 $1$ , 查看哪些二进制位的数据位第 $1$ 位是 $1$ ;

数据位索引 $3$ : $001$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_1$ 位 , 值为 $1$ ;
数据位索引 $5$ : $010$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_2$ 位 , 值为 $0$ ;
数据位索引 $7$ : $011$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;
数据位索引 $9$ : $100$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_5$ 位 , 值为 $0$ ;

令所有要校验的位异或 ( $\oplus$ ) 计算后为 $0$ ;

异或计算 $\oplus$ : 同 $0$ , 异 $1$ , 两个位不同时为 $1$ , 两个位相同时为 $0$ ;

$\begin{array}{lcl}D_1 \oplus D_2 \oplus D_4 \oplus D_5 \oplus P_1 &=& 0 \\\\ 1 \oplus 0 \oplus 1 \oplus 0 \oplus P_1 &=& 0 \\\\ 1 \oplus 1 \oplus 0 \oplus P_1 &=& 0 \\\\ 0 \oplus 0 \oplus P_1 &=& 0 \\\\ 0 \oplus P_1 &=& 0 \end{array}$

$P_1 = 0$ 才能使上述式子成立 , 因此校验位 $P_1 = 0$ ;

3、 P2 校验位计算

$P_2$ 校验的位计算 : $P_2$ 对应的二进制位是 $0010$ , 第二位是 $1$ , 查看哪些二进制位的数据位第 $2$ 位是 $1$ ;

数据位索引 $3$ : $00$ $1$ $1$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_1$ 位 , 值为 $1$ ;
数据位索引 $6$ : $01$ $1$ $0$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_3$ 位 , 值为 $1$ ;
数据位索引 $7$ : $01$ $1$ $1$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;
数据位索引 $10$ : $10$ $1$ $0$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_6$ 位 , 值为 $1$ ;

$\begin{array}{lcl}D_1 \oplus D_3 \oplus D_4 \oplus D_6 \oplus P_2 &=& 0 \\\\ 1 \oplus 1 \oplus 1 \oplus 1 \oplus P_2 &=& 0 \\\\ 0 \oplus 1 \oplus 1 \oplus P_2 &=& 0 \\\\ 1 \oplus 1 \oplus P_2 &=& 0 \\\\ 0 \oplus P_2 &=& 0 \end{array}$

$P_2 = 0$ 才能使上述式子成立 , 因此校验位 $P_2 = 0$ ;

4、 P3 校验位计算

$P_3$ 校验的位计算 : $P_3$ 对应的二进制位是 $0100$ , 第 $3$ 位是 $1$ , 查看哪些二进制位的数据位第 $3$ 位是 $1$ ;

数据位索引 $5$ : $0$ $1$ $01$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_2$ 位 , 值为 $0$ ;
数据位索引 $6$ : $0$ $1$ $10$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_3$ 位 , 值为 $1$ ;
数据位索引 $7$ : $0$ $1$ $011$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;

$\begin{array}{lcl}D_2 \oplus D_3 \oplus D_4 \oplus P_3 &=& 0 \\\\ 0 \oplus 1 \oplus 1 \oplus P_3 &=& 0 \\\\ 1 \oplus 1 \oplus P_3 &=& 0 \\\\ 0 \oplus P_3 &=& 0 \end{array}$

$P_3 = 0$ 才能使上述式子成立 , 因此校验位 $P_3 = 0$ ;

5、 P4 校验位计算

$P_4$ 校验的位计算 : $P_4$ 对应的二进制位是 $1000$ , 第 $4$ 位是 $1$ , 查看哪些二进制位的数据位第 $4$ 位是 $1$ ;

数据位索引 $9$ : $1$ $001$ , 二进制的第 $4$ 位是 $1$ , 红色部分 ; 对应数据位 $D_5$ 位 , 值为 $0$ ;
数据位索引 $10$ : $1$ $010$ , 二进制的第 $4$ 位是 $1$ , 红色部分 ; 对应数据位 $D_6$ 位 , 值为 $1$ ;

$\begin{array}{lcl}D_5 \oplus D_6 \oplus P_4 &=& 0 \\\\ 0 \oplus 1 \oplus P_4 &=& 0 \\\\ 1 \oplus P_4 &=& 0 \end{array}$

$P_4 = 1$ 才能使上述式子成立 , 因此校验位 $P_4 = 1$ ;

6、最终海明码结果

计算出的四个校验码 :

$P_1 = 0$
$P_2 = 0$
$P_3 = 0$
$P_4 = 1$

将上述校验码填写到表格中 :

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1 = 0$	$P_2 = 0$	$1$	$P_3=0$	$0$	$1$	$1$	$P_4=1$	$0$	$1$

最终海明码为 : $00$ $1$ $0$ $011$ $1$ $01$ , 蓝色是数据位 , 红色是校验位 ;

五、检错纠错

发送的正确的海明码数据是 : $00$ $1$ $0$ $011$ $1$ $01$ , 蓝色是数据位 , 红色是校验位 ;

海明码数据表格是 :

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1 = 0$	$P_2 = 0$	$1$	$P_3=0$	$0$	$1$	$1$	$P_4=1$	$0$	$1$

假设海明码第 $5$ 位出现错误 , $D_2$ 数据原来是 $0$ , 出现错误变成 $1$ ;

正确海明码 : $00$ $1$ $0$ $011$ $1$ $01$

错误海明码 : $00$ $1$ $0$ $1$ $11$ $1$ $01$ , 第 $5$ 位的 $0$ 变成了 $1$ ;

检错过程 : $4$ 个检验位 , 每个检验位 , 令所有要校验的位进行异或 $\oplus$ 运算 ;

错误海明码数据表格是 :

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1 = 0$	$P_2 = 0$	$1$	$P_3=0$	$1$ ( 错误位 )	$1$	$1$	$P_4=1$	$0$	$1$

1、 P1 校验位校验

$P_1$ 校验的位计算 : $P_1$ 对应的二进制位是 $0001$ , 第一位是 $1$ , 查看哪些二进制位的数据位第 $1$ 位是 $1$ ;

数据位索引 $3$ : $001$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_1$ 位 , 值为 $1$ ;
数据位索引 $5$ : $010$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_2$ 位 , 值为 $1$ ;
数据位索引 $7$ : $011$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;
数据位索引 $9$ : $100$ $1$ , 二进制的第一位是 $1$ , 红色部分 ; 对应数据位 $D_5$ 位 , 值为 $0$ ;

令所有要校验的数据位和校验位 , 异或 ( $\oplus$ ) 计算后为 $0$ ;

异或计算 $\oplus$ : 同 $0$ , 异 $1$ , 两个位不同时为 $1$ , 两个位相同时为 $0$ ;

$\begin{array}{lcl} &&D_1 \oplus D_2 \oplus D_4 \oplus D_5 \oplus P_1 \\\\ &=& 1 \oplus 1 \oplus 1 \oplus 0 \oplus 0 \\\\ &=& 0 \oplus 1 \oplus 0 \oplus 0 \\\\ &=& 1 \oplus 0 \oplus 0 \\\\ &=& 1 \oplus 0 \\\\ &=& 1 \end{array}$

$P_1$ 校验位校验出错 ; $D_1 , D_2, D_4, D_5$ 位中 , 有错误出现 ;

2、 P2 校验位校验

$P_2$ 校验的位计算 : $P_2$ 对应的二进制位是 $0010$ , 第二位是 $1$ , 查看哪些二进制位的数据位第 $2$ 位是 $1$ ;

数据位索引 $3$ : $00$ $1$ $1$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_1$ 位 , 值为 $1$ ;
数据位索引 $6$ : $01$ $1$ $0$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_3$ 位 , 值为 $1$ ;
数据位索引 $7$ : $01$ $1$ $1$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;
数据位索引 $10$ : $10$ $1$ $0$ , 二进制的第 $2$ 位是 $1$ , 红色部分 ; 对应数据位 $D_6$ 位 , 值为 $1$ ;

$\begin{array}{lcl} &&D_1 \oplus D_3 \oplus D_4 \oplus D_6 \oplus P_2 \\\\ &=& 1 \oplus 1 \oplus 1 \oplus 1 \oplus 0 \\\\ &=& 0 \oplus 1 \oplus 1 \oplus 0 \\\\ &=& 1 \oplus 1 \oplus 0 \\\\ &=& 0 \oplus 0 \\\\ &=& 0 \end{array}$

$P_2$ 校验位校验正确 ; $D_1 , D_3, D_4, D_6$ 位数据正确 ;

3、 P3 校验位校验

$P_3$ 校验的位计算 : $P_3$ 对应的二进制位是 $0100$ , 第 $3$ 位是 $1$ , 查看哪些二进制位的数据位第 $3$ 位是 $1$ ;

数据位索引 $5$ : $0$ $1$ $01$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_2$ 位 , 值为 $1$ ;
数据位索引 $6$ : $0$ $1$ $10$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_3$ 位 , 值为 $1$ ;
数据位索引 $7$ : $0$ $1$ $011$ , 二进制的第 $3$ 位是 $1$ , 红色部分 ; 对应数据位 $D_4$ 位 , 值为 $1$ ;

$\begin{array}{lcl} &&D_2 \oplus D_3 \oplus D_4 \oplus P_3 \\\\ &=& 1 \oplus 1 \oplus 1 \oplus 0 \\\\ &=& 0 \oplus 1 \oplus 0 \\\\ &=& 1 \oplus 0 \\\\ &=& 1 \end{array}$

$P_3$ 校验位校验出错 ; $D_2 , D_3, D_4$ 位中 , 有错误出现 ;

4、 P4 校验位校验

$P_4$ 校验的位计算 : $P_4$ 对应的二进制位是 $1000$ , 第 $4$ 位是 $1$ , 查看哪些二进制位的数据位第 $4$ 位是 $1$ ;

数据位索引 $9$ : $1$ $001$ , 二进制的第 $4$ 位是 $1$ , 红色部分 ; 对应数据位 $D_5$ 位 , 值为 $0$ ;
数据位索引 $10$ : $1$ $010$ , 二进制的第 $4$ 位是 $1$ , 红色部分 ; 对应数据位 $D_6$ 位 , 值为 $1$ ;

$\begin{array}{lcl} &&D_5 \oplus D_6 \oplus P_4 \\\\ &=& 0 \oplus 1 \oplus 1 \\\\ &=& 1 \oplus 1 \\\\ &=& 0 \end{array}$

$P_4$ 校验位校验正确 ; $D_5, D_6$ 位数据正确 ;

5、纠错

校验结果 :

$P_1$ 校验位校验出错 ; $D_1 , D_2, D_4, D_5$ 位中 , 有错误出现 ;
$P_2$ 校验位校验正确 ; $D_1 , D_3, D_4, D_6$ 位数据正确 ;
$P_3$ 校验位校验出错 ; $D_2 , D_3, D_4$ 位中 , 有错误出现 ;
$P_4$ 校验位校验正确 ; $D_5, D_6$ 位数据正确 ;

综合上面 $4$ 次校验结果 , 发现 $D_2$ 数据错误 , 将下面的表格中的 $D_2$ 错误纠正 , 由 $1$ 纠正成 $0$ 即可 ;

错误海明码数据表格是 :

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1 = 0$	$P_2 = 0$	$1$	$P_3=0$	$1$ ( 错误位 )	$1$	$1$	$P_4=1$	$0$	$1$

正确海明码数据表格是 :

二进制位	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
数据位索引	1	2	3	4	5	6	7	8	9	10
名称	$P_1$	$P_2$	$D_1$	$P_3$	$D_2$	$D_3$	$D_4$	$P_4$	$D_5$	$D_6$
实际值	$P_1 = 0$	$P_2 = 0$	$1$	$P_3=0$	$0$ ( 纠错后的结果 )	$1$	$1$	$P_4=1$	$0$	$1$

最终将错误的海明码 $00$ $1$ $0$ $1$ $11$ $1$ $01$ ( 第 $5$ 位的 $0$ 变成了 $1$ ) , 纠正为正确的海明码 $00$ $1$ $0$ $011$ $1$ $01$ ;

【计算机网络】数据链路层 : 差错控制 ( 纠错编码 | 海明码 | “海明码“ 原理 | “海明码“ 工作流程 | 确定校验啊位数 | 确定校验码和数据位置 | 求校验码值 | 检错纠错 )★

文章目录

一、 “海明码” 工作原理

二、 “海明码” 工作流程

三、 确定校验码位数

四、 确定校验码和数据位置

0、 确定校验码位置

1、 引入二进制位

2、 P1 校验位 计算

3、 P2 校验位 计算

4、 P3 校验位 计算

5、 P4 校验位 计算

6、 最终海明码结果

五、 检错纠错

1、 P1 校验位 校验

2、 P2 校验位 校验

3、 P3 校验位 校验

4、 P4 校验位 校验

5、 纠错

相关推荐