什么是海明码呀？通俗一点，但又能深刻一点！谢谢了！！！
海明码其实也不难，相对于寄偶检验码 它不仅可以检验出错误，还能修正错误！但只能是检验、修正一位错误！说一大堆理论是没什么意思，下面将通过一个例子，尽可能的用最通俗易懂的方式进行讲解！最后大家会发现海明码很神奇！！
假设要传送的数据为：1011 0011
校验流程如下：
一：确定校验位并插入到有效数据位中。
相比奇偶校验只插入一个检验码，海明码需要插入多个检验码，插入的位数与有效数据位数相关，公式如下
公式：2^r-r>k+1,其中r就是要插入检验码的个数,取满足条件的最小整数，k是有效数据位数。因为我们要传送的数据是：1011 0011，显然k=8,推出r=4。也就说我们要将4个校验位插入到有效数据中，怎么插入呢？按照如下规则：
插入位置固定为2^N（N：0，1,2,3,4，5……）处，因为r=4，即只需要取4个有{2^0,2^1,2^2,2^3},对应位置即是1,2,4,8，当然了，如果r=5,那么插入位置为：1,2,4,8，16.同类可以推出其他情况，不再啰嗦。（之所以选择这样的位置插入，是为了有效的分组，保证后面的校验分组能有效的错开，不会互相干扰，这句话不需要理解，到后面就能体会！）
通过分析得到待传送的数据为：xx1x 011x 0011,4位校验位+8为有效数据位。
二、确定校验位的数值。
显然X只能取0,1，下面确定x的值：
由一可知待传送数据为：xx1x 011x 0011。
规则：以X的位置为长度，依次从待传送数据中取X个数，然后跳过X个数，再取X个数，直到待传送数据串尾,得到一个子串，然后统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1(当然，反过来也行，其实这就是奇偶校验的规则，想了解奇偶校验可以参见我以前的回答的，这里不了解也行)
第1个X：位置为1，从第1个位置开始依次取1个数据，并跳过1个数据再取，直到串尾得到一个子串：
{x 1 0 1 0 1}，这个串可记为第1个校验组, 因为1的个数是3个为奇数，故x=0.
第2个X：位置为2，故从第2个位置开始依次取2个数据，并跳过2个数据再取，直到串尾得到一个子串：
{x1 11 01} ，记为第2个校验组,因为1的个数为4是偶数，故x=1.
第3个X：位置是4，故从第4个位置开始依次取4个数据，并跳过4个数据再取，直到串尾得到一个子串：
{x011 1}，记为第3个校验组，因为1的个数为3是奇数，故x=0.
第4个X：位置是8，故从第8个位置开始依次取8个数据，并跳过8个数据再取，直到串尾得到一个子串：
{x0011 }，记为第4个校验组，……，X=1。
故得到最终的待传送的数据串为：011001110011。
这里其实就可以看到了，为什么X的位置要取2^N,这样才能保证各个校验位不会相互干扰。
经过以上一、二步骤就完整了海明码的构造过程，下面讲解校验过程：
三、根据步骤二中的构造规则，取出各校验组
发送的数据串为：011001110011。
假设接受到的数据串为：011001111011（注意和传送数据串相比，第9为出现了错误！）
规则：以X的位置为长度，依次从待传送数据中取X个数，然后跳过X个数，再取X个数，直到待传送数据串尾,得到一个子串，然后统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1(规则必须和步骤二中一样)
根据二中制定的规则再次取出各个校验组。
第1个校验组：从第1个位置开始依次取1个数据，并跳过1个数据再取，直到串尾得到一个子串：{0 1 0 1 1 1}。
第2个校验组：从第2个位置开始依次取2个数据，并跳过2个数据再取，直到串尾得到一个子串：{11 11 01}
第3个校验组：从第4个位置开始依次取4个数据，并跳过4个数据再取，直到串尾得到一个子串：{0011 1}
第4个校验组：从第8个位置开始依次取8个数据，并跳过8个数据再取，直到串尾得到一个子串：{11011}.
四、根据步骤二的构造规则，确定存在错误的校验组，并通过错误校验组的交集，最终确定出错的位置。
由步骤三得到4个校验组：
1：{0 1 0 1 1 1}。 对应位置为{1 3 5 7 9 11}
2：{11 11 01}。对应位置为{2 3 6 7 10 11}
3：{0011 1} 。对应位置为{4567 12}
4：{11011}。 对应位置为{8 9 10 11 12}
因为我们的构造规则是：统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1。
所以正确的校验组中1的个数绝对是奇数！（好好琢磨，很容易就想通了，如果我们的规则是为奇数，则x=1,为偶数，x=0。那么正确的校验组中1的个数绝对是偶数），所以如果校验组1的个数不是奇数，那么这个校验组就存在问题。因而可以判断第1个和第4个校验组出现问题了。
确定了第1个和第4个校验组出现问题后，找到这两个校验组的交集即第9个位置和第11个位置是它们交集，即共同校验的位置。于是判断出现问题的位置要么就是第9个位置，要么就是第11个位置！因为在第2个校验组中有第11个位置，故第11个位置绝对没有出错，因为就可以判断是第9个位置出现错误！
到这里，应该懂了吧？但是不是觉得找出错位置有点麻烦啊？下面就给出一个具体的实现方法，理解了上面的描述，再了解下面实现的方法，立马就能确定出错误的位置：
首先：我们对各个校验组求异或。
第一个校验组：{0 1 0 1 1 1} 异或的结果为：0
第二个校验组：{11 11 01}异或的结果为：1
第三个校验组：{0011 1}异或的结果为：1
第四个校验组：{11011}异或的结果为：0
接着：倒置拼接异或结果，得到：0110，
最后：按位取反的到：1001,。
大家有没有惊奇的发现1001的十进制数就是9，这不就是出错的位置吗？这是巧合吗？
不急再看一个例子：
传送的数据串为： 011001110011（还是我们开始的那个串）
接受到的数据串为：011011110011（和正确数据串相比，第5个位置出错了）
第一个校验组：{0 1 1 1 0 1} 异或的结果为：0
第二个校验组：{11 11 01}异或的结果为：1
第三个校验组：{0111 1}异或的结果为：0
第四个校验组：{10011}异或的结果为：1
倒置拼接：1010 反转为：0101 对应十进制数为5！
也就是说方法是真确的！！不用怀疑！！这也就是海明码的奇妙之处！
再来看看一个例子：
传送的数据串为： 011001110011（还是我们开始的那个串）
接受到的数据串为：011001100011（和正确数据串相比，第8个位置校验位出错了）
显然这是校验位出错了，那么能不能校验出来呢？
第一个校验组：{0 1 0 1 0 1} 异或的结果为：1
第二个校验组：{11 11 01}异或的结果为：1
第三个校验组：{0011 1}异或的结果为：1
第四个校验组：{00011}异或的结果为：0
倒置反转结果为1000 正好是8，所以也没问题。
下面我们来说下规则：（其实就是说异或与奇偶的关系，想拓展的就可以看看）
上面的例子中，我们规定： 统计子串中1的个数，如果为奇数，则x=0,为偶数，x=1。如果是按这样的规定，那么校验组中1的个数必定是奇数，正是因为如此，所以校验组中如果1的个数不是奇数那么肯定出现了错误！而如果一个串中1的个数是奇数，那么串异或的结果一定为1，其实这个规则对应的就是奇校验！反之，如果为奇数，则x=1,为偶数，x=0，那么对应的就是偶校验！
故得到以下结论：
如果采用奇检验构造海明码，那么出错校验组中的1的个数必为偶数，即异或的结果必定为0！
如果采用奇检验构造海明码，那么出错的位置是校验组异或结果倒置拼接并反转的十进制数
如果采用偶检验构造海明码，那么出错校验组中的1的个数必为奇数，即异或的结果必定为1！
如果采用偶检验构造海明码，那么出错位置是校验组异或结果直接倒置拼接的十进制数！
关于偶检验构造海明码这里就不再详细展开，如果你能用偶检验的方法在把上面的例子都做一遍，那么海明码你就已经完全弄懂了！试试吧！
关于奇偶检验码 建议还是看看，因为海明码是基于奇偶校验的改进！而且奇偶校验更简单！
关于海明码的原理和计算
综合上面我们求一下信息1011的海明码是多少？
答：
我们知道信息位有4位，即为n=4,求得公式中校验位K=3。所以海明码一共7位:H7-H1 ; 信息位：D3-D0; 校验位：P3-P1。
求P3-P1在海明码中的位置。根据图中下面这句话。我们可以求得位置。
p1= 2的（1-1）次方=1
p2=>2
p3=>4
校验位在海明码中的位置：P1----1 P2----2 P3----4
现在我们需要求得P1-P3的值，我们的海明码就出来了。
eg: H7 下标为7， 校验码下标有1,2,4。 则需要7=4+2+1 。所以P1,P2,P3都参与了D3的校验。
接下来我们统计一个各个校验位校验的信号位有哪些。
P1---->P1,D0,D1,D3
P2---->P2,D0,D2,D3
P3---->P3,D1,D2,D3
进行异或运算（相同为0，相异为1）
P1=D0⊕D1⊕D3=1 1 1=1
P2=D0⊕D2⊕D3=1 0 1=0
P3=D1⊕D2⊕D3=1 0 1=0
所以海明码为：1010101。
检错计算: 本来是1011，假如传过来的是1001。(D1出错了)
则从又到左D0=1 D1=0, D2=0, D3=1
G1=P1⊕D0⊕D1⊕D3=1 1 0 1=1
G2=P2⊕D0⊕D2⊕D3=0 1 0 1=0
G3=P3⊕D1⊕D2⊕D3=0 0 0*1=1
G3G2G1=101
如果是偶校验，则需要全部为0，如果是奇校验全部为1。
101的10进制。则是海明码里面的第5位出错。H5(D1)出错。则D1取反，得到。1001-->1011 。 这样就实现了检错，改错了。
如何理解海明码可以发现双比特错，但是只能纠正单比特错？
纠错编码：
不仅可以发现错位，还可以指出错位的位置，为自动纠错提供数据。
海明码：
可以发现双比特错，但只能纠正单比特错。
海明码工作原理：
动一发而牵全身（在数据中有多个校验码，可能一个比特受多个校验码校验，当一个比特出了差错，可以通过校验码看出哪个比特出错）
海明码工作流程：
1.确定校验码位数r
n为有效信息的位数,k位校验码位数:
2^k>=n+k+1;
例如：D=1010 (n=4)
带入上述公式得出 :
k = 3 得出对应的海明码位数为 4+3=7位
2.确定校验码和数据的位置
Note：二进制从0001开始，千万不要从0开始
校验码只能放在2的几次方的位置
p1 放在2的0次方 = 1p2 放在2的1次方 = 2p3 放在2的2次方 = 4D = 1 0 1 0 (D4--D1)| 二进制 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 || 数据位 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | | 代 码 | D4 | D3 | D2 | p3 | D1 | p2 | p1 | | 实际值 | 1 | 0 | 1 | | 0 | | | 剩下的位置放置原数据
3.求出校验码的值
Note：二进制从0001开始，千万不要从0开始| 二进制 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 || 数据位 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | | 代 码 | D4 | D3 | D2 | p3 | D1 | p2 | p1 | | 实际值 | 1 | 0 | 1 | | 0 | | | 以p1为例，p1二进制位末位是 1找所有二进制位位 1 的校验位 p1,D1,D2,D4 ==（？，0，1，1）
令所有要校验的位 异或 = 0： p1,D1,D2,D4 相互异或 （同0异1） 得到p1 = 0同理求出剩余
p2 找第二位是 1p3 找第三位是 1| 二进制 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 || 数据位 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | | 代 码 | D4 | D3 | D2 | p3 | D1 | p2 | p1 | | 实际值 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
4.检错并纠错
| 二进制 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 || 数据位 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | | 代 码 | D4 | D3 | D2 | p3 | D1 | p2 | p1 | | 实际值 | 1 | 0 | 1->0 | 0 | 0 | 1 | 0 |假设D2从 1变成了0 接收端做第三步的逆操作
令所有要检验的位异或运算
p1 = (0，0，0，1) = 1p2 = 0p3 = 1可以看出出错的是第 三 位和第 一 位是 1 的数 也就是 D2 出错了 将D2改正
简单理解海明校验码
二进制数据经过传送、存取等环节，会发生误码(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
海明码的原理
海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： r 2^r ≥ k r 1 或 2^r ≥ n 1海明码的编码效率为： R=k/(k+r) 式中 k为信息位位数 r为增加冗余位位数
目录
1.海明码的原理
2.海明码的生成与接收
3.海明码的计算
4.海明码校验程序设计原理分析参考
编辑本段1.海明码的原理
在数据中间加入几个校验码，码距均匀拉大，将数据的每个二进制位分配在几个奇偶校验组里，当某一位出错，会引起几个校验位的值发生变化。
海明不等式：
校验码个数为K，2的K次方个信息，1个信息用来指出“没有错误”，其余（2^K)-1个指出错误发生在那一位，但也可能是校验位错误，故有N<=(2^K)-1-K能被校验。
海明码的编码规则：
1.每个校验位Ri被分配在海明码的第2的i次方的位置上，
2.海明码的每一位（Hi)是由多个/1个校验值进行校验的，被校验码的
位置码是所有校验位的校验位位置码之和。
一个例题：
4个数据位d0,d1,d2,d3, 3个校验位r0,r1,r2，对应的位置为：
d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1
校验位的取值，就是他所能校验的数据位的异或
b1为b3,b5,b7的异或，b2为b3,b6,b7 b4为b5,b6,b7
海明v传送到接受方后，将上三式的右边（b1,b2,b4)的逻辑表达式分别
异或上左边的值就得到了校验方程，如果上题采用偶校验
G1=b1 b3 b5 b7的异或
G2=b2 b3 b6 b7的异或
G3=b4 b5 b6 b7的异或
若G1G2G3为001是第一位错
若为011是第三位错
编辑本段2.海明码的生成与接收
特注：以下的+均代表异或
方法一：
1)海明码的生成。
例1.已知：信息码为："0010"。海明码的监督关系式为：
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
求：海明码码字。
解：1)由监督关系式知冗余码为a2a1a0。
2)冗余码与信息码合成的海明码是："0010a2a1a0"。
设S2=S1=S0=0,由监督关系式得：
异或运算：
a2=a4+a5+a6=1
a1=a3+a5+a6=0
a0=a3+a4+a6=1
因此，海明码码字为："0010101"
对以上这道题目的第二问的疑问：
冗余码与信息码合成的海明码是："0010a2a1a0"。为什么a2a1a0直接加在信息码后面，而不是按照1,2,4,8位的顺序加在信息码后面【例如：001(a2)0(a1)(a0)=0011001】
2)海明码的接收。
例2.已知：海明码的监督关系式为：
S2=a2+a4+a5+a6
S1=a1+a3+a5+a6
S0=a0+a3+a4+a6
接收码字为："0011101"(n=7)
求：发送端的信息码。
解：1)由海明码的监督关系式计算得S2S1S0=011。
2)由监督关系式可构造出下面错码位置关系表：
S2S1S0
000
001
010
100
011
101
110
111
错码位置
无错
a0
a1
a2
a3
a4
a5
a6
3)由S2S1S0=011查表得知错码位置是a3。
4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"
5)把冗余码a2a1a0删除得发送端的信息码："0010"
方法二：(不用查表，方便编程)
1)海明码的生成（顺序生成法）。
例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=4代表冗余位数，即校验码位数)
求：海明码码字。
解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码
码字:" A B 1 C 1 0 0 D 1 1 0 0 "
码位: 1 2 3 4 5 6 7 8 9 10 11 12
其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。
2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)
监督关系式的推导：
D C B A
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
根据上面表格得到 A B C D
需要说明的是公式中参与计算的是表格中出现"1"的那个位 右边是数据位的二进制数,公式中的"+"表示异或
故此有如下表达式：
A->1,3,5,7,9,11；(这里的1 3 5 7 9 11均为A那一列出现1的位)
B->2,3,6,7,10,11；
C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
D->8,9,10,11,12。
3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：
A=∑(0,1,1,0,1,0)=1
B=∑(0,1,0,0,1,0)=0
C=∑(0,1,0,0,0) =1
D=∑(0,1,1,0,0) =0
4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"
2)海明码的接收。
例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=4代表冗余位数，即校验码位数)
求：发送端的信息码。
解：1)设错误累加器(err)初值=0
2)求出冗余码的偶校验和，并按码位累加到err中：
A=∑(1,0,1,0,1,0)=1 err=err+2^0=1
B=∑(0,0,0,0,1,0)=1 err=err+2^1=3
C=∑(1,1,0,0,0) =0 err=err+0 =3
D=∑(0,1,1,0,0) =0 err=err+0 =3
由err≠0可知接收码字有错，
3)码字的错误位置就是错误累加器(err)的值3。
4)纠错--对码字的第3位值取反得正确码字：
"1 0 1 1 1 0 0 0 1 1 0 0"
5)把位于2的k次方位的冗余码删除得信息码："1 1 0 0 1 1 0 0"
编辑本段3.海明码的计算
海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。
码字(Code Word) 按如下方法构建：
1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 8, 16, 32, 64等的位置)
2、其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置)
3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。
位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…)
位置2：校验2位，跳过2位，校验2位，跳过2位 (2,3,6,7,10,11,14,15,…)
位置4：校验4位，跳过4位，校验4位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,…)
位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,…)
…
如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.
举例说明：
一个字节的数据：10011010
构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0
计算每个校验位的奇偶性 ( ?代表要设置的比特位):
位置1检查1,3,5,7,9,11:
? _ 1 _ 0 0 1 _ 1 0 1 0. 偶数个1，因此位置1设为0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0
位置2检查2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1，因此位置2设为1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0
位置4检查4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1，因此位置4设为1，即: 0 1 1 1 0 0 1 _ 1 0 1 0
位置8检查8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1，因此位置8设为0，即: 0 1 1 1 0 0 1 0 1 0 1 0
因此码字为: 011100101010.
查找并纠错一位错误
上例中构建了一个码字 011100101010，假定实际接收到的数据是011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位，可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来，对所有校验位进行检查, 将所有出错的校验位置相加, 得到的就是错误信息所在的位置.
编辑本段4.海明码校验程序设计原理分析参考
海明码校验是为了保证数据传输正确而提出的，本来就是一串要传送的数据，如：D7,D6,D5,D4,D3,D2,D1,D0，这里举的是八位数据，可以是n位数据。就这样传送数据，不知道接收到后是不是正确的。所以，要加入校验位数据才能检查是否出错。这里涉及到一个问题，要多少位校验数据才能查出错误呢？
我们只要能检测出一位出错，则对于8位信息数据，校验位为4位。满足下列条件：2的k次方大于等于n+k+1，其中k为校验位位数，n为信息数据位位数。验证一下，2的4次方等于16，n+k+1等于8+4+1等于13。 8位信息数据与4位校验位总共有12位数据，怎么排列呢？我们先把校验位按P4,P3,P2,P1排列，用通式Pi表示校验位序列，i为校验位在校验序列中的位置。 传送的数据流用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1表示，接下来的问题是如何用D7,D6,D5,D4,D3,D2,D1,D0与P4,P3,P2,P1来表M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1了。校验位在传送的数据流中位置为2的i－1次方，则P1在M1位，P2在M2位，P3在M4位，P4在M8位。其余的用信息数据从高到低插入。 传送的数据流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1。 接下来，我们要弄明白如何找出错误位的问题。引进4位校验和序列S4,S3,S2,S1。S4,S3,S2,S1等于0,0,0,0表示传送的数据流正确；如S4,S3,S2,S1等于0,0,1,0则表示传送的数据流中第2位出错；如S4,S3,S2,S1等于0,0,1,1则表示传送的数据流中第3位出错；依次类推。
用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1如何表示S4,S3,S2,S1呢，简单的方法就是S1=1时，S4,S3,S2从0,0,0到1,1,1的所有的Mx异或。即S1等于M1异或M3异或M5异或M7异或M9异或M11。也就是S1等于P1异或D0异或D1异或D3异或D4异或D6。S2=1时，S4,S3,S1从0,0,0到1,1,1的所有的Mx异或。即S2等于M2异或M3异或M6异或M7异或M10异或M11。S3=1时，S4,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S3等于M4异或M5异或M6异或M7异或M12。S4=1时，S3,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S4等于M8异或M9异或M10异或M11异或M12。这样，对于一串码流，知道几位校验位，可以很快确定哪一位出错。而在发送端，可以根据S4,S3,S2,S1的表达式求出P4,P3,P2,P1的表达式，只要把式子右边的P4或P3或P2或P1移到左边替换掉S4或S3或S2或S1就可以了。面举例说明：用^表示异或
D7,D6,D5,D4,D3,D2,D1,D0=11010001
S4=M8^M9^M10^M11^M12=D7^D6^D5^D4^P4; P4=D7^D6^D5^D4;
S3=M4^M5^M6^M7^M12 =D7^D3^D2^D1^P3; P3=D7^D3^D2^D1;
S2=M2^M3^M6^M7^M10^M11 =D6^D5^D3^D2^D0^P2; P2=D6^D5^D3^D2^D0;
S1=M1^M3^M5^M7^M9^M11=D6^D4^D3^D1^D0^P1; P1=D6^D4^D3^D1^D0;
所以，
P4=D7^D6^D5^D4=1^1^0^1=1
P3=D7^D3^D2^D1=1^0^0^0=1
P2= D6^D5^D3^D2^D0=1^0^0^0^1=0 P1=D6^D4^D3^D1^D0=1^1^0^0^1=1
故，传送码流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1等于
110110001101
若接收端收到110110001101，则
S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
S3=M4^M5^M6^M7^M12=1^0^0^0^1=0
S2=M2^M3^M6^M7^M10^M11=0^1^0^0^0^1=0
S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
故，接收码流正确。
若M6出错，由0变为1。则
S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
S3=M4^M5^M6^M7^M12=1^0^1^0^1=1
S2=M2^M3^M6^M7^M10^M11=0^1^1^0^0^1=1 S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
即S4S3S2S1=0110，此为十进制的6，说明第六位出错，也就是M6出错。完全符合。
5.海明码的表格计算
如果对于m位的数据，增加k位冗余位，则组成位n=m+k位的纠错码。对于2^m个有效码字中的每一个，都有n个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是1，含单个错误位。这样，对于一个有效的消息总共有n+1个可识别的码字。这n+1个码字相对于其他2^m-1个有效消息的距离都大于1。这意味着总共有2^m（n+1）个有效的或是可纠错的码字。显然这个数应小于等于码字的所有的可能的个数2^n。于是我们有
2^m（n+1）<2^n
因为n=m+k，我们得出
m+k+1<2^k
对于给定的数据位m，上式给出了k的下界，即要纠正单个错误，k必须取最小的值。海明建议了一种方案，可以达到这个下界，并能直接指出错在哪一位。首先把码字的位从1到n编号，，并把这个编号表示成二进制数，即2的幂之和。然后对2的每一个幂设置一个奇偶位。例如对于6号位，由于6=110（二进制），所以6号位参加第2位和第4位的奇偶校验，而不参加第1位奇偶校验。类似的9号位参加第1位和第8位的奇偶校验而不参加第2位和第4位的奇偶校验。海明把奇偶校验分配在1,2,4,8等位置上，其他位置放数据。下面根据海明编码的例图，举例说明编码的方法
海明编码的例
海明编码的例
例如传送的消息为：1001011
我们把数据放在3,5,6,7,9,10,11等位置上，1,2,4,8则为校验位。
1
0 0 1
0 1 1
1 2 3 4 5 6 7 8 9 10 11
根据海明编码的例，3、5、7、9、11的二进制编码的第一位为1，所以3、5、7、9、11号位参加第一位校验位，若按偶校验计算，1号位应为1
1
1
0 0 1
0 1 1
1 2 3 4 5 6 7 8 9 10 11
类似的，3、6、7、10、11号位参加2号位校验，5、6、7号位参加4号位校验，9、10、11号位参加8号位校验，全部按偶校验计算，最终得到如下结果
1 0 1 1 0 0 1 0 0 1 1
1 2 3 4 5 6 7 8 9 10 11
如果这个码字传输中有错误，比如说6号位出错。就会变成
√ ╳ ╳ √
1 0 1 1 0 1 1 0 0 1 1
1 2 3 4 5 6 7 8 9 10 11
当接收端按照同样的规则计算奇偶位时，就会发现1号位和8号位的奇偶性正确而2号位和4号位的奇偶性不对，于是2+4=6,，立即可以判断错在6号位。
上例中k=4，因而m<2^4-4-1=11,即数据位可以用到11位，共组成15位的码字，可检测出单个位置的错误。
怎么理解海明码？
海明码1.海明码的概念海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式：2^r>=n+1 或 2^r>=k+r+1海明码的编码效率为：R=k/(k+r)式中 k为信息位位数r为增加冗余位位数 2.海明码的生成与接收方法一：1)海明码的生成。例1.已知：信息码为："0010"。海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求：海明码码字。解：1)由监督关系式知冗余码为a2a1a0。2)冗余码与信息码合成的海明码是："0010a2a1a0"。设S2=S1=S0=0,由监督关系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，海明码码字为："0010101"2)海明码的接收。例2.已知：海明码的监督关系式为：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6接收码字为："0011101"(n=7)求：发送端的信息码。解：1)由海明码的监督关系式计算得S2S1S0=011。2)由监督关系式可构造出下面错码位置关系表： S2S1S0000001010100011101110111错码位置无错a0a1a2a3a4a5a63)由S2S1S0=011查表得知错码位置是a3。4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"5)把冗余码a2a1a0删除得发送端的信息码："0010"方法二：(不用查表，方便编程)1)海明码的生成（顺序生成法）。例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=8)求：海明码码字。解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码码字:" A B 1 C 1 0 0 D 1 1 0 0 "码位: 1 2 3 4 5 6 7 8 9 10 11 12 其中A,B,C,D分别插于2k位(k=0,1,2,3)。码位分别为1,2,4,8。2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)A->1,3,5,7,9,11；B->2,3,6,7,10,11； C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)D->8,9,10,11,12。3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：A=∑(0,1,1,0,1,0)=1B=∑(0,1,0,0,1,0)=0C=∑(0,1,0,0,0) =1D=∑(0,1,1,0,0) =04)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"2)海明码的接收。例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=8)求：发送端的信息码。解：1)设错误累加器(err)初值=02)求出冗余码的偶校验和，并按码位累加到err中：A=∑(1,0,1,0,1,0)=1 err=err+20=1B=∑(0,0,0,0,1,0)=1 err=err+21=3C=∑(1,1,0,0,0) =0 err=err+0 =3D=∑(0,1,1,0,0) =0 err=err+0 =3由err≠0可知接收码字有错，3)码字的错误位置就是错误累加器(err)的值3。4)纠错--对码字的第3位值取反得正确码字："1 0 1 1 1 0 0 0 1 1 0 0"5)把位于2k位的冗余码删除得信息码："1 1 0 0 1 1 0 0"
