【计算机网络】数据链路层 : 差错控制 ( 纠错编码 | 海明码 | “海明码“ 原

文章目录

一、 "海明码" 工作原理二、 "海明码" 工作流程三、确定校验码位数四、确定校验码和数据位置0、确定校验码位置1、引入二进制位2、 P1 校验位计算3、 P2 校验位计算4、 P3 校验位计算5、 P4 校验位计算6、最终海明码结果五、检错纠错1、 P1 校验位校验2、 P2 校验位校验3、 P3 校验位校验4、 P4 校验位校验5、纠错

一、 “海明码” 工作原理

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

海明码工作原理 :

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

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

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

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

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

二、 “海明码” 工作流程

"海明码" 工作流程 :

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

三、确定校验码位数

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

rrr 是冗余信息位kkk 是信息位

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

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

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

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

③ 满足海明不等式最小 rrr 计算 :2r≥7+r2^r \geq 7+r2r≥7+r , 依次从 111 开始代入 , 获取满足不等式最小的 rrr 的值为 444 ;

④ 发送数据 :发送的数据海明码是 101010 位 , 其中原始数据有 666 位 , 校验码有 444 位 ;

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

0、确定校验码位置

确定校验码和数据位置 :发送数据 101101101101101101 , 海明码位数为 101010 位 ;

① 校验码 444 位 :P1P_1P1 , P2P_2P2 , P3P_3P3 , P4P_4P4 ;

② 数据位 666 位 :D1D_1D1 , D2D_2D2 , D3D_3D3 , D4D_4D4 , D5D_5D5 , D6D_6D6 ;

③ 校验码位置 :校验码只能放在 222 的幂次方位置 , 如 20=12^0 = 120=1 , 21=22^1 = 221=2 , 22=42^2 = 422=4 , 23=82^3 =823=8 , 2n2^n2n等位置 ;

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

⑤ 最终生成的数据位 :

1、引入二进制位

求校验码值 :

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

2、 P1 校验位计算

P1P_1P1 校验的位计算 :P1P_1P1 对应的二进制位是 000100010001 , 第一位是 111 , 查看哪些二进制位的数据位第 111 位是 111 ;

数据位索引 333 : 001001001111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D1D_1D1 位 , 值为 111 ;数据位索引 555 : 010010010111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D2D_2D2 位 , 值为 000 ;数据位索引 777 : 011011011111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D4D_4D4 位 , 值为 111 ;数据位索引 999 : 100100100111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D5D_5D5 位 , 值为 000 ;

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

异或计算 ⊕\oplus⊕ :同 000 , 异 111 , 两个位不同时为 111 , 两个位相同时为 000 ;

D1⊕D2⊕D4⊕D5⊕P1=01⊕0⊕1⊕0⊕P1=01⊕1⊕0⊕P1=00⊕0⊕P1=00⊕P1=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}D1⊕D2⊕D4⊕D5⊕P11⊕0⊕1⊕0⊕P11⊕1⊕0⊕P10⊕0⊕P10⊕P1=====00000

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

3、 P2 校验位计算

P2P_2P2 校验的位计算 :P2P_2P2 对应的二进制位是 001000100010 , 第二位是 111 , 查看哪些二进制位的数据位第 222 位是 111 ;

数据位索引 333 : 000000111111 , 二进制的第 222 位是 111 , 红色部分 ; 对应数据位 D1D_1D1 位 , 值为 111 ;数据位索引 666 : 010101111000 , 二进制的第 222 位是 111 , 红色部分 ; 对应数据位 D3D_3D3 位 , 值为 111 ;数据位索引 777 : 010101111111 , 二进制的第 222 位是 111 , 红色部分 ; 对应数据位 D4D_4D4 位 , 值为 111 ;数据位索引 101010 : 101010111000 , 二进制的第 222 位是 111 , 红色部分 ; 对应数据位 D6D_6D6 位 , 值为 111 ;

D1⊕D3⊕D4⊕D6⊕P2=01⊕1⊕1⊕1⊕P2=00⊕1⊕1⊕P2=01⊕1⊕P2=00⊕P2=0\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}D1⊕D3⊕D4⊕D6⊕P21⊕1⊕1⊕1⊕P20⊕1⊕1⊕P21⊕1⊕P20⊕P2=====00000

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

4、 P3 校验位计算

P3P_3P3 校验的位计算 :P3P_3P3 对应的二进制位是 010001000100 , 第 333 位是 111 , 查看哪些二进制位的数据位第 333 位是 111 ;

数据位索引 555 : 000111010101 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D2D_2D2 位 , 值为 000 ;数据位索引 666 : 000111101010 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D3D_3D3 位 , 值为 111 ;数据位索引 777 : 000111011011011 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D4D_4D4 位 , 值为 111 ;

D2⊕D3⊕D4⊕P3=00⊕1⊕1⊕P3=01⊕1⊕P3=00⊕P3=0\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}D2⊕D3⊕D4⊕P30⊕1⊕1⊕P31⊕1⊕P30⊕P3====0000

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

5、 P4 校验位计算

P4P_4P4 校验的位计算 :P4P_4P4 对应的二进制位是 100010001000 , 第 444 位是 111 , 查看哪些二进制位的数据位第 444 位是 111 ;

数据位索引 999 : 111001001001 , 二进制的第 444 位是 111 , 红色部分 ; 对应数据位 D5D_5D5 位 , 值为 000 ;数据位索引 101010 : 111010010010 , 二进制的第 444 位是 111 , 红色部分 ; 对应数据位 D6D_6D6 位 , 值为 111 ;

D5⊕D6⊕P4=00⊕1⊕P4=01⊕P4=0\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}D5⊕D6⊕P40⊕1⊕P41⊕P4===000

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

6、最终海明码结果

计算出的四个校验码 :

P1=0P_1 = 0P1=0P2=0P_2 = 0P2=0P3=0P_3 = 0P3=0P4=1P_4 = 1P4=1

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

最终海明码为 :000000111000011011011111010101 , 蓝色是数据位 , 红色是校验位 ;

五、检错纠错

发送的正确的海明码数据是 :000000111000011011011111010101 , 蓝色是数据位 , 红色是校验位 ;

海明码数据表格是 :

假设海明码第 555 位出现错误 , D2D_2D2 数据原来是 000 , 出现错误变成 111 ;

正确海明码 :000000111000011011011111010101

错误海明码 :000000111000111111111111010101 , 第 555 位的 000 变成了 111 ;

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

错误海明码数据表格是 :

1、 P1 校验位校验

P1P_1P1 校验的位计算 :P1P_1P1 对应的二进制位是 000100010001 , 第一位是 111 , 查看哪些二进制位的数据位第 111 位是 111 ;

数据位索引 333 : 001001001111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D1D_1D1 位 , 值为 111 ;数据位索引 555 : 010010010111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D2D_2D2 位 , 值为 111 ;数据位索引 777 : 011011011111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D4D_4D4 位 , 值为 111 ;数据位索引 999 : 100100100111 , 二进制的第一位是 111 , 红色部分 ; 对应数据位 D5D_5D5 位 , 值为 000 ;

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

异或计算 ⊕\oplus⊕ :同 000 , 异 111 , 两个位不同时为 111 , 两个位相同时为 000 ;

D1⊕D2⊕D4⊕D5⊕P1=1⊕1⊕1⊕0⊕0=0⊕1⊕0⊕0=1⊕0⊕0=1⊕0=1\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}=====D1⊕D2⊕D4⊕D5⊕P11⊕1⊕1⊕0⊕00⊕1⊕0⊕01⊕0⊕01⊕01

P1P_1P1 校验位校验出错 ; D1,D2,D4,D5D_1 , D_2, D_4, D_5D1,D2,D4,D5 位中 , 有错误出现 ;

2、 P2 校验位校验

P2P_2P2 校验的位计算 :P2P_2P2 对应的二进制位是 001000100010 , 第二位是 111 , 查看哪些二进制位的数据位第 222 位是 111 ;

D1⊕D3⊕D4⊕D6⊕P2=1⊕1⊕1⊕1⊕0=0⊕1⊕1⊕0=1⊕1⊕0=0⊕0=0\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}=====D1⊕D3⊕D4⊕D6⊕P21⊕1⊕1⊕1⊕00⊕1⊕1⊕01⊕1⊕00⊕00

P2P_2P2 校验位校验正确 ; D1,D3,D4,D6D_1 , D_3, D_4, D_6D1,D3,D4,D6 位数据正确 ;

3、 P3 校验位校验

P3P_3P3 校验的位计算 :P3P_3P3 对应的二进制位是 010001000100 , 第 333 位是 111 , 查看哪些二进制位的数据位第 333 位是 111 ;

数据位索引 555 : 000111010101 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D2D_2D2 位 , 值为 111 ;数据位索引 666 : 000111101010 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D3D_3D3 位 , 值为 111 ;数据位索引 777 : 000111011011011 , 二进制的第 333 位是 111 , 红色部分 ; 对应数据位 D4D_4D4 位 , 值为 111 ;

D2⊕D3⊕D4⊕P3=1⊕1⊕1⊕0=0⊕1⊕0=1⊕0=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}====D2⊕D3⊕D4⊕P31⊕1⊕1⊕00⊕1⊕01⊕01

P3P_3P3 校验位校验出错 ; D2,D3,D4D_2 , D_3, D_4D2,D3,D4 位中 , 有错误出现 ;

4、 P4 校验位校验

P4P_4P4 校验的位计算 :P4P_4P4 对应的二进制位是 100010001000 , 第 444 位是 111 , 查看哪些二进制位的数据位第 444 位是 111 ;

D5⊕D6⊕P4=0⊕1⊕1=1⊕1=0\begin{array}{lcl} &&D_5 \oplus D_6 \oplus P_4 \\\\ &=& 0 \oplus 1 \oplus 1 \\\\ &=& 1 \oplus 1 \\\\ &=& 0 \end{array}===D5⊕D6⊕P40⊕1⊕11⊕10

P4P_4P4 校验位校验正确 ; D5,D6D_5, D_6D5,D6 位数据正确 ;

5、纠错

校验结果 :

P1P_1P1 校验位校验出错 ; D1,D2,D4,D5D_1 , D_2, D_4, D_5D1,D2,D4,D5 位中 , 有错误出现 ;P2P_2P2 校验位校验正确 ; D1,D3,D4,D6D_1 , D_3, D_4, D_6D1,D3,D4,D6 位数据正确 ;P3P_3P3 校验位校验出错 ; D2,D3,D4D_2 , D_3, D_4D2,D3,D4 位中 , 有错误出现 ;P4P_4P4 校验位校验正确 ; D5,D6D_5, D_6D5,D6 位数据正确 ;

综合上面 444 次校验结果 , 发现 D2D_2D2 数据错误 , 将下面的表格中的 D2D_2D2 错误纠正 , 由 111 纠正成 000 即可 ;

错误海明码数据表格是 :

正确海明码数据表格是 :

最终将错误的海明码 000000111000111111111111010101 ( 第 555 位的 000 变成了 111 ) , 纠正为正确的海明码 000000111000011011011111010101 ;