對海明碼的理解

1、對海明碼的理解海明碼是一種多重(復(fù)式)奇偶檢錯(cuò)系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯(cuò)和糾錯(cuò)。用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這種奇偶位被編在傳輸碼字的特定位置上。實(shí)現(xiàn)得合適時(shí)，這個(gè)系統(tǒng)對于錯(cuò)誤的數(shù)位無論是原有信息位中的，還是附加校驗(yàn)位中的都能把它分離出來。一個(gè)n位二進(jìn)制數(shù)位串在傳輸過程中哪一位都有出錯(cuò)的可能，也就是說有n個(gè)發(fā)生錯(cuò)誤的可能性。針對此情況，如果發(fā)送方只抽出其中一位制置奇偶校驗(yàn)位值，以便對其它位進(jìn)行偶校驗(yàn)或奇校驗(yàn)，雖然也能檢錯(cuò)，但無法確定錯(cuò)碼的位置，不能糾錯(cuò)。如果發(fā)送方抽出其中r位（放在1，2，4，8，16位上）,給每個(gè)位制置奇偶校驗(yàn)位值，

2、以便對從其它位中選擇的有差異的r個(gè)位組進(jìn)行偶校驗(yàn)或奇校驗(yàn)，這樣，就能用含r個(gè)校驗(yàn)位值的邏輯組合（其所在位置可以不連續(xù)，但是，其在邏輯上是連續(xù)的）所衍生出的2r種狀態(tài)對可能發(fā)生的錯(cuò)誤進(jìn)行相應(yīng)范圍的檢測。進(jìn)一步思考：如果讓2r種可能發(fā)生的狀態(tài)中除去一種狀態(tài)反映整個(gè)位串傳輸正確外，剩下的2r-1種狀態(tài)一一對應(yīng)地反映位串中可能發(fā)生的n種錯(cuò)誤，那么，對r會(huì)有多大的數(shù)量要求呢？顯然，r應(yīng)滿足下列關(guān)系式：2r-1=n (1)這樣，r個(gè)校驗(yàn)位所衍生出的2r種狀態(tài)才能覆蓋可能產(chǎn)生的n種錯(cuò)誤。每種錯(cuò)誤發(fā)生時(shí)才不至于漏檢。從n中扣出r個(gè)校驗(yàn)位n-r=k，這k個(gè)位是信息位。n=k+r，代入（1）式得：2r-1= k+

3、r (2)移項(xiàng)得：2r- r= k+1 (3)按(3)式進(jìn)行試算（試算不包括”取最小值） 表1r12345678k014112657120247根據(jù)經(jīng)驗(yàn) 表2r12345678k01245111226275758120121247此即r以其所衍生出的狀態(tài)能覆蓋的信息位數(shù)量。反過來，從k的數(shù)量，可以倒推需要多少校驗(yàn)位對其進(jìn)行檢測。知道了信息位數(shù)量與校驗(yàn)位數(shù)量的關(guān)系后，怎樣編海明碼呢？用一道例題加以說明。例題現(xiàn)有8位二進(jìn)制數(shù)信息位串10011101等待傳輸，問怎樣將海明校驗(yàn)位編入以資校驗(yàn)？根據(jù)前述，8個(gè)信息位要有4個(gè)校驗(yàn)位來檢測，于是整個(gè)位串長就是8+4=12位。 表3位置序號(hào)邏輯關(guān)系123456

4、789101112檢測比特名(1)A0A1A2A3A4A5A6A7A8A9A10A11校正因子校驗(yàn)位分 布(2)A0A1A3A7信息位分 布(3)A2A4A5A6A8A9A10A11信 息位 值(4)10011101 監(jiān) 督 關(guān) 系(5)A0=1A2A4A6A8A10S0(6)A1=1A2A5A6A9A10S1(7)A3=0A4A5A6A11S2(8) A7=1A8A9A10A11S3海 明碼 值(9) 111000111101S說明：表3表示海明碼內(nèi)部的邏輯關(guān)系。它反映了海明碼是按什么樣的邏輯被制造出來的。(1) 按112的順序給二進(jìn)數(shù)制位串各位上的比特啟名。(2) 把1，2，4，8位（即2

5、i,i=0,1,2位）安上奇偶校驗(yàn)比特的名。(3) 把非2i位安上信息比特的名。(4) 按名位顯示10011101，如，A2的值是10011101的第一個(gè)“1”，依此順推。(5) A0的校驗(yàn)對象：每跳1位拉入1個(gè)對象，直到盡頭。校驗(yàn)對象的值模2加之和為A0的值。(6) A1的校驗(yàn)對象：它旁邊的A2，而后每跳2位拉入2個(gè)對象，直到盡頭。校驗(yàn)對象的值的模2加之和為A1的值。(7) A3的校驗(yàn)對象：它旁邊的A4，A5 ，A6 ，而后每跳4位拉入4個(gè)對象，直到盡頭。校驗(yàn)對象的值的模2加之和為A3的值。(8) A7的校驗(yàn)對象：它旁邊的A8，A9 ，A10 ，A11，已到盡頭。校驗(yàn)對象的值的模2加之和為A

6、7的值。(5)(6)(7)(8)為什么采取這樣的邏輯方法（以2i位校驗(yàn)非2i位）選校驗(yàn)對象？為的是標(biāo)準(zhǔn)統(tǒng)一、好記，便于發(fā)送方和接收方按同一個(gè)規(guī)則計(jì)算校正因子S，從而便于接收方檢錯(cuò)糾錯(cuò)。故此說明。(9) 將各校驗(yàn)位的值按相應(yīng)位插入，形成海明碼。(10) S0是A0和A0的校驗(yàn)對象模2加之和，為0；S1是A1和A1的校驗(yàn)對象模2加之和，為0；S2是A3和A3的校驗(yàn)對象模2加之和，為0；S3是A7和A7的校驗(yàn)對象模2加之和，為0。如果發(fā)生了不為0則表明：不是校驗(yàn)者出錯(cuò)就是被校驗(yàn)者出錯(cuò)。這個(gè)海明碼一個(gè)12位的二進(jìn)數(shù)制位串中，隱含著可資互相印證的邏輯關(guān)系：一是校驗(yàn)與被校驗(yàn)（反過來是生成被生成）的關(guān)系被校

7、驗(yàn)者對校驗(yàn)者也有產(chǎn)生被產(chǎn)生作用。因?yàn)椴扇∨夹ｒ?yàn)法，校驗(yàn)位值與被校驗(yàn)的信息位值群之奇偶性有同一性。當(dāng)這個(gè)同一性被破壞時(shí)就會(huì)想到讓被校驗(yàn)的信息位值群與校驗(yàn)位值互相印證；二是校正因子與偶校驗(yàn)雙方的關(guān)系；三是按取位數(shù)量不同跳拉校驗(yàn)對象法組成的校驗(yàn)組之間的關(guān)系。正是這些關(guān)系為檢錯(cuò)糾錯(cuò)提供了基礎(chǔ)。接收方收到海明碼后，按編碼規(guī)則計(jì)算S，若S3= S2= S1= S0=0，則說明傳輸無誤。反之，只要其中有一個(gè)為1 便說明傳輸有誤。 錯(cuò)誤分析：一、 一個(gè)錯(cuò)兒影響一個(gè)S假設(shè)第一位A0在傳輸中由“1”變成了“0”，導(dǎo)致接收方在驗(yàn)算時(shí)S0由“0”變成了“1”這時(shí)接收方便知如表3的第（5）行所示的邏輯關(guān)系中出了錯(cuò)值。但

8、到底是A0錯(cuò)了還是第（5）行里的其他位值出了錯(cuò)？尚不能確定，要分析。這時(shí)如果S3=S2= S1=0就為找錯(cuò)提供了印證分析基礎(chǔ)：因?yàn)镾1=0，印證了A2、 A10傳輸無誤；因?yàn)镾2=0，印證了A4、 A6 傳輸無誤；因?yàn)镾3=0，印證了A8、 A10傳輸無誤；合計(jì)印證了A2、 A4、A6、A8、A10傳輸無誤，而這正說明（5）行里的信息位值群正確，從而擠認(rèn)出A0錯(cuò)了。糾錯(cuò)：把A0由“1”改成“0”。為了以后省卻印證分析的麻煩，不妨對這種12位海明碼制定一個(gè)固定印證表指示：當(dāng)S3 S2 S1 S0=0001時(shí)，A0錯(cuò)誤。A1、 A3 、A7傳輸錯(cuò)誤均可用此印證分析方法找出和糾正，可定一個(gè)固定印證表

9、指示：當(dāng)S3 S2 S1 S0=0010時(shí)，A1錯(cuò)誤；當(dāng)S3 S2 S1 S0=0100時(shí)，A3錯(cuò)誤；當(dāng)S3 S2 S1 S0=1000時(shí)，A1錯(cuò)誤。二、 一個(gè)錯(cuò)兒影響兩個(gè)S 假設(shè)第3位A2在傳輸中由“1”變成了“0”，導(dǎo)致接收方在驗(yàn)算時(shí)S0變成了“1”， S1變成了“1”。對照表3所示的橫豎邏輯關(guān)系看，這個(gè)錯(cuò)誤發(fā)生過程就好似是這樣：“一枚火箭1變0（在表3第3列底部），分出兩個(gè)一模一樣的彈頭A2（豎看），擊中兩個(gè)不同的目標(biāo)S0和S1（橫看）”。找錯(cuò)過程正相反：從被破壞的兩個(gè)不同的目標(biāo)S0和S1，找兩個(gè)一模一樣的彈頭A2，進(jìn)而找出錯(cuò)比特值0。當(dāng)然，這是循著邏輯關(guān)系找錯(cuò)，（表3只是說明了邏輯關(guān)系

10、）。不應(yīng)理解成循表找錯(cuò)。糾錯(cuò)：把A2由“0”改成“1”。并在印證表里填上當(dāng)S3 S2 S1 S0=0011時(shí)，A2錯(cuò)誤。按以上方法，我們同樣可以發(fā)現(xiàn)和糾正第5位A4的錯(cuò)誤，并在印證表里填上當(dāng)S3 S2 S1 S0=0101時(shí)，指示A4錯(cuò)誤；可以發(fā)現(xiàn)和糾正第6位A5的錯(cuò)誤，并在印證表里填上當(dāng)S3 S2 S1 S0=0110時(shí)，指示A5錯(cuò)誤；可以發(fā)現(xiàn)和糾正第9位A8的錯(cuò)誤，并在印證表里填上當(dāng)S3 S2 S1 S0=1001時(shí)，指示A8錯(cuò)誤；可以發(fā)現(xiàn)和糾正第10位A9的錯(cuò)誤，并在印證表里填上當(dāng)S3 S2 S1 S0=1010時(shí)，指示A9錯(cuò)誤；可以發(fā)現(xiàn)和糾正第12位A11的錯(cuò)誤，并在印證表里填上當(dāng)S3

11、 S2 S1 S0=1100時(shí)，指示A11錯(cuò)誤。以便對這些可能發(fā)生的錯(cuò)誤做到直接印證。三、 一個(gè)錯(cuò)兒影響三個(gè)S假設(shè)第7位A6在傳輸中由“1”變成了“0”，導(dǎo)致接收方在驗(yàn)算時(shí)S0變成了“1”， S1變成了“1” S2變成了“1”.對照表3看，這個(gè)錯(cuò)誤發(fā)生過程就好似是這樣：“一枚火箭1變0，分出三個(gè)一模一樣的彈頭A6，擊中三個(gè)不同的目標(biāo)S0 、S1和S2”。找錯(cuò)過程正相反：從被破壞的三個(gè)不同的目標(biāo)S0 、S1和S2，找三個(gè)一模一樣的彈頭A6，進(jìn)而找出錯(cuò)比特值0。糾錯(cuò)：把A6由“0”改成“1”。并在印證表里填上當(dāng)S3 S2 S1 S0=0111時(shí)，指示A6錯(cuò)誤。按以上方法，我們可以發(fā)現(xiàn)和糾正第11位A10的錯(cuò)誤，并在印證表里填上當(dāng)S3 S2 S1 S0=1011時(shí)，指示A10錯(cuò)誤.用一、二、三所準(zhǔn)備的印證表項(xiàng)制表如下：印證表 表4S3 S2 S1 S0000100100011010001010110出錯(cuò)A0A1A2A3A4A5S3 S2 S1 S0011110001001101010111100出錯(cuò)A6A7A8A9A10A11如果在傳輸中同時(shí)發(fā)生兩個(gè)錯(cuò)誤，就很不好辦。例如，A0錯(cuò)變?yōu)?，A1也錯(cuò)變?yōu)?，接收方在驗(yàn)算時(shí)發(fā)現(xiàn)S1= S0=1，如果按印證表查對則判為0011 A2錯(cuò)誤，結(jié)果會(huì)造成錯(cuò)上加錯(cuò)的情形，如同法官錯(cuò)判了好人，放走了原兇一樣。為避免此種情況發(fā)生還是應(yīng)該用印