漢明碼

所謂漢明碼(Hamming code)是一種錯誤更正碼，可檢查錯誤並更正。有關漢明碼的編碼方式說明如下：


(一)漢明碼的編碼：有關漢明碼的內容可以分成資料位元和核位元兩個部分，以傳輸資料中2的次方位元部分(第1,2,4,8.‥個位元)當核對位元 (check bits)Ci，分別由資料位元第k個位元中符合(2I AND k)0的所有位元中計算1的個數，結果則視採用奇同位檢查或偶同位檢查而定，若採用奇同位檢查則結果若為奇數個1則取0，偶數個l則取1；反之若採偶同 位檢查，則結果若為奇數個l則取l，偶數個1則取0。

(二)漢明碼的檢查：對各組核對位元作檢查，若引為核對位元Ci與其相關資料位元的同位檢查結果，則(Em-1, Em-2, ….E0)即為錯誤的位元位置，只要更正此一位元即可。


通用演算法
下列通用演算法可以為任意位數位產生一個可以糾錯一位（英語：Single Error Correcting）的漢明碼。
從1開始給數字的數據位（從左向右）標上序號, 1，2，3，4，5...
將這些資料位的位置序號轉換為二進制， 1, 10, 11, 100, 101, 等.
資料位的位置序號中所有為二的冪次方的位（編號1，2，4，8，等，即資料位位置序號的二進制表示中只有一個1）是校驗位
所有其它位置的資料位（資料位位置序號的二進制表示中至少2個是1）是資料位
每一位的資料包含在特定的兩個或兩個以上的校驗位中，這些校驗位取決於這些資料位的位置數值的二進制表示
校驗位 1 覆蓋了所有資料位位置序號的二進制表示倒數第一位是1的資料：1（校驗位自身，這裡都是二進制，下同），11，101，111，1001，等
校驗位 2 覆蓋了所有資料位位置序號的二進制表示倒數第二位是1的資料：10（校驗位自身），11，110，111，1010，1011，等
校驗位 4 覆蓋了所有資料位位置序號的二進制表示倒數第三位是1的資料：100（校驗位自身），101，110，111，1100，1101，1110，1111，等
校驗位 8 覆蓋了所有資料位位置序號的二進制表示倒數第四位是1的資料：1000（校驗位自身），1001，1010，1011，1100，1101，1110，1111，等
簡而言之，所有校驗位覆蓋了資料位置和該校驗位位置的二進制與的值不為0的數。
採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。

因為2的0次方，2的1次方，2的2次方...（以下類推）要作為漢明碼
的填入位置，所以先寫成如下這樣

1   2   3   4   5   6   7   8   9   先在紙上寫出1-9再將資料
          1       1   0   1       0   由左至右順序填入

為什麼有四個空格（或者說怎麼知道要空這四格），是因為有一個
公式：2^K>=M+K+1（M就是資料位元有5，所以2^K要>=5+K+1，算出
K=4）

接下來再畫一個如下的表
     8   4   2   1        ←這一行只是方便我們看十進位的值是多少
1   0   0   0   □         ←先留空格是因為還不知道該填什麼
2   0   0   □   0          填表的方式是
3   0   0   1   1          (a)若資料為 0 則相對應的位置填 0。
4   0   □   0   0          (b)若資料為 1 則以其相對應的位置值
5   0   1   0   1             化成二進位碼，並填入相對應的位置中。
6   0   0   0   0        ←所以這一行才會都是0
7   0   1   1   1        ←這一行就是因為上面7的地方是1所以改為
8   □   0   0   0          二進制後填入
9   0   0   0   0        ←這一行也都是0
---------------------

再來就要依另一個規則決定漢明碼：各數位的 1 值個數需為偶數個
依此原則決定所有漢明碼的值
     8   4   2   1
1   0   0   0   □         ←空格填1，最右邊這行由上往下數有3個1，如
2   0   0   □   0          果要湊成偶數個1，則空格要填入1
3   0   0   1   1
4   0   □   0   0        ←空格填0，因為由上往下數已經有2個1，所以
5   0   1   0   1          不用另外填1
6   0   0   0   0
7   0   1   1   1
8   □   0   0   0
9   0   0   0   0
---------------------

再回到剛剛寫的兩列數字
1   2   3   4   5   6   7   8   9
        1       1   0   1       0
1   0       0               0       這時候就知道空白該填入什麼了
----------------------------------
1   0   1   0   1   0   1   0   0   所以兩個合併出來的就是漢明碼
                                        也就是（101010100） 

再來舉錯誤更正
題目：101010101

一樣先寫出1-9，這次不用什麼公式了，因為資料就是9位元，而且我們
現在要反推，所以也不用空格
1   2   3   4   5   6   7   8   9
1   0   1   0   1   0   1   0   1   ←同樣由左至右順序填入

再來畫一個表格，照上面所說的填表方式填入
     8   4   2   1
1   0   0   0   1
2   0   0   0   0
3   0   0   1   1
4   0   0   0   0
5   0   1   0   1
6   0   0   0   0
7   0   1   1   1
8   0   0   0   0
9   1   0   0   1
-------------------

這時候可以記一個規則，一行內有奇數個1則線下方填1，反之，有偶數個1
則線下方填0。所以可以把表改成這樣：
     8   4   2   1
1   0   0   0   1
2   0   0   0   0
3   0   0   1   1
4   0   0   0   0
5   0   1   0   1
6   0   0   0   0
7   0   1   1   1
8   0   0   0   0
9   1   0   0   1
-------------------
    1   0   0   1

把線下方取得的二進位碼轉成十進位得到9，這代表第＂9＂個位元出錯了，
所以把原來題目（101010101）的第9個位元（一樣由左往右算）改成0，
得到答案