對海明碼的理解

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位上），給

2、每個(gè)位制置奇偶校驗(yàn)位值，以便對從其它位中選擇的有差異的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會有多大的數(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è)位是信

3、息 位。n=k+r，代入（1）式得：2r-1>= k+r (2移項(xiàng)得：2r- r>= k+1 (3按（3式進(jìn)行試算（試算不包括 ">”最小值）表101245111226275758120121247r12345678k014112657120247根據(jù)經(jīng)驗(yàn)表2r12345678此即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、位串長就是8+4=12位。表34個(gè)校驗(yàn)位來檢測，于是整個(gè)位置序1 2 3 4 5 6 79 10 11 12 檢邏比特名輯關(guān)系(AAAAAAAAAA9A1A1101234567801校驗(yàn)位(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位)安上奇偶校驗(yàn)比特 的名。(3把非2i位安上信息比特的名。(4按名位顯示 10011101，如，A2的值

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

6、、好記，便于發(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)系一一被校驗(yàn)者對校驗(yàn)者也 有產(chǎn)生被產(chǎn)生作用。因?yàn)椴扇∨夹ｒ?yàn)法，校驗(yàn)位值與 被校驗(yàn)的信息位

7、值群之奇偶性有同一性。當(dāng)這個(gè)同一 性被破壞時(shí)就會想到讓被校驗(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ò) 值。但到底是 A0錯(cuò)了還是第（5）行里的其他位值 出了錯(cuò)？

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

9、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只是說明了邏

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

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

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