海明校驗碼

將有效信息按某種規律分成若干組，每組安排一個校驗位，做奇偶測試，就能提供多位檢錯信息，以指出最大可能是哪位出錯，從而將其糾正。實質上，海明校驗是一種多重校驗。

它不僅具有檢測錯誤的能力，同時還具有給出錯誤所在準確位置的能力　但是因為這種海明校驗的方法只能檢測和糾正一位出錯的情況。所以如果有多個錯誤，就不能查出了。假設為k個數據位設置r個校驗位，則校驗位能表示2^r個狀態，可用其中的一個狀態指出 "沒有發生錯誤"，用其餘的2 ^r -1個狀態指出有錯誤發生在某一位，包括k個數據位和r個校驗位，因此校驗位的位數應滿足如下關係:

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

如要能檢出與自動校正一位錯，並能同時發現哪位錯，此時校驗位的位數r和數據位的位數k應滿足下述關係:

2^r-1 ≥ k + r (2.8)

按上述不等式，可計算出數據位k與校驗位r的對應關係，如表2.2所示。

表2.2

在海明碼中，位號數（1、2、3、……、n）為2的權值的那些位，即：

1(2^0)、2(2^1)、4(2^2)、8(2^3)、…2^(r-1)位，作為奇偶校驗位，並記作: P1、P2、P3 、P4、…Pr，餘下各位則為有效信息位。例如： N=11（海明碼位數）K=7（數據位數）r=4（校驗位） ，相應海明碼可表示位號為： 1， 2， 3， 4 ，5 ，6， 7， 8， 9 ，10 ，11，校驗位P占第1，2，4，8位，其他位為有效信息位，海明碼中的校驗位分別標示為P1,P2,P3,P4… Pr ,並被信息位中的一至若干位所校驗，其規律是：第i位，由校驗位位號之和等於i的那些校驗位所校驗，如：海明碼的位號為3，它被P1P2（位號分別為1,2）所校驗，海明碼的位號為5，它被P1P3（位號分別為1,4）所校驗。歸併起來: 形成了4個小組，每個小組一個校驗位，校驗位的取值，仍採用奇偶校驗方式確定。

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

表2.3 校驗位與數據位的對應關係

在P1、P2、P3、P4豎列相應行分別填1，

在該4列的低3橫行其它位置分別填0，

在最頂橫行的每個尚空位置都分別填1。

若只看第3橫行，右4豎列的3個bit的組合值分別為十進位的1、2、4、0，則分配 D1 D2 D3列的組合值為3 5 6，保證低3橫行各豎列的編碼值各不相同。

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

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

P4 = D3 D2 D1 P3 P2 P1

P3 = D3 D2

P2 = D3 D1

P1 = D2 D1

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

S4 = P4 D3 D2 D1 P3 P2 P1

S3 = P3 D3 D2

S2 = P2 D3 D1

S1 = P1 D2 D1

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

任何一位（含數據位、校驗位）均不錯，則四個S都應為0值；

任何單獨一位數據位出錯，四個S中會有三個為1；如D3錯，則S4 S3 S2 S1為1110。

若單獨一位校驗位出錯，四個S中會有一個或兩個為1；如P1錯，S4 S3 S2 S1為1001，如P4錯，S4 S3 S2 S1為1000。

任何兩位（含數據位、校驗位）同時出錯，S4一定為0，而另外三個S位一定不全為0，此時只知道是兩位同時出錯，但不能確定是哪兩位出錯，故已無法糾錯。如D1、 P2出錯，會使S4 S3 S2 S1為0001。請注意，S4的作用在於區分是奇數位出錯還是偶數位出錯，S4為1是奇數位錯，為0是無錯或偶數位錯。這不僅為發現兩位錯所必需，也是為確保能發現並改正一位錯所必需的。若不設置S4，某種兩位出錯對幾個S的影響與單獨另一位出錯可能是一樣的（不必花費精力推敲），此時若不加以區分，簡單地按一位出錯自動完成糾錯處理反而會幫倒忙。