汉明码生成过程图文详解

汉明码生成

• 步骤一、确定校验位个数
• 步骤二、确定校验位位置
• 步骤三、分组
• • 1、十进制式下标
  • 2、对应位
  • 3、数值位
  • 4、二进制式下标
  • 5、确认分组
• 步骤四、校验位数值的确定
• 总结
• 例题分析

2020-9-11修正说明：

原文将确定校验位个数的公式：2^k - 1 >= n + k写成了：2^k - 1 <= n + k,感谢weixin_43802386的指正，目前已改成正确的公式，在实例使用的地方也进行了修正，同时对原文一些用词不太准确或冗杂的地方做了修改并对分组这一步骤进行了新的排版。希望原文的失误没有给小伙伴带来困扰。

步骤一、确定校验位个数

确定校验位的个数是比较简单的一步，主要就是利用公式：2^k - 1 >= n + k

其中n为要发送的这个数据的二进制位位数，也就是原始的待发送数据有几个数字；k为检验位需要的位数。考试中常见的检验位并不会很大，一般也就是2到4位，很容易就算出来。

步骤二、确定校验位位置

校验位所处的位置也是有规定的，校验位必须放在位置下标为2^(i - 1)的位置，从理解上来说就是必须放在位置标号为2的整数次方的位置，这里用i - 1是因为i从1开始，而我们需要从0次方算。

步骤三、分组

进行分组的原因是我们要知道哪些校验位应该由哪些数据位决定。分组基于我们前两步的基础上，具体操作如下：

1、十进制式下标

根据第一步确定了一共要发送n + k位数据，位置下标从1 到（n + k）写在第一行上；

2、对应位

第二行做对应位，根据第二步算出的校验位位置先安排校验位，再将数据位按照原来的顺序依次填到剩下的位置上，这里需要注意数据的顺序是不变的；

3、数值位

第三行为数值位，将待发送数据数值写到对应位置（这里只是为了方便，不写也不影响）。

4、二进制式下标

将第一行位置标号用二进制表示，比如：1 --> 001(这里的位数以k的为准，此处以3为例），位置的标号要竖着写，也就是说位置标号的每一个二进制位对应一行。这里要注意的是，在写列的编号的时候，你可以反着写，即从下到上把1写成100；也可以顺着写，即从上到下，比如1写成001。两种都不会改变结果，只是第二种感觉更顺一点，因为我们的习惯就是上到下，所以第一次看到另一种写法的时候就不太理解，他怎么想到的这个，但是这种也是有优点的，就是你写出来的分组，校验位正好是排好序的，也就是第一组正好对应第一位检验位，其他也是一 一对应，而从上到下正好相反，所以根据自己的习惯就行。

5、确认分组

在第4步之后，在二进制化的位置标号那里从行去看，同一行中二进制位为1的同属一个组，这样就能够分好组了。

步骤四、校验位数值的确定

分好组之后，这一步就很简单了，只需要让检验位 = 同一组里的数据位的异或就可以了。这里关于异或的计算，看到一篇博文上说可以直接看1的个数，奇数个结果为1，偶数个结果为0，这是自己之前没注意到，这样的计算确实能在计算的时候帮我们节省一些时间。

总结

从篇幅就可以看出，汉明码的关键步骤在于如何确定分组， 其他步骤都是很固定的套路，基本就是利用公式。

例题分析

发送数据为0101，采用汉明码编码，发送端的发出去的数据是？

1）确定发送数据的位数

数据位n: 4 ； 检验位k：代求

把已知的数据带进2^k - 1 >= n + k --> 2^k - 1 <= 4+ k;具体的算法我也不知道怎么算，我自己的的话就用带入法，就是你大概看下K可以去多少，然后试一下，一般涉及的难度也不会太大，我们直接就能看出来的那种。

2） 确定校验位的位置

根据的我们的原则，就只需要从2的0次方开始， k个2的整数次方就可以了，比如这里k是3，那么就计算2的0到2次方，也就是：1,2,4

3）确定分组

我们就简单粗暴的用标号直接代表位置好了，因为看到有的教材还用了字母加下标的。为了方便描述把数据对应d1到d4,检验位对应c1到c3。

• 先安排校验位，结果如下

  

• 将数据位按原顺序放入剩下的位置

  

• 填写数据位

  

  * 位置下标变成二进制

  根据我们前面的描述，这里就需要三行，将提到两个不同的安排方式作对比

从上到下安排

分组：c3d2d3d4、c2d1d3d4、c1d1d2d4

从下到上排

分组：c1d1d2d4、c2d1d3d4、c3d2d3d4

• 从行去看确定分组

  从表格就可以很清晰的看出每个分组，标红的数字为1的对应位就是我们分组中的具体值。由表可知三个分组分别为：c1d1d2d4、c2d1d3d4、c3d2d3d4。从两个表格的对比我们就可以明确看出各自的优缺点。

4）校验位数值计算

根据公式或计算技巧直接算就可以了。

c1 = 0；c2 = 1; c3 = 0

注：这一步虽然简单，但还是比较容易出错的（也可能只有我会这么干吧），我容易出错的点呢就是我计算的时候想的是用数据值去计算，但是我总是会用位置标号的数值去计算，比如算c1的时候我们应该是用d1d2d4也就是011算，然后我会直接看到“位置标号二进制化”那里去，也就是会看成是用111来算，这样的话出来的每个检验位都一样了。虽然有点蠢的犯错方式，但是不知道有没有人会掉进同样的坑里。

• 确定发送数据

  把计算好的校验位放到自己的位置上就可以了。