100分求高手讲解海明码！

海明码是一位纠错码，即如果数据在传输过程中有一位出错，则可以知道出错的位数并通过取反将其改正过来。
海明码的基本意思是给传输的数据增加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，则检查成功，否则计数器的值就是出错的位所对应的编号，并将该位取反。

将K位检测位记作Ci(i=1,2,4,8)分别安插在n+k位代码编号的第1，2，4，8，16位上。
01101110(n=8)根据2的k次方大于等于n+k+1,可求出配置成海明码需增添检测位k=4,
原码01101110记作B8,B7,B6,B5,B4,B3,B2,B1
则原码同检测位的位置安排如下：
二进制序号：1 2 3 4 5 6 7 8 9 10 11 12
名称 C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1
如果按配偶原则来配置海明码，则
C1应使1，3，5，7，9，11位中的“1”的个数为偶数；
C2应使2，3，6，7，10，11位中的“1”的个数为偶数；
C4应使4，5，6，7，12位中的“1”的个数为偶数；
C8应使8，9，10，11，12位中的“1”的个数为偶数；
故C1应为3位⊕5位⊕7位⊕9位⊕11位，即C1=B8⊕B7⊕B5⊕B4⊕B2
故C2应为3位⊕6位⊕7位⊕10位⊕11位，即C2=B8⊕B6⊕B5⊕B3⊕B2
故C4应为5位⊕6位⊕7位⊕12位，即C4=B7⊕B6⊕B5⊕B1
故C8应为9位⊕10位⊕11位⊕12位，即C8=B4⊕B3⊕B2⊕B1
即，
C1=B8⊕B7⊕B5⊕B4⊕B2=0⊕1⊕0⊕1⊕1=1
C2=B8⊕B6⊕B5⊕B3⊕B2=0⊕1⊕0⊕1⊕1=1
C4=B7⊕B6⊕B5⊕B1=1⊕1⊕0⊕0=0
C8=B4⊕B3⊕B2⊕B1=1⊕1⊕1⊕0=1
故01101110的海明校验码为C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1=110011011110

二进制数据经过传送、存取等环节，会发生误码(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

---