海明校驗碼

海明校驗碼

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

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

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

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

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

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

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


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

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

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

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


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

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