對海明碼的理解重點講義

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

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

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

4、 表3位置序號邏輯關(guān)系123456789101112檢測比特名(1)A0A1A2A3A4A5A6A7A8A9A10A11校正因子校驗位分 布(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的順序給二進數(shù)制位串各位上的比特啟名

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

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

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

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

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

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

11、11的錯誤，并在印證表里填上當(dāng)S3 S2 S1 S0=1100時，指示A11錯誤。以便對這些可能發(fā)生的錯誤做到直接印證。三、 一個錯兒影響三個S假設(shè)第7位A6在傳輸中由“1”變成了“0”，導(dǎo)致接收方在驗算時S0變成了“1”， S1變成了“1” S2變成了“1”.對照表3看，這個錯誤發(fā)生過程就好似是這樣：“一枚火箭1變0，分出三個一模一樣的彈頭A6，擊中三個不同的目標S0 、S1和S2”。找錯過程正相反：從被破壞的三個不同的目標S0 、S1和S2，找三個一模一樣的彈頭A6，進而找出錯比特值0。糾錯：把A6由“0”改成“1”。并在印證表里填上當(dāng)S3 S2 S1 S0=0111時，指示A6錯誤。按以

12、上方法，我們可以發(fā)現(xiàn)和糾正第11位A10的錯誤，并在印證表里填上當(dāng)S3 S2 S1 S0=1011時，指示A10錯誤.用一、二、三所準備的印證表項制表如下：印證表 表4S3 S2 S1 S0000100100011010001010110出錯A0A1A2A3A4A5S3 S2 S1 S0011110001001101010111100出錯A6A7A8A9A10A11如果在傳輸中同時發(fā)生兩個錯誤，就很不好辦。例如，A0錯變?yōu)?，A1也錯變?yōu)?，接收方在驗算時發(fā)現(xiàn)S1= S0=1，如果按印證表查對則判為0011 A2錯誤，結(jié)果會造成錯上加錯的情形，如同法官錯判了好人，放走了原兇一樣。為避免此種情況發(fā)生還是應(yīng)該用印