漢明碼

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

用數學術語來說，漢明碼是一種二元線性碼。對於所有整數 r ≥ 2，存在一個分組長度 n = 2r − 1、k = 2r − r − 1 編碼。因此漢明碼的碼率為 R = k / n = 1 − r / (2r − 1)，對於最小距離為3、分組長度為 2r − 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（校驗位元自身，這裡都是二進位，下同），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

表中只給出了20個編碼後的位元（5個奇偶校驗位元，15個數據位元）。觀察上表可發現一個比較直觀的規律：第i個檢驗位元是第2i-1位元，從該位元開始，檢驗2i-1位元，跳過2i-1位元......依次類推。例如上表中第3個檢驗位元p4從第23-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進行漢明編碼，求編碼後的碼字。

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

位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12

數據｜1｜1｜0｜0｜0｜0｜1｜0

- 把數據行有1的列的位置寫為二進位。

位置｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜12

數據｜1｜1｜0｜0｜0｜0｜1｜0

二進位｜0011｜0101｜1011

- 收集所有二進位數字，求異或。$0011 \oplus 0101 \oplus 1011 =1101$

- 把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

- 所以編碼後的碼字是101110010010。

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

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

## (7,4)漢明碼

<image>

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}$被稱為奇偶檢驗矩陣。

## 編碼

範例

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

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

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

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

## (8,4)漢明碼

<image>

(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}$。

## 外部連結

- CGI script for calculating Hamming distances（from R. Tervo, UNB, Canada）