漢明碼計(jì)算及其糾錯(cuò)原理詳解

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

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

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

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

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

漢明碼不等式含義：

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

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

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

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

Hamming碼缺點(diǎn)：

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

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

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

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

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

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

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

某個(gè)校驗(yàn)碼Pp將處于整個(gè)編碼的第k位

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

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

c） 校驗(yàn)位與數(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，等式左邊的校驗(yàn)位為PY，X=2y.

d） 校驗(yàn)位如何參與計(jì)算：

P1’=P1^D8^D4^D1

P2’=P2^D8^D2^D1

P3’=P3^D4^D2^D1

從高到低排列的二進(jìn)制數(shù)：P3’ P2’ P1’表示的就是出錯(cuò)的編碼位，從000-011-101-110-111共5種組合，可表示原數(shù)據(jù)位D8D4D2D1某一位錯(cuò)&沒錯(cuò)的一共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出錯(cuò)，P3’ P2’ P1’=011=十進(jìn)制的3，即表示編碼后第三位出錯(cuò)，對照存儲(chǔ)格式表，果然就是D8錯(cuò)誤。

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