海明碼能夠糾正一位比特的錯誤。一個長度為$m$的數據中增

加$k$位冗餘位，構成一個 n=m+k 位的碼字，然後用 k 個監督關系式產生的 k 個校正因子來檢測和糾正錯誤。為瞭能夠糾正一個比特的錯誤，數據長度和冗餘位的數目必需滿足公式ref{eq:hamming1}，海明碼的編碼效率效為： R=m/(m+k) 。

2^k geq m+k+1 (1)

公式(1)中， m 是數據的長度， k 是海明碼校驗位的個數。

海明碼利用監督公式對數據進行交叉校驗，利用監督公式的特性可以直接定位出錯數據的位置。因為二進制數據中數據的取值隻有兩種狀態0和1，因此隻要知道出錯的位置，修改就變得非常的容易，隻要對出錯位置的數據取反就可以達到糾正的目的。例如接收端收瞭一串二進制數據101011，經過海明碼計算後得到的數字是3，說明數據中的第3位的數據出現瞭錯誤，糾正時隻需要把第三位的1取反變成0即可，糾正後的二進制串是100011。

公式(1)中海明碼雖然可以實現數據的糾錯，但是隻能實現一個比特數據的糾錯。如果數據中有多個比特同時出現錯誤，就必須使用更加復雜的海明公式。海明碼的糾錯能力和最小碼距有關。

碼距是編碼系統中兩個編碼之間不同的二進制的位數，例如數據1010和數據1111的碼距就是2，因為它們的第2和第3位數據不同，數據不同的位數是2，因此碼距是2。最小碼距（用 D 表示）是編碼系統中碼距的最小值。碼距和糾錯的能力如下：

1. 如果要檢測 e 個錯誤，最小碼距應該滿足： D>=e+1
2. 如果要糾正 t 個錯誤，最小碼距應滿足： D>=2t+1
3. 如果要檢測 e 個錯誤同時糾正 t 個錯誤，最小碼距應該滿足： D>=e+t+1 , (e>=t)

本節主要討論檢測一位錯誤且糾正一位錯誤的情況，因此最小碼距碼距$D>=3$，需添加的冗餘位的數目需滿足公式(1)

校驗位計算示例

已知原始數據為1001011,采用Hamming Code編碼後，求實際發送的數據？

求解過程如下：

1. 計算需要的校驗位數目。從題目中可知數據為的長度為7，即 m=7 ，帶入公式 m+k+1le2^k
2. 後得到 k>=4 ，為瞭減少冗餘$k$取最小值4。最後實際發送的數據長度為 7+4=11 位。
3. 重新排列數據。定義4個校驗位分別是 a1, a2, a3, a4 。根據海明碼原則組合排列7為數據和4位校驗碼。校驗碼的位置分別是 1=2^0, 2=2^1, 4= 2^2, 8=2^3 。排列後的順序如表1.4所示。

4. 計算每個校驗位的值。根據圖1.12所示，位置1（ 2^0 )，2（ 2^1 ），4（ 2^2 ），8（ 2^3 ）存放校驗數據。在圖1.12中的最後一列，列名稱是1，數字3，5，7，9，11的二進制數在該列的數據為1，因此位置1對這些位置進行監督，同理，列名為2，4，8的位置對二進制數在該列為1的位置進行校驗。公式1.7是海明碼計算的具體公式，公式中的 X_3 為表1.4中序號/下標為3的數據， X_5 為表1.4中序號/下標為5的數據，其它以此類推。符號 oplus 表示異或運算。把表1.4中的數據帶入公式(1.7)中可以得到：

begin{split} a1&=X_3oplus X_5oplus X_7oplus X_9oplus X_{11} =1oplus0oplus1oplus0oplus1=1\ a2&=X_3oplus X_6oplus X_7oplus X_{10}oplus X_{11} =1oplus0oplus1oplus1oplus1=0\ a3&=X_5oplus X_6oplus X_7 =0oplus0oplus1=1\ a4&= X_9oplus X_{10}oplus X_{11} =0oplus1oplus1=0 end{split} (1.7)

5. 帶入校驗數據得到發送數據。把 a1,a2,a3,a4 分別帶入表1.4中，得到一個新的數據序列 10110010011，這個新序列就是發送端發送出去的數據，也是線路上傳輸的數據。如果數據沒有發生沖突，這也將是接收方收到的數據。

海明碼糾錯

如果接收端收到的數據10110110011,接收方需要先計算校驗位 a1,a2,a3,a4 的值，計算的值再和數據中的校驗位進行異或比較,公式（1.8）為接收端的計算公式：

begin{split} h_1&=X_3oplus X_5oplus X_7oplus X_9oplus X_{11} oplus a1\ h_2&=X_3 oplus X_6oplus X_7oplus X_{10}oplus X_{11}oplus a2\ h_3&= X_5oplus X_6oplus X_7oplus a3\ h_4&=X_9oplus X_{10}oplus X_{11}oplus a4 end{split} （1.8）

公式（1.8）中的監督公式都分為兩個部分，前面的使用 X_i 表示的部分是和發送端一模一樣的計算公式，後面的 ai 是發送端計算不需要的，是數據中的校驗位。這個計算的本意是接收端重新計算一次校驗碼，然後和數據中校驗碼進行比較。如果自己計算的校驗碼和數據中的校驗碼相同，記為0，不同則記為1。

因為在新的數據串中a1和$X_1$是同一個數據位，a2和 X_2 是同一個數據位，a3和 X_4 是同一個數據位，a4和 X_8 是同一個數據位.因此公式（1.8）也可以表示為（1.9）.

begin{split} h_1&=X_3oplus X_5oplus X_7oplus X_9oplus X_{11} oplus X_1\ h_2&=X_3oplus X_6oplus X_7oplus X_10oplus X_{11}oplus X_2\ h_3&=X_5oplus X_6oplus X_7oplus X_4\ h_4&=X_9oplus X_{10}oplus X_{11}oplus X_8 end{split} （1.9）

計算結果按照 h_4h_3 h_2 h_1 的順序進行排列，如果結果等於0說明數據沒有出錯；如果結果不等於0，說明數據出錯。把該數據轉 化為10進制數，就是出錯數據的位置。因為二進制數中每一位置隻有2種狀態，0或者1。因此知道錯誤的位置後，改正錯誤就非常簡單，把對應的數據取反即可。

把接收到的數據 10110110011 代入公式（1.8）中得到：

begin{split} h_1&=1oplus0oplus1oplus0oplus1oplus1=0\ h_2&=1oplus0oplus1oplus1oplus1oplus0=1\ h_3&=0oplus1oplus1oplus1=1\ h_4&=0oplus1oplus1oplus0=0 end{split}

新的數據 h_4h_3h_2h_1=0110 ，轉換為十進制數值為6，因此說明接收到的數據中第6位出錯，將第六位數據取反就可以得到正確的原始數據，原始數據為 10110010011 。

在這個例子中，數據的第6位出錯，接收方在收到數據後按照規則對數據進行重新計算時，發現第2位和第4位存放的校驗結果不正確，將這兩個校驗位的序號相加 2+4=6 ，正好就是發生錯位的位置。