简单理解海明校验码

二进制数据经过传送、存取等环节，会发生误码(1变成0或0变成1)，这就肆含有如何发现及纠正误码的问题。所有解决此类问题的方法就是在原始数据(数码位)基础上增加几位校验位。我们常使用的检验码有三种. 分别是奇偶校验码、海明校验码和循环冗余校验码(CRC)。

海明校验码是由RichardHamming于1950年提出、目前还被广泛采用的一种很有效的校验方法。它的裂如笑实现原理，是在k个数据位之外加上r个校验位，从而形成一个k+r位的新的码字，使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为进一步自动纠错提供了依据。但是因为这种海明校橡棚验的方法只能检测和纠正一位出错的情况。所以如果有多个错误，就不能查出了。

什么是码距？

两个码组对应位上数字的不同位的个数称为码组的距离，简称码距，又称海明（Hamming）距离。例如00110和00100码距为1，12345和13344码距为2，Caus和Daun码距为2。

海明校验码公式（假设为k个数据位设置r个校验位）

公式怎么得出来的呢？

假设有r个校验位，一个位子有0或1两种情况，r个位子就有2 r种排列情况，能表示2 r种状态。其中一个状态用来表示正确（没有错误发生）的这种情况。其余的2 r-1种状态来表示错误发生在哪一位。总共有k+r位，所以2 r-1一定要>=总位子k+r。

按照该不等可以得出k与r的对应关系

注意：海明校验码是放在2的幂次位上的，即“1,2,4,8,16,32······”

实战求1011的海明码

第一步：求r的值（即校验位数）

直接根据公式代入得：

2^r-1 ≥ 4 + r

2^r-r ≥ 5

得到r最小为3

所以海明码的位数是4+3=7位

第二步：校验位和信息位对号入座

注意： 信息位的位置分配是从高位到低位依次存放

注意： 海明校验码是放在2的幂次位上的

位数|1|2|3|4|5|6|7

:-:|:-:|:-:|:-:|:-:|:-:|:-:

信息位|||1||1|0|1

校验位|r1|r2||r3|||

第三步：确定校验位的值

校验原则：被校验的海明位的下标等于所有参与校验该为的校验位的下标之和

然后将校验码校验的信息位的位置记录下来：

然后做对应信息位的异或运算(异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）)

代入表格得到

注意：按照从低位到高位的排列顺序得到海明码：1010101

最近和朋友的聊天涉及到了海明码纠错，先来康康海明纠错码到底是什么

Hamming Code，电信领域的一种线性调试码，由于编码简单，广泛应用于内存（RAM）。

若海明码长为n，信息位数为k，则需要插入r个监督位校验码。如果想要r个校验码能构成r个关系式来指示出错码的n个可能位置，则需要

即为

比如说我们有8位二进制数需要编码，那么应该有

海明码的校验码都在2的整数次幂处，也就是第1、2、4....等位

注意这不是数组索引，没有第0位数。

如果用pn表示第n个校验码

dk表示第k个数据

所以我们的8位二进制数编码结果应该是

校验位1 的校验规则是从当前位数起，校验做告一位，跳过一位，再校验一位，再跳过一位.......也就是说校验了所有数据位位置序号的二进制表示的最后一位是1的数据，即 0001，0011，0101，0111，1001，1011

同理，第k个校验位的校验规则是从当前位开始连续校验 位然后跳过 位纯枣明......也就是说，第k位校验位应该校验数据位位置序号的二进制表示的倒数第k位是1的数据

其实就是二进制数的第k位表示

那到底咋算嘞？

之前学过奇校验和偶校验，可以排上用场了

奇校验是要求整个被校验的位中“1”的个数为奇数，偶校验则是要求整个被校验的位中“1”的个数为偶数

我们用偶校验来试算一下。

比如我们输入的数据是10111011

插入后应该是

计算p1， 第0001，0011，0101，0111，1001，1011位中除了p1本身共有4个1，所有p1为0可以使“1”的总数为0

同理p2为0

p3为1

p4为1

所得数据为

比起普通的奇校验偶校验而言，海明码非常强大的一点就在于它不仅可以实现校验，还能实现1bit的纠错。

依然以我们的偶校验为例

可以看出来的是，所有的校验码位都不会被其他校验码影响，仅由自己校验自己，这就保证了如果我们的某位校验码出错的话不会影响其他校验码的校验结果，我们岩迅可以轻易的找到这个出错的校验码。

所以说，我们的四个校验组计算出来如果只有一个校验组的结果是错误的，那么说明是该位校验码出错，取反即可。

再来看看数据位。

因为每个数据都被校验了2-3次，所以出错的校验组数肯定大于1

如果是两个校验组出错的话，有d1、d2、d3、d5、d6、d8，每个数据位都和校验组的组合形式一一对应，因此我们知道哪两个校验组出错就知道了哪一位出错。

如果是三个校验组出错的话同理也可以找出是哪一位。

本来应该用FPGA写verilog的，不过我现在电脑里就只能写python

就用python做了一个hamming码的编码与校验纠错

海明码是一种利用奇偶性来差错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置插入K个校验位，通过扩大码距来实现检错和纠错。镇余碧

假设数据位是n位，校验位是k位，则n和k的关系必须满足以下关系：

2^k -1 >= n+k

依据给定的数据位，很容推断到校验位，但是校验位在数据中的位置需要立即。

还是以一个实际的御举例子说明吧：

原始数据：1011

这样 n=4 , 将 k=1,2,3,...  代入公式很容发现 k=3就满足条件，2^3-1 >=4+3

所以校验码位数为3位，数据和校验码一共7位。

校验码的位置都处在2的n(n=0,1,2,3...)次方中，即位于1,2,4,8,16....的位置上，其余为才能填充数据。

本例就7位数据组成：D4D3D2D1+P2P1P0

7        6        5        4        3        2        1

D4      D3    D2       P2      D1      P1    P0

1        0        1                    1

7=4+2+1 ==>第4位 P2,第2位P1，第1位 P0 这3个校验位共同校验

6=4+2==>第4位 P2,第2位P1 这2个校验位共同校验

5=4+1 ==>第4位 P2，第1位 P0  这2个校验位共同校验

3=2+1 ==>第2位P1，第1位 P0    这2个校验位共同校验

校验码计数,异或运算：

P2 = D7^D6^D5=1^0^1=0

P1=D7^D6^D3=1^0^1=0

P0=D7^D5^D3=1^1^1=1

校验码为：001

传输数据为： 1 0 1  0  1  0 1

检错和纠错原理

接收方依据同样的规则重新计算三位校验毁唤码的值。而后与接收到的校验码进行异或。当数据无误时，产生的校验码无误，若接收到的校验码有误，那么这不同的2个校验码异或，必然为1.

若某位的校验码最终异或结果为1，则表示产生了错误，找出错误位之后，就可以纠错了，纠错方法就时将该为逆转。

---