- 相關推薦
數(shù)據(jù)存儲系統(tǒng)中的安全衛(wèi)士－－漢明碼
畢業(yè)論文摘要：漢明碼是1種編碼效率極高的差錯控制碼，漢明碼及擴展?jié)h明碼廣泛應用于數(shù)據(jù)存儲系統(tǒng)中。本文在簡單分析漢明碼原理的基礎上，詳細闡述了漢明碼的編碼及糾錯步驟，旨在使讀者理解漢明碼的糾錯過程以及在實際中的廣泛應用。 畢業(yè)論文 論文網(wǎng)
關鍵詞：差錯控制編碼技術；漢明碼；原理；編碼、糾錯步驟
隨著PC機的日益普及，存儲對象的日漸多元化，用戶對存儲需求不斷升級，如何保證數(shù)據(jù)穩(wěn)定、高速傳輸？RAID（“Redundant Array of Independent Disk”）獨立冗余磁盤陣列解決了這個難題，并且成為目前存儲的主流技術。RAID是如何實現(xiàn)數(shù)據(jù)高速、可靠的傳輸呢，1個關鍵的核心技術就是應用了1定的差錯控制編碼技術，在RAID眾多系列中最復雜的RAID 2中就采用了“漢明碼（Hamming Code）差錯控制編碼技術”，它在數(shù)據(jù)存儲及移動過程中進行差錯控制，對傳輸過程中出現(xiàn)的差錯自動進行糾正，保證了數(shù)據(jù)傳輸?shù)陌踩煽啃浴９P者在這里將闡述漢明碼的編碼原理，并剖析漢明碼編碼糾錯過程。
1：漢明碼的應用與原理
漢明碼是1950年由美國貝爾實驗室漢明(也有譯為海明)提出來的，是第1個設計用來糾錯的分組碼。目前，漢明碼及其變形已廣泛地應用在數(shù)字通信、數(shù)據(jù)通信中的數(shù)據(jù)存儲系統(tǒng)中，尤其在計算機的內(nèi)存尋址及RAM與寄存器之間來回傳送比特位時經(jīng)常使用。
漢明碼是在原編碼的基礎上附加1部分代碼，使其滿足糾錯碼的條件，原編碼我們可將它稱為信息碼，附加碼稱為校驗碼(又可稱為監(jiān)督碼或冗余碼)。漢明碼碼距為3，所以只能夠發(fā)現(xiàn)2個錯誤或糾正1個錯誤，編碼效率最高。它屬于線性分組碼，由于線性碼的編碼和譯碼容易實現(xiàn)，至今仍是應用最廣泛的1類碼。
2：漢明碼編碼過程
漢明碼編碼可遵循以下四個步驟：
1。 由信息位數(shù)，根據(jù)漢明不等式，確定校驗位數(shù)
2。確定校驗碼位置 畢業(yè)論文 論文網(wǎng)
3。確定校驗碼的值
4。求出漢明碼
實例：若有17位長的信息碼為1001101，請求出漢明碼。
步驟1：校驗位數(shù)的確定
由漢明不等式2r-1≥n 或 2r≥k+r+1(其中r為檢驗碼位數(shù)， k為信息碼位數(shù)，n為編碼后的碼總長)可知，在本題中k=7，代入2r≥k+r+1公式中可解得r 的取值為4，即需要4位檢驗碼（可依次編為r0、r1、r2、r3），則總碼長n=k+r=7+4=11。
步驟2：確定校驗碼位置
從理論上講校驗碼位可放在任何位置，但習慣上將它放于位置1，2，4，8……等位置，對于校驗位少的可用強記法記住所在位置，而對于位數(shù)較多的強記法就不適用，在這里介紹1種公式法，不用死記硬背，即可求出各校驗碼的位置。
校驗位rn對應的位置為2n，n的取值從0開始，則：
r0=20=1 r1=21=2 r2=22=4 r3=23=8
將校驗位填在表格1對應的單元格內(nèi)，其余位用信息碼填充。表格1中，位數(shù)是指數(shù)據(jù)存放在第幾位，共11位，用In表示(n的取值從1至11)。
11 10 9 8 7 6 5 4 3 2 1 位數(shù)
1 0 0 r3 1 1 0 r2 1 r1 r0 編碼
表格 1
步驟3：確定校驗碼的值
確定校驗碼的值是個較繁瑣的過程，遵循以下幾個步驟：
首先，將信息碼所對應的位數(shù)寫成2的冪之和的形式。在實例中我們知道信息碼對應的位數(shù)有I11、I10、I9、I7、I6、I5、I3等7位，相應的值寫成如下形式：
11=23+21+20 10=23+21 9=23+20 7=22+21+20 6=22+21 5=22+20 3=21+20
其次，校驗位rn由信息碼對應位數(shù)的冪之和形式中包含有n的信息碼異或而得，從表格1分析可知， r0的值由I11（信息碼為1）、I9（信息碼為0）、I7位（信息碼為1）、I5位（信息碼為0）、I3（信息碼為1）對應的信息碼異或而得，
則r0=1○+0○+1○+0○+1=1
依此類推：
r1=1○+0○+1○+1○+1=0
r2==1○+1○+0=0
r3==1○+0○+0=1
步驟4：求出漢明碼
將校驗位rn的值填充到表格1中，即可求出漢明碼為10011100101。
11 10 9 8 7 6 5 4 3 2 1 位數(shù)
1 0 0 1 1 1 0 0 1 0 1 漢明碼
表格 2
三：漢明碼糾錯步驟
實例1中，由7位信息碼，求出了漢明碼為10011100101，若該編碼傳輸被接收時，第7位變成了0，接收端如何來判斷并且糾正錯誤呢？
11 10 9 8 7 6 5 4 3 2 1 位數(shù)
1 0 0 1 1 1 0 0 1 0 1 漢明碼
1 0 0 1 0 1 0 0 1 0 1 出錯的漢明碼
表格 3
在漢明碼中，通過校驗因子進行驗證，校驗因子公式為Sn=rn(校驗碼) ○+ Rn(接收碼)
rn(校驗碼)即為所對應的r的取值，Rn(接收碼)為由信息碼對應位數(shù)的冪之和形式中包含有n的信息碼異或而得。
如表格4所示，出錯的第7位數(shù)據(jù)用藍色顯示，黃色表示校驗位，黑色表示信息位。
S0=r0(校驗碼) ○+ R0(接收碼)=1○+1○+0○+0○+0○+1=1
S1=r1(校驗碼) ○+ R1(接收碼)=0○+1○+1○+0○+0○+1=1
S2=r2(校驗碼) ○+ R2(接收碼)=0○+0○+1○+0=1
S3=r3(校驗碼) ○+ R3(接收碼)=1○+0○+0○+1=0
求出來的S3S2S1S0=0111（即十進制7），該數(shù)指示了發(fā)生錯誤的比特的準確位置是第7位，1旦確定了錯誤的位置，接收方就可在將該位糾正過來，在本題中將0改為1，這樣就起到了糾錯的作用。
11 10 9 8 7 6 5 4 3 2 1 位數(shù)
1 0 0 1 0 1 0 0 1 0 1 出錯的漢明碼
表格 4
結束語
本文從RAID 2中應用漢明碼進行糾錯為出發(fā)點，闡述了漢明碼的原理及應用方向，通過實例，對如何進行漢明碼編碼及漢明碼如何進行糾錯進行了詳解。
參考文獻：
[ 1 ] 李斯偉 雷新生 數(shù)據(jù)通信技術 人民郵電出版社 2004
[ 2 ] Bernard Sklar著 數(shù)字通信—基礎與應用研究 電子工業(yè)出版社 2003 畢業(yè)論文 論文網(wǎng)
【數(shù)據(jù)存儲系統(tǒng)中的安全衛(wèi)士－－漢明碼】相關文章：
企業(yè)數(shù)據(jù)標準化中數(shù)據(jù)元素理論的應用研究07-15
數(shù)據(jù)挖掘技術在電信行業(yè)中的應用06-04
ERP系統(tǒng)中數(shù)據(jù)倉庫的應用06-16
數(shù)據(jù)的完整性在數(shù)據(jù)庫應用系統(tǒng)中的設計與實施05-06
Delphi 5 數(shù)據(jù)庫應用中ODBC數(shù)據(jù)源的自動管理09-13