汉明码

汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序列段，在每一段后面附加r位的监督码，且监督码和信息码之间构成线性关系，即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。

编码原理

设码长为n，信息位长度为k，监督位长度为r=n-k。如果需要纠正一位出错，因为长度为n的序列上每一位都可能出错，一共有n种情况，另外还有不出错的情况，所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2^r种情况。因此

2^r >= n + 1， 即r >= log(n+1)

我们以一个例子来说明汉明码。假设k=4，需要纠正一位错误，则

2^r >= n + 1 = k + r + 1 = 4 + r + 1

解得r >= 3。我们取r=3，则码长为3+4=7。用a6,a5,...a0表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我们作如下规定（这个规定是任意的）：

S1 S2 S3 错码的位置

0 0 1 a0

0 1 0 a1

1 0 0 a2

0 1 1 a3

1 0 1 a4

1 1 0 a5

1 1 1 a6

0 0 0 无错

按照表中的规定可知，仅当一个错码位置在a2,a4,a5或a6时校正子S1为1，否则S1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系：

S1 = a6⊕a5⊕a4⊕a2 (1)式

同理，可以得到：

S2 = a6⊕a5⊕a3⊕a1 (2)式

S3 = a6⊕a4⊕a3⊕a0 (3)式

在发送信号时，信息位a6,a5,a4,a3的值取决于输入信号，是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定，即监督位的取值应该使上述(1)(2)(3)式中的S1,S2,S3为0，这表示初始情况下没有错码。即

a6⊕a5⊕a4⊕a2 = 0

a6⊕a5⊕a3⊕a1 = 0

a6⊕a4⊕a3⊕a0 = 0

由上式进行移项运算，得到：

a2 = a6⊕a5⊕a4

a1 = a6⊕a5⊕a3

a0 = a6⊕a4⊕a3

已知信息位后，根据上式即可计算出a2,a1,a0三个监督位的值。

接收端受到每个码组后，先按照(1)~(3)式计算出S1,S2,S3，然后查表可知错码情况。

例如，若接收到的码字为0000011，按照(1)~(3)计算得到：

S1 = 0, S2 = 1, S3 = 1

查表可得在a3位有一个错码。

这种编码方法的最小汉明距离为d=3，所以这种编码可以纠正一个错码或者检测两个错码。

举例说明

现以数据码1101为例讲讲汉明码的编码原理，此时D8=1、D4=1、D2=0、D1=1，在P1编码时，先将D8、D4、D2的二进制码相加，结果为偶数2，汉明码对奇数结果编码为0，偶数结果为1，因此P1值为0，D8+D4+D1=3，为奇数，那么P2值为1，D8+D2+D1=2，为偶数，P3值为0。这样，参照上文的位置表，汉明码处理的结果就是1101-010。在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码的。下面就是它们与前面的规定的对应表：

A6 A5 A4 A3 A2 A1 A0

D8 D4 D2 D1 P1 P2 P3

P1=D8^D4^D2

P2 =D8^D4^D1

P3 =D8^D2^D1

从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的（不过只允许一个位出错，两个出错就无法检查出来了，这从下面的纠错例子中就能体现出来）。在校验时则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1）则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。　还是刚才的1101的例子，正确的编码应该是1101-010，如果第三个数据位D4在传输途中因干扰而变成了1，就成了1111-010。检测时，P1+D8+D4+D2的结果是奇数3，第一位纠错代码为1。P2+D8+D4+D1的结果是偶数4，第二位纠错代码为0，P3+D8+D2+D1的结果是奇数3，第三但纠错代码代码为1，有错误。那么具体是哪个位有错误呢？101查上面错码位置的表可得A4也就是D2位置出错了。