$2.5.4海明碼
海明碼是由R.HmIMI1ing在1950年首次提出的,它是一種可以糾正一位差錯(cuò)的編碼。
可以借用簡單奇偶校驗(yàn)碼的生成原理來說明海明碼的構(gòu)造方法。若k(=n-1)位信息位an-1an-2…a1加上一位偶校驗(yàn)位a0,構(gòu)成一個(gè)n位的碼字an-1an-2...a1a0,則在接收端校驗(yàn)時(shí),可按關(guān)系式
S=an-1+an-2+…+a1+a0
來計(jì)算。若求得S=0,則表示元錯(cuò);若S=1,則有錯(cuò)。上式可稱為監(jiān)督關(guān)系式,S稱為校.正因子。.在奇偶校驗(yàn)情況下,只有一個(gè)監(jiān)督關(guān)系式和一個(gè)校正因子,其取值只有0或1兩種情.況,分別代表元錯(cuò)和有錯(cuò)兩種結(jié)果,還不能指出差錯(cuò)所在的位置。不難設(shè)想,若增加冗余位,也即相應(yīng)地增加了監(jiān)督關(guān)系式和校正因子,就能區(qū)分更多的情況。如果有兩個(gè)校正因子.
S1和S0,則S1S0取值就有00、01、10或11四種可能的組合,也即能區(qū)分四種不同的情況。若其中一種取值用于表示無錯(cuò)(如00),則另外三種(01、10及11)便可以用來指出.不同情況的差錯(cuò),從而可以進(jìn)一步區(qū)分出是哪一位錯(cuò)。
設(shè)信息位為k位,增加r位冗余位,構(gòu)成一個(gè)n=k+r位的碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分元錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò),則要求滿足以下關(guān)系式:
2r>=n+1 或 2r>=k+r+1
以k=4為例來說明,則要滿足上述不等式,必須r>=3。假設(shè)取r=3,則n=k+r=7,即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0,構(gòu)成7位碼字a6a5a4a3a2a1a0,其中a2、a1和a0分別由4位信息位中某幾位半加得到,在校驗(yàn)時(shí),a2、a1和a0就分別和這些位半.加構(gòu)成三個(gè)不同的監(jiān)督關(guān)系式。在無錯(cuò)時(shí),這三個(gè)關(guān)系式的值S2、S1和S0全為"0"。若a2錯(cuò),則S2=1,而S1=S0=0;若a1錯(cuò),則S1=1,而S2=S0=0;若a0錯(cuò),則s0=1,而S2=S1=0。S2、S1和S0這三個(gè)校正因子的其它4種編碼值可用來區(qū)分a3、a4、a5、a6中的一位錯(cuò),其對應(yīng)關(guān)系如表2.1。當(dāng)然,也可以規(guī)定成另外的對應(yīng)關(guān)系,這并不影響討論的一般性。
表2.1 S2 S1 S0 值與錯(cuò)碼位置的對應(yīng)關(guān)系
S2 S1 S0 000 001 010 100 011 101 110 111
錯(cuò)碼位置 無錯(cuò) a0 a1 a2 a3 a4 a5 a6
由表可見,a2、a4、a5或a6的一位錯(cuò)都應(yīng)使S2=1,由此可以得到監(jiān)督關(guān)系式..
S2=a2+a4+a5+a6....
同理可得:S1=a1+a3+a5+a6..
S0=a0+a3+a4+a6
在發(fā)送端編碼時(shí),信息位a6、a5、a4和句的值取決于輸入信號,它們在具體的應(yīng)用中有l(wèi)確定的值。冗余位電、a1和ao的值應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系式來確定,使上述三式l中的S2、S1和S0取值為零,即
a2+a4+a5+a6=0
a1+a3+a5+a6=0
a0+a3+a4+a6=0
由此可求得:
a2=a4+a5+a6
a1=a3+a5+a6
a0=a3+a4+a6
已知信息位后,按上述三式即可算出各冗余位。對于本例來說,各種信息位算出的冗余位如表2.2所示。
表2.2 由信息位算得海明碼冗余位
信息位 冗余位 信息位 冗余位
a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a0
0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111
在接收端收到每個(gè)碼字后,按監(jiān)督關(guān)系式算出S2、S1和S0,若它們?nèi)珵?0",則認(rèn)為無錯(cuò);若不全為"0",在一位錯(cuò)的情況下,可查表2.1來判定是哪一位錯(cuò),從而糾正之。例如碼字0010101傳輸中發(fā)生一位錯(cuò),在接收端收到的為0011101,代入監(jiān)督關(guān)系式可算得S2=0、S1=1和S0=1,由表2.1可查得S2S1S0=011對應(yīng)于a3錯(cuò),因而可將0011101糾正為00101010。
上述海明碼的編碼效率為4/7。若K=7,按2r>=k+r+1可算得r至少為4,此時(shí)編碼.效率為7/11?？梢?信息位位數(shù)越多時(shí)編碼效率就越高
海明碼是由R.HmIMI1ing在1950年首次提出的,它是一種可以糾正一位差錯(cuò)的編碼。
可以借用簡單奇偶校驗(yàn)碼的生成原理來說明海明碼的構(gòu)造方法。若k(=n-1)位信息位an-1an-2…a1加上一位偶校驗(yàn)位a0,構(gòu)成一個(gè)n位的碼字an-1an-2...a1a0,則在接收端校驗(yàn)時(shí),可按關(guān)系式
S=an-1+an-2+…+a1+a0
來計(jì)算。若求得S=0,則表示元錯(cuò);若S=1,則有錯(cuò)。上式可稱為監(jiān)督關(guān)系式,S稱為校.正因子。.在奇偶校驗(yàn)情況下,只有一個(gè)監(jiān)督關(guān)系式和一個(gè)校正因子,其取值只有0或1兩種情.況,分別代表元錯(cuò)和有錯(cuò)兩種結(jié)果,還不能指出差錯(cuò)所在的位置。不難設(shè)想,若增加冗余位,也即相應(yīng)地增加了監(jiān)督關(guān)系式和校正因子,就能區(qū)分更多的情況。如果有兩個(gè)校正因子.
S1和S0,則S1S0取值就有00、01、10或11四種可能的組合,也即能區(qū)分四種不同的情況。若其中一種取值用于表示無錯(cuò)(如00),則另外三種(01、10及11)便可以用來指出.不同情況的差錯(cuò),從而可以進(jìn)一步區(qū)分出是哪一位錯(cuò)。
設(shè)信息位為k位,增加r位冗余位,構(gòu)成一個(gè)n=k+r位的碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分元錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò),則要求滿足以下關(guān)系式:
2r>=n+1 或 2r>=k+r+1
以k=4為例來說明,則要滿足上述不等式,必須r>=3。假設(shè)取r=3,則n=k+r=7,即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0,構(gòu)成7位碼字a6a5a4a3a2a1a0,其中a2、a1和a0分別由4位信息位中某幾位半加得到,在校驗(yàn)時(shí),a2、a1和a0就分別和這些位半.加構(gòu)成三個(gè)不同的監(jiān)督關(guān)系式。在無錯(cuò)時(shí),這三個(gè)關(guān)系式的值S2、S1和S0全為"0"。若a2錯(cuò),則S2=1,而S1=S0=0;若a1錯(cuò),則S1=1,而S2=S0=0;若a0錯(cuò),則s0=1,而S2=S1=0。S2、S1和S0這三個(gè)校正因子的其它4種編碼值可用來區(qū)分a3、a4、a5、a6中的一位錯(cuò),其對應(yīng)關(guān)系如表2.1。當(dāng)然,也可以規(guī)定成另外的對應(yīng)關(guān)系,這并不影響討論的一般性。
表2.1 S2 S1 S0 值與錯(cuò)碼位置的對應(yīng)關(guān)系
S2 S1 S0 000 001 010 100 011 101 110 111
錯(cuò)碼位置 無錯(cuò) a0 a1 a2 a3 a4 a5 a6
由表可見,a2、a4、a5或a6的一位錯(cuò)都應(yīng)使S2=1,由此可以得到監(jiān)督關(guān)系式..
S2=a2+a4+a5+a6....
同理可得:S1=a1+a3+a5+a6..
S0=a0+a3+a4+a6
在發(fā)送端編碼時(shí),信息位a6、a5、a4和句的值取決于輸入信號,它們在具體的應(yīng)用中有l(wèi)確定的值。冗余位電、a1和ao的值應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系式來確定,使上述三式l中的S2、S1和S0取值為零,即
a2+a4+a5+a6=0
a1+a3+a5+a6=0
a0+a3+a4+a6=0
由此可求得:
a2=a4+a5+a6
a1=a3+a5+a6
a0=a3+a4+a6
已知信息位后,按上述三式即可算出各冗余位。對于本例來說,各種信息位算出的冗余位如表2.2所示。
表2.2 由信息位算得海明碼冗余位
信息位 冗余位 信息位 冗余位
a6a5a4a3 a2a1a0 a6a5a4a3 a2a1a0
0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111
在接收端收到每個(gè)碼字后,按監(jiān)督關(guān)系式算出S2、S1和S0,若它們?nèi)珵?0",則認(rèn)為無錯(cuò);若不全為"0",在一位錯(cuò)的情況下,可查表2.1來判定是哪一位錯(cuò),從而糾正之。例如碼字0010101傳輸中發(fā)生一位錯(cuò),在接收端收到的為0011101,代入監(jiān)督關(guān)系式可算得S2=0、S1=1和S0=1,由表2.1可查得S2S1S0=011對應(yīng)于a3錯(cuò),因而可將0011101糾正為00101010。
上述海明碼的編碼效率為4/7。若K=7,按2r>=k+r+1可算得r至少為4,此時(shí)編碼.效率為7/11?？梢?信息位位數(shù)越多時(shí)編碼效率就越高