淺談海明碼校驗(yàn)碼

【摘要】 本文結(jié)合了本人的教學(xué)體會(huì)，簡明介紹了海明碼是如何達(dá)到在檢測出一位出錯(cuò)并能自動(dòng)恢復(fù)該出錯(cuò)位的正確值以及檢測出二位同時(shí)出錯(cuò)的效果的。

【關(guān)鍵詞】 海明校驗(yàn)碼；自動(dòng)糾錯(cuò)

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

海明碼是由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ù)。下面通過一個(gè)例子來看海明碼是如果實(shí)現(xiàn)其功能的，在例子之前先說明海明碼編碼的一般性規(guī)則。①校驗(yàn)位一般放在2ⁿ位置（也就是第1、2、4、8、……個(gè)位置）；②每個(gè)校驗(yàn)位只校驗(yàn)數(shù)據(jù)位中位置號的二進(jìn)制編碼和自己本身位置號的二進(jìn)制編碼匹配的數(shù)據(jù)位。說明：P1位置號的二進(jìn)制編碼為0001，因?yàn)楦鶕?jù)后面可知P1處在二進(jìn)制串的第1個(gè)位置，所以它負(fù)責(zé)校驗(yàn)位置號二進(jìn)制編碼為0011、0101、0111、1001、1011的數(shù)據(jù)位，也就是P1負(fù)責(zé)校驗(yàn)D1D2D4D5D7；因?yàn)檫@幾個(gè)數(shù)據(jù)位的位置號的二進(jìn)制編碼和P1一樣，最低位都是1。P2位置號的二進(jìn)制編碼為0010，因?yàn)楦鶕?jù)后面可知P2處在二進(jìn)制串的第2個(gè)位置，所以它負(fù)責(zé)校驗(yàn)位置號二進(jìn)制編碼為0011、0110、0111、1010、1011的數(shù)據(jù)位，也就是P2負(fù)責(zé)校驗(yàn)D1D3D4D6D7；因?yàn)檫@幾個(gè)數(shù)據(jù)位的位置號的二進(jìn)制編碼和P2一樣，倒數(shù)第2位都是1。同理我們可以推出P3負(fù)責(zé)校驗(yàn)D2D3D4D8。P4負(fù)責(zé)校驗(yàn)D5D6D7D8。現(xiàn)在我們來看這個(gè)例子：假設(shè)現(xiàn)有一8位并口用來傳輸數(shù)據(jù)，也就是k=8，這8位數(shù)據(jù)分別定義為D1、D2、D3、D4、D5、D6、D7、D8。校驗(yàn)位我們定義成P（也就是第1個(gè)校驗(yàn)位為P1、第2個(gè)為P2，依次類推）。那么根據(jù)海明碼編碼的一般性規(guī)則，把數(shù)據(jù)位和校驗(yàn)位放在一起組成了一個(gè)這樣的二進(jìn)制串：P5D8D7D6D5P4D4D3D2P3D1P2P1說明：①除P5外其他的檢驗(yàn)位P1（處在第1個(gè)位置）、P2（處在第2個(gè)位置）、P3（處在第4個(gè)位置）、P4（處在第8個(gè)位置）符合一般性規(guī)則。②P5是為了校驗(yàn)2位出錯(cuò)加到最高位的那么根據(jù)一般性規(guī)則的第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個(gè)式子也是為了校驗(yàn)2位出錯(cuò)而設(shè)置的知道這幾個(gè)式子是怎么來的后，我們來看三個(gè)問題。首先如何計(jì)算海明碼，假設(shè)要傳輸?shù)?位二進(jìn)制數(shù)據(jù)是10011010，根據(jù)上面的5個(gè)式子可以得到P1=1、P2=1、P3=1、P4=0、P5=1。將其代入二進(jìn)制串可知當(dāng)要傳輸?shù)?位二進(jìn)制數(shù)據(jù)是10011010時(shí)，它的海明碼為110010101011。其次如何檢測一位出錯(cuò)并恢復(fù)該出錯(cuò)位在判斷一位出錯(cuò)的時(shí)候要用到下面幾個(gè)式子：①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以上幾個(gè)式子大家可以看出來在正常傳輸?shù)倪^程中是S1=S2=S3=S4=S5=0的，因?yàn)镻1就是等于D1、D2、D4、D5、D7，所以它們之間相異或結(jié)果為0（S2、S3、S4、S5等于0的原因一樣）。現(xiàn)在假設(shè)海明碼在傳輸?shù)倪^程中有1位出錯(cuò)了，出錯(cuò)的可能是數(shù)據(jù)位，也可能是校驗(yàn)位，我們現(xiàn)在分情況討論。①數(shù)據(jù)位錯(cuò)，校驗(yàn)位沒出錯(cuò)；假設(shè)D3出錯(cuò)了（D3本來是0，出錯(cuò)后變成1了）我們看下S1、S2、S3、S4、S5值的變化。S4=0：S4的值沒變，因?yàn)镾4是P4、D5、D6、D7、D8異或，跟D3沒關(guān)系。S3=1：S3的值變了，因?yàn)镾3是P3、D2、D3、D4、D8異或，跟D3有關(guān)系。S2=1：S2的值變了，因?yàn)镾2是P2、D1、D3、D4、D6、D7異或，跟D3有關(guān)系。S1=0：S1的值沒變，因?yàn)镾1是P1、D1、D2、D4、D5、D7異或，跟D3沒關(guān)系。S5=1：S5的值變了，因?yàn)镾5是所有的數(shù)據(jù)位和所有的校驗(yàn)位異或，跟D3有關(guān)系。也就是所當(dāng)D3出錯(cuò)的時(shí)候S4S3S2S1=0110，也就是十進(jìn)制的6，我們在看看D3在海明碼二進(jìn)制串中的位置號，是不是也是6。是不是很神奇，大家可以多試幾個(gè)，同時(shí)大家也可以發(fā)現(xiàn)S5=1。首先校驗(yàn)位出錯(cuò)，數(shù)據(jù)位沒出錯(cuò)。這個(gè)我就不再舉例說明了，大家可以去試下，結(jié)論也和數(shù)據(jù)位錯(cuò)，校驗(yàn)位沒出錯(cuò)一樣。從而我們可以得出結(jié)論：當(dāng)S5=1時(shí)候，說明是海明碼一位出錯(cuò)，這個(gè)時(shí)候我們可以通過S4S3S2S1的值找出出錯(cuò)的海明碼的位置號，找到了出錯(cuò)的位置號了糾錯(cuò)就不是難事了，只需要把對應(yīng)位置的數(shù)據(jù)取反就是正確的碼值了。

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

4 參考文獻(xiàn)

[1] 王愛英．計(jì)算機(jī)組成與結(jié)構(gòu)[M]．北京：清華大學(xué)出版社，2004.

[2] 程曉榮.計(jì)算機(jī)組成與結(jié)構(gòu)[M].北京：中國電力出版社，2007.