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

韩曙亮

发布于 2023-03-28 16:47:36

5320

发布于 2023-03-28 16:47:36

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、 “海明码” 工作原理

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

海明码工作原理 :

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

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

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

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

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

二、 “海明码” 工作流程

"海明码" 工作流程 :

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

三、确定校验码位数

海明不等式 :

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_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

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

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_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

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

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

, 二进制的第

2

位是

1

, 红色部分 ; 对应数据位

D_1

位 , 值为

1

;

数据位索引

6

:

01

1

0

, 二进制的第

2

位是

1

, 红色部分 ; 对应数据位

D_3

位 , 值为

1

;

数据位索引

7

:

01

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_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

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

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_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

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

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_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

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

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

, 二进制的第

2

位是

1

, 红色部分 ; 对应数据位

D_1

位 , 值为

1

;

数据位索引

6

:

01

1

0

, 二进制的第

2

位是

1

, 红色部分 ; 对应数据位

D_3

位 , 值为

1

;

数据位索引

7

:

01

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_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

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

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_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

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

P_4=1

0

1

最终将错误的海明码

00

1

0

1

11

1

01

( 第

5

位的

0

变成了

1

) , 纠正为正确的海明码

00

1

0

011

1

01

;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-08-17，如有侵权请联系 cloudcommunity@tencent.com 删除

二进制

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度