當計算機存儲或移動數據時,可能會產生數據位錯誤,這時可以利用漢明碼來檢測并糾錯,簡單的說,漢明碼是一個錯誤校驗碼碼集,由Bell 實驗室的R.W.Hamming 發明,因此定名為漢明碼。
漢明碼(Hamming Code),是在電信領域的一種線性調試碼,以發明者理查德·衛斯里·漢明的名字命名。漢明碼在傳輸的消息流中插入驗證碼,以偵測并更正單一比特錯誤。由于漢明編碼簡單,它們被廣泛應用于內存(RAM )。其SECDED (single error correction, double error detection)版本另外加入一檢測比特,可以偵測兩個或以下同時發生的比特錯誤,并能夠更正單一比特的錯誤。因此,當發送端與接收端的比特樣式的漢明距離(Hamming distance)小于或等于1時(僅有1 bit發生錯誤),可實現可靠的通信。相對的,簡單的奇偶檢驗碼除了不能糾正錯誤之外,也只能偵測出奇數個的錯誤。
在數學方面,漢明碼是一種二元線性碼。對于每一個整數,存在一個編碼,帶有個奇偶校驗位個數據位。該奇偶檢驗矩陣的漢明碼是通過列出所有米欄的長度是兩兩獨立。
漢明碼的定義和漢明碼不等式:
設:m=數據位數,k=校驗位數為,n=總編碼位數=m+k,有Hamming不等式:

漢明碼不等式含義:
a) 總數據長度為N,如果每一位數據是否錯誤都要記錄,就需要N位來存儲。
b) 每個校驗位都可以表示:對或錯;校驗位共K位,共可表示2k種狀態
c) 總編碼長度為N,所以包含某一位錯和全對共N+1種狀態。
d) 所以2k≧N+1 e) 數據表見下

Hamming碼缺點:
無法實現2位或2位以上的糾錯,Hamming碼只能實現一位糾錯。
以典型的4位數據編碼為例,演示漢明碼的工作過程
a) 數據存儲格式:

依照此前的漢明碼不等式計算出,當數據位為4位時,漢明碼校驗位至少為3位,如上方式排列
可以看的出D8、D4、D2、D1中的數字都是2的整數冪
b) 漢明校驗碼的插入規律:
設:編碼位代號k,校驗碼位代號p,數據位代號n
某個校驗碼Pp將處于整個編碼的第k位
k=2^(p-1)=2的(p-1)次方
以數據位為5的一組9位數編碼為例,如下:

c) 校驗位與數據位的對應關系:
注:^是邏輯運算符異或。
P1=D8^D4^D1
P2=D8^D2^D1
P3=D4^D2^D1
小解釋:數據位共4位每行等式都缺少一位,而缺少的這位數據位正好是DX,等式左邊的校驗位為PY,X=2y.
d) 校驗位如何參與計算:
P1’=P1^D8^D4^D1
P2’=P2^D8^D2^D1
P3’=P3^D4^D2^D1
從高到低排列的二進制數:P3’ P2’ P1’表示的就是出錯的編碼位,從000-011-101-110-111共5種組合,可表示原數據位D8D4D2D1某一位錯&沒錯的一共5種狀態。
e) 設有一數字為:1101,帶入運算:
D8=1、D4=1、D2=0、D1=1,
P1 =1,P2=0、P3=0。
漢明碼處理的結果就是1010101
假設:D8出錯,P3’ P2’ P1’=011=十進制的3,即表示編碼后第三位出錯,對照存儲格式表,果然就是D8錯誤。
假設:D4錯誤,P3’ P2’ P1’=101=十進制的5,即表示編碼后第五位出錯,對照存儲格式表,果然就是D4錯誤。
-
漢明碼
+關注
關注
0文章
8瀏覽量
8268
發布評論請先 登錄
基于FPGA的漢明碼譯碼器如何對碼元數據添加噪聲干擾?
【原創】基于FPGA的漢明碼編碼解碼設計
提高漢明碼對突發干擾的糾錯能力
PIC單片機串行通信中的漢明編碼自動檢糾錯
一種基于漢明碼和濕紙碼的隱寫算法
利用FPGA實現模式可變的衛星數據存儲器糾錯系統
基于FPGA的檢糾錯邏輯算法的實現
漢明碼計算及其糾錯原理詳解
評論