海明码是由R.HmIMI1ing在1950年首次提出的,它是一种可以纠正一位差错的编码。

    可以借用简单奇偶校验码的生成原理来说明海明码的构造方法。若k(=n-1)位信息位a_n-1a_n-2…a₁加上一位偶校验位a₀,构成一个n位的码字a_n-1a_n-2...a₁a₀,则在接收端校验时,可按关系式

　　　　S=a_n-1+a_n-2+…+a₁+a₀

来计算。若求得S=0,则表示元错;若S=1,则有错。上式可称为监督关系式,S称为校.正因子。.在奇偶校验情况下,只有一个监督关系式和一个校正因子,其取值只有0或1两种情.况,分别代表元错和有错两种结果,还不能指出差错所在的位置。不难设想,若增加冗余位,也即相应地增加了监督关系式和校正因子,就能区分更多的情况。如果有两个校正因子.
S₁和S₀,则S₁S₀取值就有00、01、10或11四种可能的组合,也即能区分四种不同的情况。若其中一种取值用于表示无错(如00),则另外三种(01、10及11)便可以用来指出.不同情况的差错,从而可以进一步区分出是哪一位错。

    设信息位为k位,增加r位冗余位,构成一个n=k+r位的码字。若希望用r个监督关系式产生的r个校正因子来区分元错和在码字中的n个不同位置的一位错,则要求满足以下关系式:
2^r>=n+1  或  2^r>=k+r+1

    以k=4为例来说明,则要满足上述不等式,必须r>=3。假设取r=3,则n=k+r=7,即在4位信息位a₆a₅a₄a₃后面加上3位冗余位a₂a₁a₀,构成7位码字a₆a₅a₄a₃a₂a₁a₀,其中a2、a1和a0分别由4位信息位中某几位半加得到,在校验时,a₂、a₁和a₀就分别和这些位半.加构成三个不同的监督关系式。在无错时,这三个关系式的值S₂、S₁和S₀全为"0"。若a₂错,则S₂=1,而S₁=S₀=0;若a₁错,则S₁=1,而S₂=S₀=0;若a₀错,则s₀=1,而S₂=S₁=0。S₂、S₁和S₀这三个校正因子的其它4种编码值可用来区分a₃、a₄、a₅、a₆中的一位错,其对应关系如表2.1。当然,也可以规定成另外的对应关系,这并不影响讨论的一般性。

表2.1                                S₂ S₁ S_{0 值与错码位置的对应关系}

由表可见,a₂、a₄、a₅或a₆的一位错都应使S₂=1,由此可以得到监督关系式..
S₂=a₂+a₄+a₅+a₆....
同理可得:S1=a₁+a₃+a₅+a₆..
S₀=a₀+a₃+a₄+a₆
在发送端编码时,信息位a₆、a₅、a₄和句的值取决于输入信号,它们在具体的应用中有l确定的值。冗余位电、a₁和a_o的值应根据信息位的取值按监督关系式来确定,使上述三式l中的S₂、S₁和S₀取值为零,即
a₂+a₄+a₅+a₆=0
a₁+a₃+a₅+a₆=0
a₀+a₃+a₄+a₆₌0
由此可求得:
a₂=a₄+a₅+a₆
a₁=a₃+a₅+a₆
a₀=a₃+a₄+_a6

已知信息位后,按上述三式即可算出各冗余位。对于本例来说,各种信息位算出的冗余位如表2.2所示。

表2.2                        由信息位算得海明码冗余位

    在接收端收到每个码字后,按监督关系式算出S₂、S₁和S₀,若它们全为"0",则认为无错;若不全为"0",在一位错的情况下,可查表2.1来判定是哪一位错,从而纠正之。例如码字0010101传输中发生一位错,在接收端收到的为0011101,代入监督关系式可算得S₂=0、S₁=1和S₀=1,由表2.1可查得S₂S₁S₀=011对应于a₃错,因而可将0011101纠正为00101010。

    上述海明码的编码效率为4/7。若K=7,按2r>=k+r+1可算得r至少为4,此时编码.效率为7/11。可见,信息位位数越多时编码效率就越高