漢明碼計算及其糾錯原理詳解

當(dāng)計算機(jī)存儲或移動數(shù)據(jù)時，可能會產(chǎn)生數(shù)據(jù)位錯誤，這時可以利用漢明碼來檢測并糾錯，簡單的說，漢明碼是一個錯誤校驗碼碼集，由Bell 實驗室的R.W.Hamming 發(fā)明，因此定名為漢明碼。

漢明碼（Hamming Code），是在電信領(lǐng)域的一種線性調(diào)試碼，以發(fā)明者理查德·衛(wèi)斯里·漢明的名字命名。漢明碼在傳輸?shù)南⒘髦胁迦腧炞C碼，以偵測并更正單一比特錯誤。由于漢明編碼簡單，它們被廣泛應(yīng)用于內(nèi)存（RAM ）。其SECDED （single error correction， double error detection）版本另外加入一檢測比特，可以偵測兩個或以下同時發(fā)生的比特錯誤，并能夠更正單一比特的錯誤。因此，當(dāng)發(fā)送端與接收端的比特樣式的漢明距離（Hamming distance）小于或等于1時（僅有1 bit發(fā)生錯誤），可實現(xiàn)可靠的通信。相對的，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數(shù)個的錯誤。

在數(shù)學(xué)方面，漢明碼是一種二元線性碼。對于每一個整數(shù)，存在一個編碼，帶有個奇偶校驗位個數(shù)據(jù)位。該奇偶檢驗矩陣的漢明碼是通過列出所有米欄的長度是兩兩獨(dú)立。

漢明碼的定義和漢明碼不等式：

設(shè)：m=數(shù)據(jù)位數(shù)，k=校驗位數(shù)為，n=總編碼位數(shù)＝m+k，有Hamming不等式：

漢明碼不等式含義：

a） 總數(shù)據(jù)長度為N，如果每一位數(shù)據(jù)是否錯誤都要記錄，就需要N位來存儲。

b） 每個校驗位都可以表示：對或錯；校驗位共K位，共可表示2k種狀態(tài)

c） 總編碼長度為N，所以包含某一位錯和全對共N+1種狀態(tài)。

d） 所以2k≧N+1 e） 數(shù)據(jù)表見下

Hamming碼缺點(diǎn)：

無法實現(xiàn)2位或2位以上的糾錯，Hamming碼只能實現(xiàn)一位糾錯。

以典型的4位數(shù)據(jù)編碼為例，演示漢明碼的工作過程

a） 數(shù)據(jù)存儲格式：

依照此前的漢明碼不等式計算出，當(dāng)數(shù)據(jù)位為4位時，漢明碼校驗位至少為3位，如上方式排列

可以看的出D8、D4、D2、D1中的數(shù)字都是2的整數(shù)冪

b） 漢明校驗碼的插入規(guī)律：

設(shè)：編碼位代號k，校驗碼位代號p，數(shù)據(jù)位代號n

某個校驗碼Pp將處于整個編碼的第k位

k=2^（p-1）=2的（p-1）次方

以數(shù)據(jù)位為5的一組9位數(shù)編碼為例，如下：

c） 校驗位與數(shù)據(jù)位的對應(yīng)關(guān)系：

注：^是邏輯運(yùn)算符異或。

P1=D8^D4^D1

P2=D8^D2^D1

P3=D4^D2^D1

小解釋：數(shù)據(jù)位共4位每行等式都缺少一位，而缺少的這位數(shù)據(jù)位正好是DX，等式左邊的校驗位為PY，X=2y.

d） 校驗位如何參與計算：

P1’=P1^D8^D4^D1

P2’=P2^D8^D2^D1

P3’=P3^D4^D2^D1

從高到低排列的二進(jìn)制數(shù)：P3’ P2’ P1’表示的就是出錯的編碼位，從000-011-101-110-111共5種組合，可表示原數(shù)據(jù)位D8D4D2D1某一位錯&沒錯的一共5種狀態(tài)。

e） 設(shè)有一數(shù)字為：1101，帶入運(yùn)算：

D8=1、D4=1、D2=0、D1=1，

P1 =1，P2=0、P3=0。

漢明碼處理的結(jié)果就是1010101

假設(shè)：D8出錯，P3’ P2’ P1’=011=十進(jìn)制的3，即表示編碼后第三位出錯，對照存儲格式表，果然就是D8錯誤。

假設(shè)：D4錯誤，P3’ P2’ P1’=101=十進(jìn)制的5，即表示編碼后第五位出錯，對照存儲格式表，果然就是D4錯誤。