海明校驗(yàn)碼

　　這是由Richard Hamming于1950年提出、目前還被廣泛采用的一種很有效的校驗(yàn)方法，是只要增加少數(shù)幾個(gè)校驗(yàn)位，就能檢測出二位同時(shí)出錯(cuò)、亦能檢測出一位出錯(cuò)并能自動(dòng)恢復(fù)該出錯(cuò)位的正確值的有效手段，后者被稱為自動(dòng)糾錯(cuò)。它的實(shí)現(xiàn)原理，是在k個(gè)數(shù)據(jù)位之外加上r個(gè)校驗(yàn)位，從而形成一個(gè)k+r位的新的碼字，使新的碼字的碼距比較均勻地拉大。把數(shù)據(jù)的每一個(gè)二進(jìn)制位分配在幾個(gè)不同的偶校驗(yàn)位的組合中，當(dāng)某一位出錯(cuò)后，就會(huì)引起相關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化，這不但可以發(fā)現(xiàn)出錯(cuò)，還能指出是哪一位出錯(cuò),為進(jìn)一步自動(dòng)糾錯(cuò)提供了依據(jù)。

　　假設(shè)為k個(gè)數(shù)據(jù)位設(shè)置r個(gè)校驗(yàn)位，則校驗(yàn)位能表示2^r個(gè)狀態(tài)，可用其中的一個(gè)狀態(tài)指出 "沒有發(fā)生錯(cuò)誤"，用其余的2 ^r -1個(gè)狀態(tài)指出有錯(cuò)誤發(fā)生在某一位，包括k個(gè)數(shù)據(jù)位和r個(gè)校驗(yàn)位，因此校驗(yàn)位的位數(shù)應(yīng)滿足如下關(guān)系:

　　　　　2^r ≥ k + r + 1 (2.7)

　　如要能檢出與自動(dòng)校正一位錯(cuò)，并能同時(shí)發(fā)現(xiàn)兩位錯(cuò)，此時(shí)校驗(yàn)位的位數(shù)r和數(shù)據(jù)位的位數(shù)k應(yīng)滿足下述關(guān)系:
　　　　　
　　　　　2^r-1 ≥ k + r (2.8)

　　按上述不等式，可計(jì)算出數(shù)據(jù)位k與校驗(yàn)位r的對應(yīng)關(guān)系，如表2.2所示。

　　設(shè)計(jì)海明碼編碼的關(guān)鍵技術(shù)，是合理地把每個(gè)數(shù)據(jù)位分配到r個(gè)校驗(yàn)組中，以確保能發(fā)現(xiàn)碼字中任何一位出錯(cuò)；若要實(shí)現(xiàn)糾錯(cuò)，還要求能指出是哪一位出錯(cuò)，對出錯(cuò)位求反則得到該位的正確值。例如，當(dāng)數(shù)據(jù)位為3位（用D3 D2 D1表示）時(shí)，檢驗(yàn)位應(yīng)為4位（用P4 P3 P2 P1表示）?？赏ㄟ^表2.3表示的關(guān)系，完成把每個(gè)數(shù)據(jù)位劃分在形成不同校驗(yàn)位的偶校驗(yàn)值的邏輯表達(dá)式中。

表2.3 校驗(yàn)位與數(shù)據(jù)位的對應(yīng)關(guān)系


　　在P1、P2、P3、P4豎列相應(yīng)行分別填1，
　　在該4列的低3橫行其它位置分別填0，
　　在最頂橫行的每個(gè)尚空位置都分別填1。
　　若只看低3橫行，右4豎列的3個(gè)bit的組合值分別為十進(jìn)制的1、2、4、0，則分配 D1 D2 D3列的組合值為3 5 6，保證低3橫行各豎列的編碼值各不相同。

　　表中D3 D2 D1為三位數(shù)據(jù)位，P4 P3 P2 P1為四位校驗(yàn)位。其中低三位中的每一個(gè)校驗(yàn)位P3 P2 P1的值，都是用三個(gè)數(shù)據(jù)位中不同的幾位通過偶校驗(yàn)運(yùn)算規(guī)則計(jì)算出來的。其對應(yīng)關(guān)系是：對P_i（i的取值為1~3），總是用處在Pi取值為1的行中的、用1標(biāo)記出來的數(shù)據(jù)位計(jì)算該P(yáng)_i的值。最高一個(gè)校驗(yàn)位P4，被稱為總校驗(yàn)位，它的值，是通過對全部三個(gè)數(shù)據(jù)位和其它全部校驗(yàn)位（不含P4本身）執(zhí)行偶校驗(yàn)計(jì)算求得的。

　　形成各校驗(yàn)位的值的過程叫做編碼，按剛說明的規(guī)則，4個(gè)校驗(yàn)位所用的編碼方程為：
　　　

　　由多個(gè)數(shù)據(jù)位和多個(gè)校驗(yàn)位組成的一個(gè)碼字，將作為一個(gè)數(shù)據(jù)單位處理，例如被寫入內(nèi)存或被傳送走。之后，在執(zhí)行內(nèi)存讀操作或在數(shù)據(jù)接收端，則可以對得到的碼字，通過偶校驗(yàn)來檢查其合法性，通常稱該操作過程為譯碼，所用的譯碼方程為：


　　譯碼方程和編碼方程的對應(yīng)關(guān)系很簡單。譯碼方程，是用一個(gè)校驗(yàn)碼和形成這個(gè)校驗(yàn)碼的編碼方程執(zhí)行異或，實(shí)際上是又一次執(zhí)行偶校驗(yàn)運(yùn)算。通過檢查四個(gè)S的結(jié)果，可以實(shí)現(xiàn)檢錯(cuò)糾錯(cuò)的的目的。實(shí)際情況是，當(dāng)譯碼求出來的S4、S3、S2、S1的得值與表2.3中的那一列的值相同，就說明是哪一位出錯(cuò)；故人們又稱表2.3為出錯(cuò)模式表。若出錯(cuò)的是數(shù)據(jù)位，對其求反則實(shí)現(xiàn)糾錯(cuò)；若出錯(cuò)的是校驗(yàn)位則不必理睬。舉例如下：

　　任何一位（含數(shù)據(jù)位、校驗(yàn)位）均不錯(cuò)，則四個(gè)S都應(yīng)為0值；
　　任何單獨(dú)一位數(shù)據(jù)位出錯(cuò)，四個(gè)S中會(huì)有三個(gè)為1；如D3錯(cuò)，則S4 S3 S2 S1為1110。
　　若單獨(dú)一位校驗(yàn)位出錯(cuò)，四個(gè)S中會(huì)有一個(gè)或兩個(gè)為1；如P1錯(cuò)，S4 S3 S2 S1為1001，如P4錯(cuò)，S4 S3 S2 S1為1000。
　　任何兩位（含數(shù)據(jù)位、校驗(yàn)位）同時(shí)出錯(cuò)，S4一定為0，而另外三個(gè)S位一定不全為0，此時(shí)只知道是兩位同時(shí)出錯(cuò)，但不能確定是哪兩位出錯(cuò)，故已無法糾錯(cuò)。如D1、 P2出錯(cuò)，會(huì)使S4 S3 S2 S1為0001。請注意，S4的作用在于區(qū)分是奇數(shù)位出錯(cuò)還是偶數(shù)位出錯(cuò)，S4為1是奇數(shù)位錯(cuò)，為0是無錯(cuò)或偶數(shù)位錯(cuò)。這不僅為發(fā)現(xiàn)兩位錯(cuò)所必需，也是為確保能發(fā)現(xiàn)并改正一位錯(cuò)所必需的。若不設(shè)置S4，某種兩位出錯(cuò)對幾個(gè)S的影響與單獨(dú)另一位出錯(cuò)可能是一樣的（不必花費(fèi)精力推敲），此時(shí)若不加以區(qū)分，簡單地按一位出錯(cuò)自動(dòng)完成糾錯(cuò)處理反而會(huì)幫倒忙。