數據存儲系統中的安全衛士－－漢明碼

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

【數據存儲系統中的安全衛士－－漢明碼】相關(guān)文章：

數據挖掘在ＣＲＭ中的應用分析06-09

數據挖掘技術(shù)在ＣＲＭ中的應用09-20

企業(yè)數據標準化中數據元素理論的應用研究07-15

數據挖掘技術(shù)在電信行業(yè)中的應用06-04

數據挖掘技術(shù)在飯店營(yíng)銷(xiāo)中的運用08-11

ERP系統中數據倉庫的應用06-16

數據的完整性在數據庫應用系統中的設計與實(shí)施05-06

Delphi 5 數據庫應用中ODBC數據源的自動(dòng)管理09-13

淺析數據融合技術(shù)及其在林業(yè)中的應用08-12

淺談數據挖掘在電子商務(wù)中的應用10-08