你看得懂的海明碼校驗和糾錯原理（二）

     接上篇：http://blog.csdn.net/lycb_gz/article/details/8214961 

    以下内容摘自筆者最新出版的最新著作《深入了解計算機網絡》一書：http://item.jd.com/11165825.html

     本書原始目錄：http://blog.csdn.net/lycb_gz/article/details/8199839

4.    實作校驗和糾錯

    雖然上一步已把各位校驗碼求出來了，但是如何實作檢測出哪一位在傳輸過程中出了差錯呢？（海明碼也隻能檢測并糾正一位錯誤）它又是如何實作對錯誤的位進行糾正呢？其實最關鍵的原因就是海明碼是一個多重校驗碼，也就是碼字中的資訊碼位同時被多個校驗碼進行校驗，然後通過這些碼位對不同校驗碼的關聯影響最終可以找出是哪一位出錯了。

1）海明碼的差錯檢測

    現假設整個碼字一共是18位，根據表5-1可以很快得出，其中有5位是校驗碼，再根據本節前面介紹的校驗碼校驗規則可以很快得出各校驗碼所校驗的碼字位，如表5-2所示。

    表5-2  各校驗碼校驗的碼位對照表

      從表中可以得出以下兩個規律：

•      所有校驗碼所在的位是隻由對應的校驗碼進行校驗，如第1位（隻由p1校驗）、第2位（隻由p2校驗）、第4位（隻由p3校驗）、第8位（隻由p4校驗）、第16位（隻由p5校驗），……。也就是這些位如果發生了差錯，影響的隻是對應的校驗碼的校驗結果，不會影響其它校驗碼的校驗結果。這點很重要，如果最終發現隻是一個校驗組中的校驗結果不符，則直接可以知道是對應校驗組中的校驗碼在傳輸過程中出現了差錯。
•    所有資訊碼位均被至少兩個校驗碼進行了校驗，也就是至少校驗了兩次。檢視對應的是哪兩組校驗結果不符，然後根據表5-2就可以很快确定是哪位資訊碼在傳輸過程中出了差錯。

      海明碼校驗的方式就是各校驗碼對它所校驗的位組進行“異或運算”，即：

G1=p1⊕b1⊕b2⊕b4⊕b5⊕……

G2=p2⊕b1⊕b3⊕b4⊕b6⊕b7⊕b10⊕b11⊕……

G3= p3⊕b2⊕b3⊕b4⊕b8⊕b9⊕b10⊕b11⊕……

G4= p4⊕b5⊕b6⊕b7⊕b8⊕b9⊕b10⊕b11⊕……

G5= p5⊕b12⊕b13⊕b14⊕b15⊕b16⊕b17⊕b18⊕b19⊕b20⊕b21⊕b11⊕b23⊕b24⊕b25⊕b26⊕……

    正常情況下（也就是整個碼字不發生差錯的情況下），在采用偶校驗時，各校驗組通過異或運算後的校驗結果均應該是為0，也就是前面所說的G1、G2、G3、G4，……均為0，因為此時1為偶數個，進行異或運算後就是0；而采用奇校驗時，各組校驗結果均應是為1。

    現在舉一個例子來說明，假設傳輸的海明碼為111000111101（一共12位，帶陰影的4位就是校驗碼），從中可以知道它有四個校驗組：G1、G2、G3、G4，然而到達接收端經過校驗後發現隻有G4=1（也就是隻有這組校驗結果不等于0），通過前面介紹的校驗規律可以很快地發現是G4校驗組中的p4校位碼（也就是整個碼字中的第8位）錯了（因為隻有一組校驗結果出現差錯時，則肯定隻是對應的校驗位出了差錯），也就是最終的碼字變成了：111000001101。

    再假設G3、G4兩個校驗值都不為0，也就是都等于1。通過表5-2中比較G3、G4兩個校驗組（注意本示例中碼字長度一共才12位，隻需要比較前12位）中共同校驗的碼位可是以很快發現是b8，也就是第12位出現了差錯，也就是最終的碼字變成了：111000011100。

    【經驗之談】在這裡一定要注意，最終有多少個校驗組出現差錯也不是随意的，一定要結合實際傳輸的碼字長度來考慮。如上例是一共12位，如果換成了是16位的碼字，且當b9位出現差錯時，則G1、G3、G4一定會同時出現錯誤，因為b9這個位是三個校驗組同時校驗的，隻要它一出錯，肯定會同時影響這三個校驗組的值。同理，如果是b11位出現了差錯，因為它同時受G1、G2、G3、G4四個校驗組校驗，是以這四個校驗組結果都将出現錯誤。

    2）海明碼的差錯糾正

    檢測出了是哪位差錯還不夠，因為海明碼具有糾正一位錯誤的能力，是以還需要完成糾錯過程。這個過程的原理比較簡單，就是直接對錯誤的位進行取反，或者加“1”操作，使它的值由原來的“1”變成“0”，由原來的“0”變成“1”（因為二進制中每一位隻能是這二者之一）。

    以上就是海明碼的整差錯檢測和差錯糾正原理了，确實比單純的奇偶校驗碼複雜些，但隻要理清了思路，也還是比較簡單的。