|
漢明碼歷史 漢明碼（Hamming Code），是在電信領(lǐng)域的一種線性調(diào)試碼，以發(fā)明者理查德·衛(wèi)斯里·漢明的名字命名。漢明碼在傳輸?shù)南⒘髦胁迦腧炞C碼，當(dāng)計算機存儲或移動數(shù)據(jù)時，可能會產(chǎn)生數(shù)據(jù)位錯誤，以偵測并更正單一比特錯誤。由于漢明編碼簡單，它們被廣泛應(yīng)用于內(nèi)存（RAM）和磁盤糾錯的編碼。漢明碼不僅可以用來檢測轉(zhuǎn)移數(shù)據(jù)時發(fā)送的錯誤，還可以用來修正作物。(漢明碼只能發(fā)現(xiàn)和修正一位錯誤，對于兩位及兩位以上的錯誤無法發(fā)現(xiàn)和糾正)。 1940年，漢明于貝爾實驗室（Bell Labs）工作，運用貝爾模型V（Bell Model V）電腦，一個周期時間在幾秒鐘內(nèi)的機電繼電器機器。輸入端是依靠打孔卡（Punched Card），這不免有些讀取錯誤。在平日，特殊代碼將發(fā)現(xiàn)錯誤并閃燈（flash lights），使得操作者能夠糾正這個錯誤。在周末和下班期間，在沒有操作者的情況下，機器只會簡單地轉(zhuǎn)移到下一個工作。漢明在周末工作，他對于不可靠的讀卡機發(fā)生錯誤后，總是必須重新開始項目變得愈來愈沮喪。在接下來的幾年中，他為了解決調(diào)試的問題，開發(fā)了功能日益強大的調(diào)試算法。在1950年，他發(fā)表了今日所稱的漢明碼�，F(xiàn)在漢明碼有著廣泛的應(yīng)用。 漢明碼原理 設(shè)將要進(jìn)行檢測的二進(jìn)制源碼為n位，為使其具有糾錯能力，需要再加上k位的檢測位，組成n+k=m位的二進(jìn)制。那么，新增加的檢測位數(shù)k應(yīng)滿足：
這就是漢明碼不等式，規(guī)定所得到的m位編碼$2^k(k \geq 0 | 2^k < n+k)$位上插入特殊的校驗碼，其余位把源碼按順序放置。n位二進(jìn)制和校驗碼位數(shù)k的關(guān)系： n k最小值
1 2
2~4 3
5~11 4
12~26 5
27~57 6
57~120 7
漢明碼編碼方式1編碼規(guī)則：在新的編碼的$2^{(k-1)} (k \geq 0)$位上填入0(即校驗位)。 在新的編碼的其余位把源碼按原順序填入校驗位的編碼方式為：第k位校驗碼從則從新的編碼的第$2^{(k-1)}$位開始，每計算$2^{(k-1)}$位的異或，跳$2^{(k-1)}$位，再計算下一組$2^{(k-1)}$位的異或，填入$2^{(k-1)}$位。 比如：第1位校驗碼位于新的編碼的第1位$2^{(1-1)}==1$(漢明碼從1位開始)，計算1,3,5,7,9,11,13,15,…位的異或，填入新的編碼的第1位。第2位校驗碼位于新的編碼的第2位$2^{(2-1)}==2$，計算2,3,6,7,10,11,14,15,…位的異或，填入新的編碼的第2位。第3位校驗碼位于新的編碼的第4位$2^{(3-1)}==4$，計算4,5,6,7,12,13,14,15,20,21,22,23,…位的異或，填入新的編碼的第4位。第4位校驗碼位于新的編碼的第8位$2^{(4-1)}==8$，計算8-15,24-31,40-47,…位的異或，填入新的編碼的第8位。第5位校驗碼位于新的編碼的第16位$2^{(5-1)}==16$，計算16-31,48-63,80-95,…位的異或，填入新的編碼的第16位。
編碼示例： 以10101源碼為例，$n=5$,由公式$2^k-1 \geq n+k$得$k=4$，如下表所示編碼結(jié)果為001101011。 1 2 3 4 5 6 7 8 9
$2^{(1-1)}$校驗位 $2^{(1-1)}$校驗位 1 $2^{(1-1)}$校驗位 0 1 0 $2^{(1-1)}$校驗位 1
0 0 1 0 0 1 0 0 1
0(計算1，3，5，7，9位異或) 0(計算2，3，6，7位異或) 1 1(計算4,5,6,7位異或) 0 1 0 (計算8，9位異或) 1
計算校驗碼的第1位（1,3,5,7,9進(jìn)行異或）: 結(jié)果為0，所以漢明碼第2^0位為0，結(jié)果為0 _ 1 _ 0 10 _ 1 計算校驗碼的第2位（2,3,6,7進(jìn)行異或）: 結(jié)果為0，所以漢明碼第2^1位為0，結(jié)果為001 _ 0 10 _ 1 計算校驗碼的第3位（4,5,6,7進(jìn)行異或）: 結(jié)果為1，所以漢明碼第2^2位為0，結(jié)果為0011 0 10 _ 1 計算校驗碼的第4位（8, 9進(jìn)行異或）: 結(jié)果為0，所以漢明碼第2^3位為1，結(jié)果為001101011 所以最終編碼為001101011.
漢明碼編碼方式2通過k值將源碼分為$P_n$組，第1組為$2^0$，第2組為$2^1$，第3組為$2^2$，同理以此類推分組按照$2^{(k-1)}$。同時分組后插入的校驗碼的位置也是按照次規(guī)律插入，$2^0$位插入第1個校驗碼，即$P_1$組第1位，$2^1$位插入第2個校驗碼，即$P_2$組第1位，$2^2$位插入第3個校驗碼，即$P_3$組第1位，以此類推。 P1組包含(1(校驗碼),3,5,7,9,11...位)
P2組包含(2(校驗碼),3,6,7,10,11,14,15...位)
P3組包含(4(校驗碼),5,6,7,12,13,14,15...位)
...
同時也可以通過下表方式來劃分組。 編號 1 2 3 4 5 6 7 8
二進(jìn)制 0001 0010 0011 0100 0110 0111 1000 1001 將編號轉(zhuǎn)成二進(jìn)制從右向左，如果第1位是1，例如編號是1,3,5,7....的就分入P1組，如果第2位是1的，例如編號2,3,6,7,10...的就分入第P2組，以此類推將所有的編號分入相應(yīng)的組中。 當(dāng)分好組之后，P1組中第1位（校驗位）應(yīng)使1，3，5，7，9，11...位中“1”的個數(shù)為偶數(shù)。P2組中第2位（校驗位）應(yīng)使2，3，6，7，10，11，14，15...位中“1”的個數(shù)為偶數(shù)。P3組中第4位（校驗位）應(yīng)使4，5，6，7，12，13，14，15...位中“1”的個數(shù)為偶數(shù)。漢明碼還存在配奇原則，與之相反。
編碼示例： 以10101源碼為例，$n=5$,由公式$2^k-1 \geq n+k$得$k=4$，如下表所示編碼結(jié)果為001101011，C1,C2,C3,C4為插入的校驗碼。 1 2 3 4 5 6 7 8 9
$2^{(1-1)}$校驗位 $2^{(1-1)}$校驗位 1 $2^{(1-1)}$校驗位 0 1 0 $2^{(1-1)}$校驗位 1
C1 C2 B1 C3 B2 B3 B4 C4 B5 如果按照配偶原則來配置漢明碼，則C1應(yīng)使1,3,5,7,9位中“1”的個數(shù)為偶數(shù)；C2應(yīng)使2,3,6,7位中“1”的個數(shù)為偶數(shù)；C3應(yīng)使4,5,6,7位中“1”的個數(shù)為偶數(shù)；C4應(yīng)使8,9位中的“1”的個數(shù)為偶數(shù)。所以10101源碼的漢明碼為001101011。 漢明碼的糾錯 根據(jù)以上說的漢明碼的配偶原則和配奇原則我們來看漢明碼的糾錯。設(shè)接收到的錯誤漢明碼（按配偶原則配置）是001101001，我們可以根據(jù)上述規(guī)律來確定出錯位。 序號 1 2 3 4 5 6 7 8 9
接收到的漢明碼 0 0 1 1 0 1 0 1 1 那么新的檢測位為： P1=1位^3位^5位^7位^9位，得到0。 P2=2位^3位^6位^7位，得到0。 P3=4位^5位^6位^7位，得到0。 P4=8位^9位，得到1。 根據(jù)P4P3P2P1構(gòu)成的二進(jìn)制是1000，將1000轉(zhuǎn)換成十進(jìn)制為8，說明是第8位出錯，或者根據(jù)配偶原則的規(guī)律，其“1”的個數(shù)必須是偶數(shù)也能判斷出是第8位，所以第8位應(yīng)將“1”改為“0”，那么正確的漢明碼應(yīng)為001101011。 漢明碼屬于分組奇偶校驗，P4P3P2P1=0000，說明接收方生成的校驗位和收到的校驗位相同，否則不同說明出錯。由于分組時校驗位只參加一組奇偶校驗，有效信息參加至少兩組奇偶校驗，若果校驗位出錯，P4P3P2P1的某一位將為1，剛好對應(yīng)位號8、4、2、1；若果有效信息出錯，將引起P4P3P2P1中至少兩位為1。
以上博文參考自：
|
