10海明码校验码[中章]

海明校验码

海明码同时还会出现在计算机网络这门课程当中，所以需要要求掌握

设计思想

海明码设计思路:将信息位分组进行偶校验 --> 多个校验位->多个校验位标志错误的位置

多个校验位就可以携带多种状态信息(对还是错，错在哪)

需要多少校验码呢?

图解:
我们假设现在有n个信息位,k个校验位

我们k个校验位一共可以表达出2^k次方种状态，而需要表达的内容包裹$信息位置+校验位+正确的状态$
我们需要用2^k来表达n+k+1

$$ 2^k \geq n + k + 1 $$

根据这个算式我们可以得出

$$
\left{
\begin{array}{c}
假设有10位: \ &2^k - k\geq 11 \therefore k \leq 4\
\
假设有15位: \ &2^k - k \geq 16 \therefore k \leq 5\
\end{array}
\right.
$$

海明码求解步骤

假设我们的信息位: 1010

确定海明码的位数

我们这里有4位需要传递的信息，所以我们根据算式$ 2^k \geq n + k + 1 $可以得知，我们需要3个校验位

我们对这些位数进行定义

• 信息位就是大写字母D表示,比如D₁D₂D₃
• 校验位用大写字母P表示，比如P₁P₂P₃
• 所有的位数就用大写字母H表示,比如H₁H₂H₃

确定校验位

我们规定校验位应该放在$2^{i-1}$的位置上
如果现在有4个校验位，那么他们不应该连在一起放置，而且是需要按照这个公式进行放置

$$
p_1 \rightarrow 1号位置\
p_2 \rightarrow 2号位置\
p_3 \rightarrow 4号位置\
p_4 \rightarrow 8号位置\
$$

确定校验位的值

上面我们已经知道，校验位要放在什么地方，现在我们要用奇偶校验中的偶校验来求校验位的值^[1]

这个时候我们就拥有了纠错能力，如果我们的数据没有错误,我们最终三个校验位的值都会是0

假如数据发生错误，我们的结果就会是奇数,同时我们就可以根据值来判断是第几个位出错了

010位出错，转换为十进制就是 $$ 010 ,B = 2 ,D $$
此时就说明我们的H₂的位置上出错了

 

假如我们现在出错的位置是110 $$110 ,B = 6 ,D $$
此时就说明我们的H₆的位置上发生了错误

但是此时我们现在还是有一个麻烦，如果有多个位置发生了错误,那么我们就不知道到底是哪里发生了错误,于是我们还需要一个全局校验位，对整体进行偶校验

总览和回顾

---

1. 使用异或运算求偶校验码 ↩︎