淺談海明碼校驗碼

【摘要】 本文結合了本人的教學體會，簡明介紹了海明碼是如何達到在檢測出一位出錯并能自動恢復該出錯位的正確值以及檢測出二位同時出錯的效果的。

【關鍵詞】 海明校驗碼；自動糾錯

【中圖號】 G623.58 【文獻標示碼】 A 【文章編號】 1005-1074(2008)12-0152-01

海明碼是由Richard Hamming于1950年提出、目前還被廣泛采用的一種很有效的校驗方法，是只要增加少數幾個校驗位，就能檢測出二位同時出錯、亦能檢測出一位出錯并能自動恢復該出錯位的正確值的有效手段，后者被稱為自動糾錯。它的實現原理，是在k個數據位之外加上r個校驗位，從而形成一個k+r位的新的碼字，使新的碼字的碼距比較均勻地拉大。把數據的每一個二進制位分配在幾個不同的偶校驗位的組合中，當某一位出錯后，就會引起相關的幾個校驗位的值發生變化，這不但可以發現出錯，還能指出是哪一位出錯，為進一步自動糾錯提供了依據。下面通過一個例子來看海明碼是如果實現其功能的，在例子之前先說明海明碼編碼的一般性規則。①校驗位一般放在2ⁿ位置（也就是第1、2、4、8、……個位置）；②每個校驗位只校驗數據位中位置號的二進制編碼和自己本身位置號的二進制編碼匹配的數據位。說明：P1位置號的二進制編碼為0001，因為根據后面可知P1處在二進制串的第1個位置，所以它負責校驗位置號二進制編碼為0011、0101、0111、1001、1011的數據位，也就是P1負責校驗D1D2D4D5D7；因為這幾個數據位的位置號的二進制編碼和P1一樣，最低位都是1。P2位置號的二進制編碼為0010，因為根據后面可知P2處在二進制串的第2個位置，所以它負責校驗位置號二進制編碼為0011、0110、0111、1010、1011的數據位，也就是P2負責校驗D1D3D4D6D7；因為這幾個數據位的位置號的二進制編碼和P2一樣，倒數第2位都是1。同理我們可以推出P3負責校驗D2D3D4D8。P4負責校驗D5D6D7D8。現在我們來看這個例子：假設現有一8位并口用來傳輸數據，也就是k=8，這8位數據分別定義為D1、D2、D3、D4、D5、D6、D7、D8。校驗位我們定義成P（也就是第1個校驗位為P1、第2個為P2，依次類推）。那么根據海明碼編碼的一般性規則，把數據位和校驗位放在一起組成了一個這樣的二進制串：P5D8D7D6D5P4D4D3D2P3D1P2P1說明：①除P5外其他的檢驗位P1（處在第1個位置）、P2（處在第2個位置）、P3（處在第4個位置）、P4（處在第8個位置）符合一般性規則。②P5是為了校驗2位出錯加到最高位的那么根據一般性規則的第2條可以得出：①P1=D1 D2、D4、D5、D7；②P2=D1、D3、D4、D6、D7；③P3=D2、D3、D4、D8；④P4=D5、D6、D7、D8；⑤P5=D1、D2、D3、D4、D5、D6、D7、D8、P1、P2、P3、P4說明：第5個式子也是為了校驗2位出錯而設置的知道這幾個式子是怎么來的后，我們來看三個問題。首先如何計算海明碼，假設要傳輸的8位二進制數據是10011010，根據上面的5個式子可以得到P1=1、P2=1、P3=1、P4=0、P5=1。將其代入二進制串可知當要傳輸的8位二進制數據是10011010時，它的海明碼為110010101011。其次如何檢測一位出錯并恢復該出錯位在判斷一位出錯的時候要用到下面幾個式子：①S1=P1、D1、D2、D4、D5、D7；②S2=P2、D1、D3、D4、D6、D7；③S3=P3、D2、D3、D4、D8；④S4=P4、D5、D6、D7、D8；⑤S5=P5、D1、D2、D3、D4、D5、D6、D7、D8、P1、P2、P3、P4以上幾個式子大家可以看出來在正常傳輸的過程中是S1=S2=S3=S4=S5=0的，因為P1就是等于D1、D2、D4、D5、D7，所以它們之間相異或結果為0（S2、S3、S4、S5等于0的原因一樣）。現在假設海明碼在傳輸的過程中有1位出錯了，出錯的可能是數據位，也可能是校驗位，我們現在分情況討論。①數據位錯，校驗位沒出錯；假設D3出錯了（D3本來是0，出錯后變成1了）我們看下S1、S2、S3、S4、S5值的變化。S4=0：S4的值沒變，因為S4是P4、D5、D6、D7、D8異或，跟D3沒關系。S3=1：S3的值變了，因為S3是P3、D2、D3、D4、D8異或，跟D3有關系。S2=1：S2的值變了，因為S2是P2、D1、D3、D4、D6、D7異或，跟D3有關系。S1=0：S1的值沒變，因為S1是P1、D1、D2、D4、D5、D7異或，跟D3沒關系。S5=1：S5的值變了，因為S5是所有的數據位和所有的校驗位異或，跟D3有關系。也就是所當D3出錯的時候S4S3S2S1=0110，也就是十進制的6，我們在看看D3在海明碼二進制串中的位置號，是不是也是6。是不是很神奇，大家可以多試幾個，同時大家也可以發現S5=1。首先校驗位出錯，數據位沒出錯。這個我就不再舉例說明了，大家可以去試下，結論也和數據位錯，校驗位沒出錯一樣。從而我們可以得出結論：當S5=1時候，說明是海明碼一位出錯，這個時候我們可以通過S4S3S2S1的值找出出錯的海明碼的位置號，找到了出錯的位置號了糾錯就不是難事了，只需要把對應位置的數據取反就是正確的碼值了。

如何檢測出2位同時出錯有了上面的基礎后，我們很容易發現，如果是2位出錯，不管出錯的2位是數據位，還是校驗位，S5必定等于0而且S4S3S2S1必定不等于0000。（大家可以去試下）通過上面的討論我們可以得出以下結論。①如果傳輸過程正常：S5S4S3S2S1=0。②如果是一位出錯：S5=1，并且通過S4S3S2S1的值可以找出出錯的到底是那一位。③如果是二位出錯：S5=0，并且S4S3S2S1≠0000補充說明：其實在判斷一位出錯的時候，S5=1不一定是一位出錯，可能3位出錯，也可能是5、7位出錯（如果你細心的話應該能發現），但是由于在計算機數據傳輸過程中，一位出錯的幾率比多位同時出錯的幾率高的多，所以該方案還是有很好的使用價值。

4 參考文獻

[1] 王愛英．計算機組成與結構[M]．北京：清華大學出版社，2004.

[2] 程曉榮.計算機組成與結構[M].北京：中國電力出版社，2007.