Hamming_code

在電信領域中，**漢明碼**（英語：**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 個錯誤控制位就足以確定是否出錯及哪一位出錯了。

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

### 通用算法

下列通用算法可以為任意位數位產生一個可以糾錯一位（英語：**S**ingle **E**rror **C**orrecting）的漢明碼。

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 的數。

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

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

　
:

表中只給出了 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 進行漢明編碼，求編碼後的碼字。

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

2. 把**數據**行有 1 的列的**位置**寫為二進位。

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

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

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

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

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

## (7,4) 漢明碼

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

(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]. ISBN978-0-471-64800-0. （原始內容存檔於 2008-04-06）.
* MacKay, David J.C. Information Theory, Inference and Learning Algorithms. Cambridge: Cambridge University Press. 2003-09. ISBN0-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） （頁面存檔備份，存於網際網路檔案館）