海明校驗(yàn)碼的原理詳解

1、海明校驗(yàn)碼的原理詳解2006年12月27日 星期三 10:57海明碼是一種多重(復(fù)式)奇偶檢錯(cuò)系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯(cuò)和糾錯(cuò)。用在海明碼中的全部傳輸碼字是由原來(lái)的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這種奇偶位被編在傳輸碼字的特定位置上。實(shí)現(xiàn)得合適時(shí)，這個(gè)系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無(wú)論是原有信息位中的，還是附加校驗(yàn)位中的都能把它分離出來(lái)。 推導(dǎo)并使用長(zhǎng)度為m位的碼字的海明碼，所需步驟如下： 1、確定最小的校驗(yàn)位數(shù)k，將它們記成D1、D2、Dk，每個(gè)校驗(yàn)位符合不同的奇偶測(cè)試規(guī)定。 2、原有信息和k個(gè)校驗(yàn)位一起編成長(zhǎng)為m+k位的新碼字。選擇k校驗(yàn)位（0或1）以

2、滿足必要的奇偶條件。 3、對(duì)所接收的信息作所需的k個(gè)奇偶檢查。 4、如果所有的奇偶檢查結(jié)果均為正確的，則認(rèn)為信息無(wú)錯(cuò)誤。 如果發(fā)現(xiàn)有一個(gè)或多個(gè)錯(cuò)了，則錯(cuò)誤的位由這些檢查的結(jié)果來(lái)唯一地確定。 校驗(yàn)位數(shù)的位數(shù) 推求海明碼時(shí)的一項(xiàng)基本考慮是確定所需最少的校驗(yàn)位數(shù)k?？紤]長(zhǎng)度為m位的信息，若附加了k個(gè)校驗(yàn)位，則所發(fā)送的總長(zhǎng)度為m+k。在接收器中要進(jìn)行k個(gè)奇偶檢查，每個(gè)檢查結(jié)果或是真或是偽。這個(gè)奇偶檢查的結(jié)果可以表示成一個(gè)k位的二進(jìn)字，它可以確定最多2k種不同狀態(tài)。 這些狀態(tài)中必有一個(gè)其所有奇偶測(cè)試試都是真的，它便是判定信息正確的條件。于是剩下

3、的（2k-1）種狀態(tài)，可以用來(lái)判定誤碼的位置。于是導(dǎo)出下一關(guān)系： 2k-1m+k 碼字格式 從理論上講，校驗(yàn)位可放在任何位置，但習(xí)慣上校驗(yàn)位被安排在1、2、4、8、的位置上。 圖5列出了m=4，k=3時(shí)，信息位和校驗(yàn)位的分布情況。 碼字位置B1B2B3B4B5B6B7校驗(yàn)位xxx信息位xxxx復(fù)合碼字P1P2D1P3D2D3D4圖5 海明碼中校驗(yàn)位和信息位的定位 校驗(yàn)位的確定 下面為我增加，意在提出編碼方法以助理解（但編碼是否主要標(biāo)準(zhǔn)不可知）每行的值等于數(shù)值為1的各位碼相異或。如m=4,k=3.數(shù)據(jù)位前三行，校驗(yàn)位

4、為后三行。即A=p1D1D3D4=0 得P1=D1D3D4B=P2D2D3D4=0 得P2=D2D3D4C=P3D1D2D3D4=0 得P3=D1D2D3D4           以下計(jì)算訪求同下k個(gè)校驗(yàn)位是通過(guò)對(duì)m+k位復(fù)合碼字進(jìn)行奇偶校驗(yàn)而確定的。其中：P1位負(fù)責(zé)校驗(yàn)海明碼的第1、3、5、7、（P1、D1、D2、D4、）位，（包括P1自己）P2負(fù)責(zé)校驗(yàn)海明碼的第2、3、6、7、（P2、D1、D3、D4、）位，（包括P2自己）P3負(fù)責(zé)校驗(yàn)海明碼的第4、5

5、、6、7、（P3、D2、D3、D4、）位，（包括P3自己）對(duì)m=4，k=3，偶校驗(yàn)的例子，只要進(jìn)行式次偶性測(cè)試。這些測(cè)試（以A、B、C表示）在圖6所示各位的位置上進(jìn)行。奇偶條件碼 字 位 置1234567ABCx   x  xx   xx  x xxxxx圖6 奇偶校驗(yàn)位置因此可得到三個(gè)校驗(yàn)方程及確定校驗(yàn)位的三個(gè)公式：A=B1B3B5B7=0 得P1=D1D2D4B=B2B3B6B7=0 得P2=D1D3D4C=B4B5B6B

6、7=0 得P3=D2D3D4若四位信息碼為1001，利用這三個(gè)公式可求得三個(gè)校驗(yàn)位P1、P2、P3值。和海明碼， 上面是發(fā)送方的處理在接收方，也可根據(jù)這三個(gè)校驗(yàn)方程對(duì)接收到的信息進(jìn)行同樣的奇偶測(cè)試：A=B1B3B5B7=0；B=B2B3B6B7=0；C=B4B5B5B7=0。若三個(gè)校驗(yàn)方程都成立,即方程式右邊都等于0，則說(shuō)明沒有錯(cuò)。若不成立即方程式右邊不等于0，說(shuō)明有錯(cuò)。從三個(gè)方程式右邊的值，可以判斷那一位出錯(cuò)。例如，如果第3位數(shù)字反了，則C=0(此方程沒有B3），A=B=1（這兩個(gè)方程有B3）?？蓸?gòu)成二進(jìn)數(shù)CBA，以A為最低有效位，則錯(cuò)誤位置就可簡(jiǎn)單地用二進(jìn)數(shù)CBA=01

7、1指出。同樣，若三個(gè)方程式右邊的值為001，說(shuō)明第1位出錯(cuò)。若三個(gè)方程式右邊的值為100，說(shuō)明第4位出錯(cuò)。海明碼的碼距應(yīng)該是3，所以能糾正1位出錯(cuò)。而奇偶校驗(yàn)碼的碼距才是2，只能發(fā)現(xiàn)1位出錯(cuò)，但不能糾正（不知道那一位錯(cuò)）。無(wú)校驗(yàn)的碼距是1，它出任何一位出錯(cuò)后還是合法代碼，所以也就無(wú)法發(fā)現(xiàn)出錯(cuò)。 這是關(guān)于海明碼的經(jīng)典說(shuō)法，即碼距為3，可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)。應(yīng)滿足2k-1m+k。 但在清華的王愛英主編的計(jì)算機(jī)組成與結(jié)構(gòu)（該書已成為國(guó)內(nèi)的權(quán)威）中還提出了一種碼距為4的海明碼，可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)。應(yīng)滿足2(k-1)m+k。 由于王愛英書上對(duì)這兩種概念沒有

8、很仔細(xì)解釋（特別對(duì)碼距為3的海明碼），過(guò)渡很突然。有些書簡(jiǎn)單抄襲時(shí)沒有仔細(xì)消化，所以出現(xiàn)一些概念錯(cuò)。對(duì)于一般碼距為3的海明碼，應(yīng)該是“可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)”，而不是“可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)”。在試題中出現(xiàn)過(guò)類似的錯(cuò)誤。 若四位信息碼為1001，利用這三個(gè)公式可求得三個(gè)校驗(yàn)位P1、P2、P3值。和海明碼，如圖7則表示了信息碼為1001時(shí)的海明碼編碼的全部情況。而圖8中則列出了全部16種信息（D1D2D3D4=00001111）的海明碼。碼字位置B1B2B3B4B5B6B7碼位類型P1P2D1P3D2D3D4信息碼-1-001校驗(yàn)位00-1-編碼后的海明碼0011001圖7 四位信息碼的海明編碼 P1P2D1P3D2D3D40000000