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