對海明碼的理解

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

2、每個位制置奇偶校驗位值，以便對從其它位中選擇的有差異的r個位組進(jìn)行偶校驗或奇校驗，這樣，就能用含 r個校驗位值的邏輯組合（其所在位置 可以不連續(xù)，但是，其在邏輯上是連續(xù)的）所衍生出的2r種狀態(tài)對可能發(fā)生的錯誤進(jìn)行相應(yīng)范圍的檢測。進(jìn)一步思考： 如果讓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個位是信

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

4、位串長就是8+4=12位。表34個校驗位來檢測，于是整個位置序1 2 3 4 5 6 79 10 11 12 檢邏比特名輯關(guān)系(AAAAAAAAAA9A1A1101234567801校驗位(A AAA2分布20 137信息位 (3A AAA A A9 A1 A1A1(6(7(8=1A1S1=1A1=0A1A1說明：表3表示海明碼內(nèi)部的邏輯關(guān)系。它反映了海明碼是按什 么樣的邏輯被制造出來的。(1按112的順序給二進(jìn)數(shù)制位串各位上的比特啟名。(2把1, 2, 4, 8位(即2i,i=0,1,2位)安上奇偶校驗比特 的名。(3把非2i位安上信息比特的名。(4按名位顯示 10011101，如，A2的值

5、是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，已到盡 頭。校驗對象的值的模2加之和為A7的值。(5(6(7(8為什么采取這樣的邏輯方法(以 2i位校驗 非2i位)選校驗對象？為的是標(biāo)準(zhǔn)統(tǒng)一

6、、好記，便于發(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位的二進(jìn)數(shù)制位串中，隱含著可資互相印證的邏輯關(guān)系：一是校驗與被校驗(反 過來是生成被生成)的關(guān)系一一被校驗者對校驗者也 有產(chǎn)生被產(chǎn)生作用。因為采取偶校驗法，校驗位值與 被校驗的信息位

7、值群之奇偶性有同一性。當(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的第（5）行所示的邏輯關(guān)系中出了錯 值。但到底是 A0錯了還是第（5）行里的其他位值 出了錯？

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

9、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 （豎看），擊中兩個不同的目標(biāo)一一S0和S1 （橫看）”。找錯過程正相反：從被 破壞的兩個不同的目標(biāo) 一一S0和S1，找兩個一模一樣的彈頭一一A2,進(jìn)而找出錯比特值 一一0。當(dāng)然，這是循著邏輯關(guān) 系找錯，（表3只是說明了邏

10、輯關(guān)系）。不應(yīng)理解成循表找 錯。糾錯：把A2由“0改成“ 1”并在印證表里填上當(dāng) S3 s2 si sO=ooii 時，a2 錯誤。按以上方法，我們同樣可以發(fā)現(xiàn)和糾正第5位A4的錯誤，并在印證表里填上當(dāng)s3 s2 si s0=0ioi時，指示a4錯誤；可以發(fā)現(xiàn)和糾正第6位a5的錯誤，并在印證表里填上當(dāng)s3 s2 si s0=0iio時，指示a5錯誤；可以發(fā)現(xiàn)和糾 正第9位A8的錯誤，并在印證表里填上當(dāng)S3 s2 sis0=i00i時，指示A8錯誤；可以發(fā)現(xiàn)和糾正第 io位A9的 錯誤，并在印證表里填上當(dāng)s3 s2 si s0=i0io時，指示a9錯誤；可以發(fā)現(xiàn)和糾正第i2位Aii的錯誤，并在印

11、證表里填上當(dāng)s3 s2 si s0=iio0時，指示Aii錯誤。以便對這些 可能發(fā)生的錯誤做到直接印證。三、一個錯兒影響三個 s假設(shè)第7位A6在傳輸中由“i變成了 “0”導(dǎo)致接收 方在驗算時so變成了 “i” si變成了 “i” 2變成了 a丄力i .對照表3看，這個錯誤發(fā)生過程就好似是這樣：一枚火箭一一i變0,分出三個一模一樣的彈頭 一一A6,擊 中三個不同的目標(biāo) 一一s0、si和s2”。找錯過程正相反：從被破壞的三個不同的目標(biāo) 一一S0、S1和s2,找三個一模 一樣的彈頭一一a6,進(jìn)而找出錯比特值 一一0。糾錯：把a(bǔ)6由“0改成“ 1”并在印證表里填上當(dāng)s3 s2 si s0=oiii時，

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