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

2023-03-28 16:47:36 浏览数 (1)

文章目录

  • 一、 "海明码" 工作原理
  • 二、 "海明码" 工作流程
  • 三、 确定校验码位数
  • 四、 确定校验码和数据位置
    • 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_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
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
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_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
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
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
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_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
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
1
P_4=1
0
1

最终将错误的海明码

00
1
0
1
11
1
01

( 第

5

位 的

0

变成了

1

) , 纠正 为 正确的海明码

00
1
0
011
1
01

;

二进制 工作流 数据 索引 原理

0 人点赞