海明校驗碼的原理詳解

1、.海明校驗碼的原理詳解2006年12月27日 星期三 10:57海明碼是一種多重(復式)奇偶檢錯系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯和糾錯。用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這種奇偶位被編在傳輸碼字的特定位置上。實現(xiàn)得合適時，這個系統(tǒng)對于錯誤的數(shù)位無論是原有信息位中的，還是附加校驗位中的都能把它分離出來。推導并使用長度為m位的碼字的海明碼，所需步驟如下：1、確定最小的校驗位數(shù)k，將它們記成D1、D2、Dk，每個校驗位符合不同的奇偶測試規(guī)定。2、原有信息和k個校驗位一起編成長為m+k位的新碼字。選擇k校驗位（0或1）以滿足必要的奇偶條件。3、對所接收的

2、信息作所需的k個奇偶檢查。4、如果所有的奇偶檢查結(jié)果均為正確的，則認為信息無錯誤。如果發(fā)現(xiàn)有一個或多個錯了，則錯誤的位由這些檢查的結(jié)果來唯一地確定。校驗位數(shù)的位數(shù)推求海明碼時的一項基本考慮是確定所需最少的校驗位數(shù)k?？紤]長度為m位的信息，若附加了k個校驗位，則所發(fā)送的總長度為m+k。在接收器中要進行k個奇偶檢查，每個檢查結(jié)果或是真或是偽。這個奇偶檢查的結(jié)果可以表示成一個k位的二進字，它可以確定最多2k種不同狀態(tài)。這些狀態(tài)中必有一個其所有奇偶測試試都是真的，它便是判定信息正確的條件。于是剩下的（2k-1）種狀態(tài)，可以用來判定誤碼的位置。于是導出下一關系：2k-1m+k碼字格式從理論上講，校驗位可

3、放在任何位置，但習慣上校驗位被安排在1、2、4、8、的位置上。圖5列出了m=4，k=3時，信息位和校驗位的分布情況。碼字位置B1B2B3B4B5B6B7校驗位xxx信息位xxxx復合碼字P1P2D1P3D2D3D4圖5海明碼中校驗位和信息位的定位校驗位的確定下面為我增加，意在提出編碼方法以助理解（但編碼是否主要標準不可知）每行的值等于數(shù)值為1的各位碼相異或。如m=4,k=3.數(shù)據(jù)位前三行，校驗位為后三行。即A=p1D1D3D4=0得P1=D1D3D4B=P2D2D3D4=0得P2=D2D3D4C=P3D1D2D3D4=0得P3=D1D2D3D4以下計算訪求同下k個校驗位是通過對m+k位復合碼字

4、進行奇偶校驗而確定的。其中：P1位負責校驗海明碼的第1、3、5、7、（P1、D1、D2、D4、）位，（包括P1自己）P2負責校驗海明碼的第2、3、6、7、（P2、D1、D3、D4、）位，（包括P2自己）P3負責校驗海明碼的第4、5、6、7、（P3、D2、D3、D4、）位，（包括P3自己）對m=4，k=3，偶校驗的例子，只要進行式次偶性測試。這些測試（以A、B、C表示）在圖6所示各位的位置上進行。奇偶條件碼字位置1234567ABCxxxxxxxxxxxx圖6奇偶校驗位置因此可得到三個校驗方程及確定校驗位的三個公式：A=B1B3B5B7=0得P1=D1D2D4B=B2B3B6B7=0得P2=D1

5、D3D4C=B4B5B6B7=0得P3=D2D3D4若四位信息碼為1001，利用這三個公式可求得三個校驗位P1、P2、P3值。和海明碼，上面是發(fā)送方的處理在接收方，也可根據(jù)這三個校驗方程對接收到的信息進行同樣的奇偶測試：A=B1B3B5B7=0；B=B2B3B6B7=0；C=B4B5B5B7=0。若三個校驗方程都成立,即方程式右邊都等于0，則說明沒有錯。若不成立即方程式右邊不等于0，說明有錯。從三個方程式右邊的值，可以判斷那一位出錯。例如，如果第3位數(shù)字反了，則C=0(此方程沒有B3），A=B=1（這兩個方程有B3）。可構成二進數(shù)CBA，以A為最低有效位，則錯誤位置就可簡單地用二進數(shù)CBA=0

6、11指出。同樣，若三個方程式右邊的值為001，說明第1位出錯。若三個方程式右邊的值為100，說明第4位出錯。海明碼的碼距應該是3，所以能糾正1位出錯。而奇偶校驗碼的碼距才是2，只能發(fā)現(xiàn)1位出錯，但不能糾正（不知道那一位錯）。無校驗的碼距是1，它出任何一位出錯后還是合法代碼，所以也就無法發(fā)現(xiàn)出錯。這是關于海明碼的經(jīng)典說法，即碼距為3，可以發(fā)現(xiàn)2位，或者糾正1位錯。應滿足2k-1m+k。但在清華的王愛英主編的計算機組成與結(jié)構（該書已成為國內(nèi)的權威）中還提出了一種碼距為4的海明碼，可以發(fā)現(xiàn)2位，并且糾正1位錯。應滿足2(k-1)m+k。由于王愛英書上對這兩種概念沒有很仔細解釋（特別對碼距為3的海明碼

7、），過渡很突然。有些書簡單抄襲時沒有仔細消化，所以出現(xiàn)一些概念錯。對于一般碼距為3的海明碼，應該是“可以發(fā)現(xiàn)2位，或者糾正1位錯”，而不是“可以發(fā)現(xiàn)2位，并且糾正1位錯”。在試題中出現(xiàn)過類似的錯誤。若四位信息碼為1001，利用這三個公式可求得三個校驗位P1、P2、P3值。和海明碼，如圖7則表示了信息碼為1001時的海明碼編碼的全部情況。而圖8中則列出了全部16種信息（D1D2D3D4=00001111）的海明碼。碼字位置B1B2B3B4B5B6B7碼位類型P1P2D1P3D2D3D4信息碼-1-001校驗位00-1-編碼后的海明碼0011001圖7四位信息碼的海明編碼P1P2D1P3D2D3D40000000110100