汉明校验码原理解析

1. 简介

汉明校验码又名海明码。作用是在一定程度上能校验是否有传输出错,如果仅有一位出错,还能纠错。

2. 需求

对于原信息串一共 \(k\) 位,内容为: \([A_k,A_{k-1},A_{k-2},…,,A_{1}]\) ,且为二进制,每一位非 0 则 1 .

先考虑最简单的情况集:S={仅某一位出错,都没出错}

  • 如果没出错能基于校验码得知没出错
  • 如果出错能基于校验码发现是哪一位出错,并纠错(当情况集仅限于S)

3. 要求

要做到上述两点我们需要多少比特的信息呢?

很简单,数一下有多少种状态再取 \(log_2\) 即可。没有出错为 \(1\) 个状态,每一位分别出错,一共 \(k\) 个状态,总计 \(1+k\) 个状态,那至少需要 \(log_2(1+k)\) 位额外的验证位才可能承载这样的需求。

而且当引入了额外验证位后,通常要把验证位本身出错的情况也考虑进去。假设最后使用了 \(m\) 位验证位。则

\begin{align}
m \geq log_2(1+k+m)
\end{align}

整理一下,得到

\begin{align}
2^m – m \geq 1 + k
\end{align}

即可以以此考察 $late m$ 最低的要求。

3. 计算方式

如何用 \(log_2 (k+m+1)\) 的二进制位去指针哪一位有问题呢?

借鉴10头猪的试1000瓶毒药问题,我们或许可以使用二进制的思路:一个目标位会影响多个结果位,且影响方式尽可能正交。

其实最简单的就是二进制编码。

假设传输的信息是 111111 ,但第 5 位传输错误,希望能配合校验码通过一个运算得到 “(前面m-3个零)101” ,即二进制的 5。

但与此同时别忘了还有一个重要状态是 “都没出错” 。好在我们如果下标编号是从 1 开始,则可以令为 0 的结果代表正确。

由此,需求被进一步细化为

  • 正确的情况下,可以通过一个校验运算,输入获得的信息,得到 0
  • 有一位错误的情况下,可以通过相同的校验运算,得到错误的位置

那怎么做到这一点呢?

继续借鉴10头猪的试1000瓶毒药的问题。毒药问题中,有毒和无毒是两种绝对的状态,所以可以用绝对的 0 和 1 进行表示,于是可以直接构建二进制。

而在这里,结果并非绝对的 0 和 1 ,而是相对于初始值是否相异的问题。

有什么运算能帮我们判断相异呢?巧了~那就是“异或”

同时异或还有一个很好的性质:

  • 不仅可以判断两个位是否相同。如果把 n 个位相继异或运算得到的值,和任意一位取反后的值刚好相反。

(哈哈哈,是不是有点像逆序数的奇偶性)

基于此可以照搬毒药的方式生成校验码序列,假设 $m$ 位汉明码序列为:

\begin{align}
[A_{k+m},A_{k-1+m},A_{k-2+m},…,,A_{1+m},V_m,V_{m-1},V_{m-2},…,,V_{1}]
\end{align}

则 \(V_i\) = 按序异或(所有序号二进制第 i 位为 1 的位)

这样似乎就可以在获取信息后用相反的方式按异或得到理论校验码,并且再和接受的校验码异或得到 0(正确)或者 x (第x位错误)

但事实上这样还有问题:

  1. 计算一个校验码位时,可能运算内容参杂了其他校验码位,比如在计算 第 2 位校验码时,需考虑第 7 位(如果存在)校验码的值,那到底应该先计算谁呢?会互锁吗?
  2. 事实上上个问题还是小问题,更重要的是当得到一个校验码的值为 100 (m=3),那到底是第三位校验码出错还是第四位信息位出错呢?这产生了歧异。

当然,解决方法并不困难,即把校验码的 $V_i$ 放在整个序列的第 $2^i$ 位置,使 0010、0100、1000、0001 等等都刚好指向自己。这样消除了歧异。且在计算时不会相互交叉。

于是便得到了汉明码。

\begin{align}
[…A_5,V_4,A_4,A_3,A_2,V_3,A_1,V_2,V_{1}]
\end{align}

4. 示例

4.1 计算汉明码

比如我们有一个信息长为 4 内容为”1010″,需要求其汉明码。

首先确定校验码需要的位数,根据

\begin{align}
2^m \geq 1+k+m
\end{align}

将 \(k = 4\) 代入,可以发现满足条件的 $m$ 最小的正整数为 $3$

于是结果的形式应为:\([1,0,1,V_3,0,V_2,V_1]\)

再求每一位校验码,根据$V_i$ = 按序异或(所有序号二进制第 i 位为 1 的位)

\begin{align}
V_1 &= 1 xor 1 xor 0 = 0 \\
V_2 &= 1 xor 0 xor 0 = 1\\
V_3 &= 1 xor 1 xor 1= 1
\end{align}

于是得到汉明码 \([1,0,1,1,0,1,0]\)

4.2 纠错示例

如果我们在传输汉明码 \([1,0,1,1,0,1,0]\) 时,第 3 位传错了,获得 \([1,0,1,1,1,1,0]\) ,则接收方重新计算

\begin{align}
V_1 &= 1 xor 1 xor 1 = 1 \\
V_2 &= 1 xor 0 xor 1 = 0 \\
V_3 &= 1 xor 1 xor 1= 1
\end{align}

将计算得到的校验序列 101 与接受的校验序列 110 取异或,得到011,即十进制的3,即第3位有问题。

4.3 多位出错

如果有多位传输出错会有什么情况呢,比如两位出错,使 \([1,0,1,1,0,1,0]\) 传错为 \([1,0,1,1,1,1,1]\),计算后得到 010 ,这显然不能再用于纠错,但依旧可以根据其不等于 0 得知有错。

再尝试多出错一位,使 \([1,0,1,1,0,1,0]\) 传错为 \([1,0,1,1,1,0,1]\),得到 000 ,则是否错误的信息也无法判断了。

由此可知这样的方式产生的汉明码仅足够一位的纠错,如果要更多位则需要其他方式增强。

5. 全校验

\begin{align}
2^k-k>n+1
\end{align}

时,由于信息还有富余,可以选在首部再加一位全校验位,值等于后续所有位的异或结果。进一步增强识别能力。

6. 参考资料

https://www.zhihu.com/question/29169628/answer/837787585

Leave a Comment