錯誤更正-漢明碼

漢明碼

漢明碼
所謂漢明碼(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的數。
採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。

資料位位置		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
編碼後資料位置		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
奇偶校驗位 覆蓋率	p1	X		X		X		X		X		X		X		X		X		X
	p2		X	X			X	X			X	X			X	X			X	X
	p4				X	X	X	X					X	X	X	X					X
	p8								X	X	X	X	X	X	X	X
	p16																X	X	X	X	X