漢明碼檢視原始碼討論檢視歷史

來自 孔夫子舊書網 的圖片

漢明碼是中國科技名詞。

世界上所有的國家中，只有我們中國的文化是始終沒有間斷過的傳承下來，也只有 「漢字」是世界上唯一的古代一直演變過來沒有間斷過的文字形式。

名詞解釋

漢明碼（Hamming Code），是在電信領域的一種線性調試碼，以發明者理查德·衛斯里·漢明的名字命名。漢明碼在傳輸的消息流中插入驗證碼，當計算機存儲或移動數據時，可能會產生數據位錯誤，以偵測並更正單一比特錯誤。由於漢明編碼簡單，它們被廣泛應用於內存（RAM）。

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

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個錯誤控制位就足以確定是否出錯及哪一位出錯了。