汉明码详解（哈工大计组）

66 阅读 0 评论 44 点赞

我是靠谱客的博主热心缘分，最近开发中收集的这篇文章主要介绍汉明码详解（哈工大计组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

奇偶校验

汉明码采用分组奇偶校验
那么先搞懂奇偶校验，再说分组奇偶校验
在这里插入图片描述
说白了，就是要在代码前加入一位校验位
奇校验： 加入校验位后1的个数为奇数
偶校验： 加入校验位后1的个数为偶数

以下例子都采用偶校验

分组奇偶校验

分组其实有多种方式，汉明码采用了一种特殊的分组方式。
我们先不采用汉明码的方式分组，看看其他分组。
如下面例子：
在这里插入图片描述
我们采用偶校验，先不分组，怎么操作呢？
这个代码中有3个1，奇数个，那么最前面就要加个1，构成偶数个，如下：

我们如果送出去进行校验（先忽略校验过程），发现这个9位代码有错，1的个数变成了奇数个，但是是哪一位就不清楚了。

如果我们进行分组划分，划分为两组，每组之前都加校验码，采用偶校验，如下：
在这里插入图片描述
前4位0010，我们加1校验码
后四位0011，加0作为校验码
这样，如果前5位校验，发现1个数变为奇数，说明错误位置就在前5位里。
这样就缩小了范围。

上述的分组其实是一种简单的、无重叠的划分，各组之间没有交集。
而汉明码的分组就比较特殊了，如下：
比如一个7位代码，第1位我们不说是“第1个位置”，我们用二进制表示，说“第00001位置”。第二个位置，表示为“第00010位置”，以此类推。

那么这个7位数代码，各个位置用二进制表示：
第1位：第00001位；第2位：第00010位
第3位：第00011位；第4位：第00100位
第5位：第00101位；第6位：第00110位
第7位：第00111位

如何分组呢？
第1组：二进制代码最右边为1的，也就是XXXX1。
第2组：右边倒数第二位为1的，即XXX1X。
第3组：右边倒数第三位为1的，即XX1XX。
… …
那么，第1、3、5、7位就被分到第1组
我们发现3、7也满足第二组，同时也放入第2组中。所以，汉明码的分组是有重叠的。
分组情况如下：
在这里插入图片描述
组分好了，那校验位在哪里？
校验位是针对这一组数据的，所以不会和其他组共用位置。（第一个例子就是如此）
所以校验位放在1、2、4… … 2^i-1（i表示第几组）

如果我们把这样的汉明码送出去校验，结果发现第1组错了，2、3组没错，那么一定是第1位代码错误，公共部分不会错误（如果是第3位错误，那么第2组也会错误）

那么分组以及校验位的问题就解决了

配置汉明码

比如0011，要配置汉明码
对于校验位个数，要满足以下公式：
在这里插入图片描述
k表示校验位个数，n表示代码位数（例子中即为4）
2^k刚好大于等于n+k+1，计算完后，k=3
所以汉明码共7位

还记得汉明码的分组规则吧，每组都有一个校验位。
C1是第1组的校验位，第1组有1、3、5、7这些位置，3、5、7位置上共有1个1，如果采用偶校验，那么校验位上写1，即C1为1。
第二组2、3、6、7，校验位在2上，3、6、7上的1个数为偶数，那么C2为0。
第三组4、5、6、7，校验位在4上，5、6、7上的1个数为偶数，那么C4为0。
汉明码就确定了，如下：
在这里插入图片描述

汉明码纠错

概念：
形成新的检测位Pi，其位数与增添的检测位有关，如增添3位(k=3) ，新的检测位为P4、P2、P1。
说白了给这3组弄个编号，如果有错记为1，无错记为0。

已知接收到的汉明码为0100111（配偶原则配置），问要传送的信息是什么？
我们根据汉明码分组原则判断。
第1组为1、3、5、7的位置，分别为0、0、1、1，偶数个1，没有错，P1=0
第2组，2、3、6、7位置分别为1、0、1、1，奇数个1，有错，P2=1。
第3组4、5、6、7位置分别为0、1、1、1，奇数，有错，P4=1。

判断1个数也可以用异或操作：
在这里插入图片描述
P2和P4组有错，那么找公共位置，即6或7。但是7也在P1中，所以排除7，第6位有错。