汉明码

在電信領域中，漢明碼（），也称为海明码，是推广得到的一種线性纠错码，由理查德·衛斯里·漢明于1950年發明。相比而言，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。汉明码是，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。

用數學术语来说，漢明碼是一種二元線性碼。對於所有整數 ，存在一个分组长度 、 编码。因此汉明码的码率为 ，对于最小距离为3、分组长度为  的码来说是最高的。漢明碼的奇偶檢驗矩陣的是通過列出所有长度为  的非零列向量构成的。

 歷史 
漢明碼的發明者理查德·衛斯里·漢明在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个错误控制位元就足以確定是否出錯及哪一位元出錯了。

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

 通用算法 
下列通用算法可以为任意位元数字产生一个可以纠错一位元（）的漢明碼。

 從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的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有区别。

校验位元一般的规律可以如下表示：

 {| class="wikitable" style="text-align:center;"
|-
!colspan="2"| 数据位元位置
! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 !! 17 !! 18 !! 19 !! 20
|rowspan="7"| ...
|-
!colspan="2"| 编码后数据位置
!style="background-color: #90FF90;"| p1
!style="background-color: #90FF90;"| p2 !! d1
!style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4
!style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11
!style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15
|-
!rowspan="5"|奇偶校驗位元覆蓋率
!style="background-color: #90FF90;"| p1
| X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X ||   || X || 
|-
!style="background-color: #90FF90;"| p2
|   || X || X ||   ||   || X || X ||   ||   || X || X ||   ||   || X || X ||   ||   || X || X || 
|-
!style="background-color: #90FF90;"| p4
|   ||   ||   || X || X || X || X ||   ||   ||   ||   || X || X || X || X ||   ||   ||   ||   || X
|-
!style="background-color: #90FF90;"| p8
|   ||   ||   ||   ||   ||   ||   || X || X || X || X || X || X || X || X ||   ||   ||   ||   || 
|-
!style="background-color: #90FF90;"| 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进行汉明编码，求编码后的码字。

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. 收集所有二进制数字，求异或。

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

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

 建立奇偶檢驗矩陣 

矩陣被稱為（標準）生成矩陣線性(n,k)碼。

和被稱為奇偶檢驗矩陣。

 編碼 

範例

从上述矩阵我们有2k=24=16码词。

二进制码的码词可以从得到。对和存在(一个只有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)汉明码）上附加一个额外的奇偶位元。

这可以用下面修正的矩阵相加：



和

 。

注意，并非用标准形式表示。为了得到，原子行操作能够被用来获得一个等价的矩阵对陈形式的：

 。

 (11,7)漢明碼 

 相關條目 
 格雷碼
 漢明距離
 前向錯誤更正
 里德-所罗门码

 參考文獻 




 外部連結 
 CGI script for calculating Hamming distances（from R. Tervo, UNB, Canada） 

Category:美国发明
Category:编码理论
Category:错误检测与校正
Category:計算機算術