漢明碼

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

1940年，漢明於貝爾實驗室（Bell Labs）工作，運用貝爾模型V（Bell Model V）電腦，一個週期時間在幾秒鐘內的機電繼電器機器。輸入端是依靠打孔卡（Punched Card），這不免有些讀取錯誤。在平日，特殊代碼將發現錯誤並閃燈（flash lights），使得操作者能夠糾正這個錯誤。在週末和下班期間，在沒有操作者的情況下，機器只會簡單地轉移到下一個工作。漢明在週末工作，他對於不可靠的讀卡機發生錯誤後，總是必須重新開始項目變得愈來愈沮喪。在接下來的幾年中，他為了解決調試的問題，開發了功能日益強大的調試算法。在1950年，他發表了今日所稱的漢明碼。現在漢明碼有着廣泛的應用。

與其他的錯誤校驗碼類似，漢明碼也利用了奇偶校驗位的概念，通過在數據位後面增加一些比特，可以驗證數據的有效性。利用一個以上的校驗位，漢明碼不僅可以驗證數據是否有效，還能在數據出錯的情況下指明錯誤位置。

在接收端通過糾錯譯碼自動糾正傳輸中的差錯來實現碼糾錯功能，稱為前向糾錯FEC。在數據鏈路中存在大量噪音時，FEC可以增加數據吞吐量。通過在傳輸碼列中加入冗餘位(也稱糾錯位)可以實現前向糾錯。但這種方法比簡單重傳協議的成本要高。漢明碼利用奇偶塊機制降低了前向糾錯的成本。

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

漢明碼SECDED（single error correction, double error detection）版本另外加入一檢測比特，可以偵測兩個或以下同時發生的比特錯誤，並能夠更正單一比特的錯誤。因此，當發送端與接收端的比特樣式的漢明距離（Hamming distance）小於或等於1時（僅有1 bit發生錯誤），可實現可靠的通信。相對的，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。

下列通用算法可以為任意位數字產生一個可以糾錯一位的漢明碼：

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

採用奇校驗還是偶校驗都是可行的。偶校驗從數學的角度看更簡單一些，但在實踐中並沒有區別。校驗位一般的規律可以如下表示：

觀察上表可發現一個比較直觀的規律：第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] 

奇偶校驗是一種添加一個奇偶位用來指示之前的數據中包含有奇數還是偶數個1的檢驗方式。如果在傳輸的過程中，有奇數個位發生了改變，那麼這個錯誤將被檢測出來（注意奇偶位本身也可能改變）。一般來説，如果數據中包含有奇數個1的話，則將奇偶位設定為1；反之，如果數據中有偶數個1的話，則將奇偶位設定為0。換句話説，原始數據和奇偶位組成的新數據中，將總共包含偶數個1. 奇偶校驗並不總是有效，如果數據中有偶數個位發生變化，則奇偶位仍將是正確的，因此不能檢測出錯誤。而且，即使奇偶校驗檢測出了錯誤，它也不能指出哪一位出現了錯誤，從而難以進行更正。數據必須整體丟棄並且重新傳輸。在一個噪音較大的媒介中，成功傳輸數據可能需要很長時間甚至不可能完成。雖然奇偶校驗的效果不佳，但是由於他只需要一位額外的空間開銷，因此這是開銷最小的檢測方式。並且，如果知道了發生錯誤的位，奇偶校驗還可以恢復數據。 如果一條信息中包含更多用於糾錯的位，且通過妥善安排這些糾錯位使得不同的出錯位產生不同的錯誤結果，那麼我們就可以找出出錯位了。在一個7位的信息中，單個數據位出錯有7種可能，因此3個錯誤控制位就足以確定是否出錯及哪一位出錯了。 ^[2] 

一般來説，若漢明碼長為n，信息位數為k，則監督位數r=n-k。若希望用r個監督位構造出r個監督關係式來指示一位錯碼的n種可能位置，則要求

2^r-1≥n或2^r≥k+r+1 ^[3] 

現以數據碼1101為例説明漢明碼編碼原理，此時D1=1、D2=1、D3=0、D4=1，在P1編碼時，先將D1、D2、D4的二進制碼相加，結果為奇數3，校驗碼P1對奇數結果編碼為1，偶數結果為0（偶校驗法），因此，

D1+D2+D4=3,P1=1;

D1+D3+D4=2,P2=0;

D2+D3+D4=2,P3=0;

這樣，參照上文的位置表（P1 P2 D1 P3 D2 D3 D4），漢明碼處理的結果就是：1010101

在這個4位數據碼的例子中，我們可以發現每個校驗碼都是以三個數據碼為基準進行編碼的。

從編碼形式上，我們可以發現漢明碼是一個校驗很嚴謹的編碼方式。在這個例子中，通過對4個數據位的3個位的3次組合檢測來達到具體碼位的校驗與修正目的（不過只允許一個位出錯；大於1且偶數個位出錯時，校驗反而是正確的，造成誤判；大於1且奇數個位出錯則無法定位）。在校驗時則把每個校驗碼與各自對應的數據位值相加，如果結果為偶數（糾錯代碼為0）就是正確，如果為奇數（糾錯代碼為1）則説明當前漢明碼所對應的三個數據位中有錯誤，此時再通過其他兩個校驗碼各自的運算來確定具體是哪個位出了問題。

還是剛才的1101的例子，正確的編碼應該是1010101，對應P1 P2 D1 P3 D2 D3 D4。

如果第五個數據位在傳輸途中因干擾而變成了0，就成了1010001, 即 D2=0。

檢測時：

1）P1=D1 + D2 + D4=1 + 0 + 1=2，除以2餘數0，原來第一位糾錯代碼為1，錯誤，説明P1 D4 D2 D1中有一位是錯誤的。

2）P2=D1 + D3 + D4=1 + 0 + 1=2，除以2餘數0，正確，説明P2 D4 D3 D1都是正確的，這裏結合上邊已經可以得出只有P1和D2中一個是錯誤的。

3）P3=D2 + D3 + D4=0 + 0 + 1 =1，除以2餘數1，而原來第三位糾錯代碼為0，有錯誤，由上邊2）知道D4和D3是正確的，那麼這裏説明只有P3和D2中一個是錯誤的。

綜合以上，可以得出這個結論：D2出錯了。 ^[4] 

那麼漢明碼的數量與數據位的數量之間有何比例呢？上面的例子中數據位是4位，加上3位漢明碼是7位，而2的3次冪是8。這其中就存在一個規律，即2^P≥P+D+1，其中P代表漢明碼的個數，D代表數據位的個數，比如4位數據，加上1就是5，而能大於5的2的冪數就是3（2^3=8，2^2=4）。這樣，我們就能算出任何數據位時所需要的漢明碼位數：7位數據時需要4位漢明碼（16>4+7+1），64位數據時就需要7位漢明碼（128>64+7+1），大家可以依此推算。此時，它們的編碼規也與4位時不一樣了。