海明碼能夠糾正一位比特的錯誤。一個長度為$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 表示)是編碼系統中碼距的最小值。碼距和糾錯的能力如下:
本節主要討論檢測一位錯誤且糾正一位錯誤的情況,因此最小碼距碼距$D>=3$,需添加的冗餘位的數目需滿足公式(1)
已知原始數據為1001011,采用Hamming Code編碼後,求實際發送的數據?
求解過程如下:
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 ,正好就是發生錯位的位置。
下一篇
(報告出品方/作者:開源證券,諸海濱,趙昊)1、公司情況:深耕智能終端產品,2021年營收上漲39%1.1、發展歷程:成立於2011...