漢明碼

在電信領域中，漢明碼（英語：hamming code），也稱為海明碼，是(7,4)漢明碼推廣得到的一種線性錯誤更正碼，由理察·衛斯里·漢明於1950年發明。相比而言，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。漢明碼是完整碼，它在於它封包長度相同、最小距離為3的碼中能達到最高的位元速率。

用數學術語來說，漢明碼是一種二元線性碼。對於所有整數 r ≥ 2，存在一個封包長度 n = 2^r − 1、k = 2^r − r − 1 編碼。因此漢明碼的位元速率為 R = k / n = 1 − r / (2^r − 1)，對於最小距離為3、封包長度為 2^r − 1 的碼來說是最高的。漢明碼的奇偶檢驗矩陣的是通過列出所有長度為 r 的非零列向量構成的。

歷史

漢明碼的發明者理察·衛斯里·漢明在1948年，運用貝爾模型V（Bell Model V）電腦於貝爾實驗室（Bell Labs）工作。輸入端是依靠打孔卡（Punched Card），這不免會造成些讀取錯誤。在工作日，當機器檢測到錯誤將停止並閃燈（flash lights），使得操作員能夠解決這個錯誤。在週末和下班期間，沒有操作者的情況下，機器只會簡單地轉移到下一個工作。

漢明在週末工作，他對於不可靠的讀卡機發生錯誤後，總是不得不重新啟動程式變得愈來愈沮喪。在接下來的幾年中，他為了解決偵錯的問題，開發了功能日益強大的偵錯演算法。在1950年，他發表了今日所稱的漢明碼，並且時至今日仍在修正錯誤記憶體上顯示其應用價值。

漢明碼之前

人們在漢明碼出現之前使用過多種檢查錯誤的編碼方式，但是沒有一個可以在和漢明碼在相同空間消耗的情況下，得到相等的效果。

奇偶

主條目：奇偶校驗位

奇偶校驗是一種添加一個奇偶位元用來指示之前的資料中包含有奇數還是偶數個1的檢驗方式。如果在傳輸的過程中，有奇數個位元發生了改變，那麼這個錯誤將被檢測出來（注意奇偶位元本身也可能改變）。一般來說，如果資料中包含有奇數個1的話，則將奇偶位元設定為1；反之，如果資料中有偶數個1的話，則將奇偶位元設定為0。換句話說，原始資料和奇偶位元組成的新資料中，將總共包含偶數個1.

奇偶校驗並不總是有效，如果資料中有偶數個位元發生變化，則奇偶位元仍將是正確的，因此不能檢測出錯誤。而且，即使奇偶校驗檢測出了錯誤，它也不能指出哪一位元出現了錯誤，從而難以進行更正。資料必須整體丟棄並且重新傳輸。在一個噪音較大的媒介中，成功傳輸資料可能需要很長時間甚至不可能完成。雖然奇偶校驗的效果不佳，但是由於他只需要一位元額外的空間開銷，因此這是開銷最小的檢測方式。並且，如果知道了發生錯誤的位元，若將該位元取反，奇偶校驗還可以恢復資料。

五取二碼

五取二碼使用由3個0和2個1組成的五個位元，以此提供十種可能的組合來表示數字 0-9。 該方案可以檢測所有單位元錯誤、所有奇數位元錯誤和一些偶數位元錯誤（例如兩個 「1」位元的翻轉）。 但是它無法自行糾正這些錯誤。

漢明碼

如果一條資訊中包含更多用於糾錯的位元，且通過妥善安排這些糾錯位元使得不同的出錯位元產生不同的錯誤結果，那麼我們就可以找出出錯位元了。在一個7位元的資訊中，單個位元出錯有7種可能，因此3個錯誤控制位元就足以確定是否出錯及哪一位元出錯了。

漢明研究了包括五取二碼在內的編碼方案，並歸納了他們的想法。

通用演算法

下列通用演算法可以為任意位元數位產生一個可以糾錯一位元（英語：Single Error Correcting）的漢明碼。

1. 從1開始給數字的數據位元（從左向右）標上序號, 1，2，3，4，5...
2. 將這些資料位元的位置序號轉換為二進制，1, 10, 11, 100, 101,等。
3. 資料位元的位置序號中所有為二的冪次方的位元（編號1，2，4，8，等，即資料位元位置序號的二進制表示中只有一個1）是校驗位元
4. 所有其它位置的資料位元（資料位元位置序號的二進制表示中至少2個是1）是新的資料位元
5. 每一位元的資料包含在特定的兩個或兩個以上的校驗位元中，這些校驗位元取決於這些資料位元的位置數值的二進制表示
   1. 校驗位元1覆蓋了所有資料位元位置序號的二進制表示倒數第一位元是1的資料：1（校驗位元自身，這裡都是二進制，下同），11，101，111，1001，等
   2. 校驗位元2覆蓋了所有資料位元位置序號的二進制表示倒數第二位元是1的資料：10（校驗位元自身），11，110，111，1010，1011，等
   3. 校驗位元4覆蓋了所有資料位元位置序號的二進制表示倒數第三位元是1的資料：100（校驗位元自身），101，110，111，1100，1101，1110，1111，等
   4. 校驗位元8覆蓋了所有資料位元位置序號的二進制表示倒數第四位元是1的資料：1000（校驗位元自身），1001，1010，1011，1100，1101，1110，1111，等
   5. 簡而言之，所有校驗位元覆蓋了資料位置和該校驗位元位置的二進制與的值不為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

表中只給出了20個編碼後的位元（5個奇偶校驗位元，15個資料位元）。觀察上表可發現一個比較直觀的規律：第i個核對位元元是第2^i-1位元，從該位元開始，檢驗2^i-1位元，跳過2^i-1位元......依次類推。例如上表中第3個核對位元元p4從第2^3-1=4位元開始，檢驗4、5、6、7共4位元，然後跳過8、9、10、11共4位元，再檢驗12、13、14、15共4位元......

要檢查某一位元的錯誤，則需檢查某一位元所包含的所有奇偶校驗位元。這種錯誤的模式被叫做伴隨式錯誤。如果所有奇偶校驗位元是正確的，就沒有錯誤。除此以外的情況，錯誤的奇偶校驗位元的位置的和將辨識錯誤的位元。例如，如果位置為1、2、8的奇偶校驗位元指示了一個錯誤，那麼位置為1+2+8=11的位元出錯了。如果只有一個奇偶校驗位元指示了錯誤，那麼該奇偶校驗位元自身出錯了。

例子

對11000010進行漢明編碼，求編碼後的碼字。

1. 列出表格，從左往右（或從右往左）填入數位，但2的次方的位置不填。

位置	1	2	3	4	5	6	7	8	9	10	11	12
資料			1		1	0	0		0	0	1	0

2. 把資料行有1的列的位置寫為二進制。

位置	1	2	3	4	5	6	7	8	9	10	11	12
資料			1		1	0	0		0	0	1	0
二進制			0011		0101						1011

3. 收集所有二進制數位，求互斥或。<math>0011 \oplus 0101 \oplus 1011 =1101</math>

4. 把1101依次填入表格中2的次方的位置（低位元在左）。

位置	1	2	3	4	5	6	7	8	9	10	11	12
資料			1		1	0	0		0	0	1	0
二進制			0011		0101						1011
校驗	1	0		1				1

5. 所以編碼後的碼字是101110010010。

帶附加奇偶校驗碼的漢明碼（SECDED）

加一個位元元在數列的最前面，採用奇校驗碼或偶校驗碼， 用以檢驗後面的漢明碼是否有錯。

(7,4)漢明碼

File:Hamming(7,4).svg

Graphical depiction of the 4 data bits and 3 parity bits and which parity bits apply to which data bits

主條目：(7,4)漢明碼

1950年，漢明發明了(7,4)代碼。其編碼由4資料位元元到7位元，增加三個奇偶校驗碼。(7,4)漢明碼可以檢測並糾正單位元元錯誤，且也能檢測雙位元元錯誤。

建立奇偶檢驗矩陣

矩陣<math>\mathbf{G} := \begin{pmatrix} I_k | -A^T \\ \end{pmatrix}</math>被稱為（標準）生成矩陣線性(n,k)碼。

和<math>\mathbf{H} := \begin{pmatrix} A | I_{n-k} \\ \end{pmatrix}</math>被稱為奇偶檢驗矩陣。

編碼

範例

從上述矩陣我們有2^k=2⁴=16碼詞。

二進制碼<math> \overrightarrow{x}</math>的碼詞可以從<math>\overrightarrow{x}=\overrightarrow{a}G </math>得到。對<math>\overrightarrow{a}=a_1a_2a_3a_4 </math>和<math> a_i </math>存在<math> F_2 </math>(一個只有0和1的二元域）。

故此碼表即是所有4個三元組（k個三元組）。

因而，（1,0,1,1）編碼為（0,1,1,0,0,1,1）。

(8,4)漢明碼

File:Hamming(8,4).svg

The same (7,4) example from above with an extra parity bit

(7,4)漢明碼可以很容易地編碼為一個(8,4)碼，通過在(7,4)編碼詞（參見(7,4)漢明碼）上附加一個額外的奇偶位元。

這可以用下面修正的矩陣相加：

<math>\mathbf{G} := \begin{pmatrix}

1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}_{8,4}</math>

和

<math>

\mathbf{H} := \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}_{4,8} </math>。

注意，<math>\mathbf{H}</math>並非用標準形式表示。為了得到<math>\mathbf{G}</math>，原子行操作能夠被用來獲得一個等價的矩陣對陳形式的<math>\mathbf{H}</math>：

<math>

\mathbf{H} = \left(\left.\begin{array}{cccc} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0\end{array}\right|\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{array}\right)_{4,8} </math>。

相關條目

• 格雷碼
• 漢明距離
• 前向錯誤更正
• 里德-所羅門碼

參考文獻

• Moon, Todd K. Error Correction Coding. New Jersey: John Wiley & Sons. 2005 [2009-06-18]. ISBN 978-0-471-64800-0. （原始內容存檔於2008-04-06）. 
• MacKay, David J.C. Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. 2003-09. ISBN 0-521-64298-1. （原始內容存檔於2016-02-17）. 
• D.K. Bhattacharryya, S. Nandi. An efficient class of SEC-DED-AUED codes. 1997 International Symposium on Parallel Architectures, Algorithms and Networks（ISPAN '97）: 410–415. doi:10.1109/ISPAN.1997.645128. 

外部連結

• CGI script for calculating Hamming distances（from R. Tervo, UNB, Canada） （頁面存檔備份，存於網際網路檔案館）