海明码原理

海明码是一位纠错码，即如果数据在传输过程中有一位出错，则可以知道出错的位数并通过取反将其改正过来。

海明码的基本意思是给传输的数据增加r个校验位，从而增加两个合法消息（合法码字）的不同位的个数（海明距离）。假设要传得信息有m位，则经海明编码的码字就有n=m+r位。怎样安排才能达到我们的目的呢？在解释之前我们先看一道微软的面试题。

面试题：

把1K个苹果分到10个篮子里（当然苹果分到

篮子里后就不能再动了，只能分一次）。
要求：
用这10个篮子能够组成1-1000任意一个数字 。

这是个考察二进制思想的题目，让每个篮子里的苹果数等于二进制位的权重就可以了，即分别放1，2，4，8，……各苹果。

换到海明码里也是这样，为了让r个校验码（r个篮子）表示n个信息位（n个苹果），且无论哪一位错误都能表示出来（能够组成任意一个数字），先将码字的位从左到右标号，分别为1，2，3，……。显然要将校验位安排在第1，2，4，8，……编号上，数据放在其他的编号上。为了能够将n位信息全部表示出来还应该有2r-1>=n。每个数据位影响几个校验位，譬如编号11

对应的数据影响编号1、2、8对应的校验位,因为11=1+2+8。为了更清楚理解上面的意思，让我们来看一个例子：将1001000编码成海明码。

因为编号1、2、4、8处是校验位，所以3、5、6、7、9、10、11处是数据位，将要传输的数据与编号对应如下：

3 5 6 7 9 10 11

1 0 0 1 0 0 0

数据位影响的校验位如下：

编号3处的数据位影响编号1、2处的校验位，

编号7处的数据位影响编号1、2、4处的校验位，

经偶校验的校验位1、2的值为0，校验位4的值

为1，其他校验位均为0。所以对应的海明码

为：00110010000。

接受方通过检验校验位来计算出错的位，如果校验位i的奇偶性不正确，则将计数器的值加i，如果所有的校验位都检查完了，且计数器为0，则检查成功，否则计数器的值就是出错的位所对应的编号，并将该位取反。

PS：其实接受方可以不用检查校验位是否有正确的奇偶性，而是看它是否为1，若是则计数器加i，检查完所有的校验位，将计数器的值对应的信息位取反。