漢明碼

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

用數學術語來說，漢明碼是一種二元線性碼。對於所有整數 $r \geq 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，2，3，4，5...
將這些數據位的位置序號轉換為二進制，1, 10, 11, 100, 101,等。
數據位的位置序號中所有為二的冪次方的位（編號1，2，4，8，等，即數據位位置序號的二進制表示中只有一個1）是校驗位
所有其它位置的數據位（數據位位置序號的二進制表示中至少2個是1）是新的數據位
每一位的數據包含在特定的兩個或兩個以上的校驗位中，這些校驗位取決於這些數據位的位置數值的二進制表示
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的數。

採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。

校驗位一般的規律可以如下表示：

編碼後數據位置		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
數據位位置		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
奇偶校驗位覆蓋率	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.收集所有二進制數碼，求異或。 $0011\oplus 0101\oplus 1011=1101$

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)漢明碼

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

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

建立奇偶檢驗矩陣

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

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

編碼

範例

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

二進制碼 ${\overrightarrow {x}}$ 的碼詞可以從 ${\overrightarrow {x}}={\overrightarrow {a}}G$ 得到。對 ${\overrightarrow {a}}=a_{1}a_{2}a_{3}a_{4}$ 和 $a_{i}$ 存在 $F_{2}$ (一個只有0和1的二元域）。

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

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

(8,4)漢明碼

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

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

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

\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}

和

\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}

。

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

\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}

。

(11,7)漢明碼

參考文獻

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）（頁面存檔備份，存於互聯網檔案館）

^ See Lemma 12 of (PDF). [2016-09-01]. （原始內容存檔 (PDF)於2021-04-17）.

[1] See Lemma 12 of (PDF). [2016-09-01]. （原始內容存檔 (PDF)於2021-04-17）.

[1]

漢明碼

目次

歷史