Hamming Code ECC （漢明碼錯(cuò)誤檢測與修正）

    現(xiàn)在存儲(chǔ)工程師要接觸到RAID 系統(tǒng)中最為復(fù)雜的等級(jí)之一。RAID 2 之所以復(fù)雜就是因?yàn)樗捎昧嗽缙诘腻e(cuò)誤檢測與修正技術(shù)—-漢明碼（Hamming Code ）校驗(yàn)技術(shù)。因此在介紹RAID 2 之前有必要講講漢明碼的原理。

    漢明碼的原理：

圖 1-5 針對(duì)4 位數(shù)據(jù)的漢明碼編碼示意圖

    漢明碼是一個(gè)在原有數(shù)據(jù)中插入若干校驗(yàn)碼來進(jìn)行錯(cuò)誤檢查和糾正的編碼技術(shù)。以典型的4 位數(shù)據(jù)編碼為例，漢明碼將加入3 個(gè)校驗(yàn)碼，從而使實(shí)際傳輸?shù)臄?shù)據(jù)位達(dá)到7 個(gè)（位），它們的位置如果把上圖中的位置橫過來就是：

圖 1-6 漢明碼原理

    注：Dx中的x是2的整數(shù)冪（下面的冪都是指整數(shù)冪）結(jié)果，多少冪取決于碼位，D1是0次冪，D8是3次冪，想想二進(jìn)制編碼就知道了

    現(xiàn)以數(shù)據(jù)碼1101 為例講講漢明碼的編碼原理，此時(shí)D8=1、D4=1、D2=0、D1=1，在P1 編碼時(shí)，先將D8、D4、D1 的二進(jìn)制碼相加，結(jié)果為奇數(shù)3，漢明碼對(duì)奇數(shù)結(jié)果編碼為1，偶數(shù)結(jié)果為0，因此P1 值為1，D8+D2+D1=2 ，為偶數(shù)，那么P2 值為0，D4+D2+D1=2 ，為偶數(shù)，P3 值為0。這樣，參照上文的位置表，漢明碼處理的結(jié)果就是1010101 。在這個(gè)4 位數(shù)據(jù)碼的例子中，存儲(chǔ)工程師可以發(fā)現(xiàn)每個(gè)漢明碼都是以三個(gè)數(shù)據(jù)碼為基準(zhǔn)進(jìn)行編碼的。圖示就是它們的對(duì)應(yīng)表（圖1-6 ）：

    從編碼形式上，存儲(chǔ)工程師可以發(fā)現(xiàn)漢明碼是一個(gè)校驗(yàn)很嚴(yán)謹(jǐn)?shù)木幋a方式。在這個(gè)例子中，通過對(duì)4 個(gè)數(shù)據(jù)位的3 個(gè)位的3 次組合檢測來達(dá)到具體碼位的校驗(yàn)與修正目的（不過只允許一個(gè)位出錯(cuò)，兩個(gè)出錯(cuò)就無法檢查出來了，這從下面的糾錯(cuò)例子中就能體現(xiàn)出來）。在校驗(yàn)時(shí)則把每個(gè)漢明碼與各自對(duì)應(yīng)的數(shù)據(jù)位值相加，如果結(jié)果為偶數(shù)（糾錯(cuò)代碼為0）就是正確，如果為奇數(shù)（糾錯(cuò)代碼為1）則說明當(dāng)前漢明碼所對(duì)應(yīng)的三個(gè)數(shù)據(jù)位中有錯(cuò)誤，此時(shí)再通過其他兩個(gè)漢明碼各自的運(yùn)算來確定具體是哪個(gè)位出了問題。

    還是剛才的1101 的例子，正確的編碼應(yīng)該是1010101 ，如果第三個(gè)數(shù)據(jù)位在傳輸途中因干擾而變成了1，就成了1010111 。檢測時(shí)，P1+D8+D4+D1 的結(jié)果是偶數(shù)4，第一位糾錯(cuò)代碼為0，正確。P1+D8+D2+D1 的結(jié)果是奇數(shù)3，第二位糾錯(cuò)代碼為1，有錯(cuò)誤。P3+D4+D2+D1 的結(jié)果是奇數(shù)3，第三但糾錯(cuò)代碼代碼為1，有錯(cuò)誤。那么具體是哪個(gè)位有錯(cuò)誤呢？三個(gè)糾錯(cuò)代碼從高到低排列為二進(jìn)制編碼110 ，換算成十進(jìn)制就是6，也就是說第6 位數(shù)據(jù)錯(cuò)了，而數(shù)據(jù)第三位在漢明碼編碼后的位置正好是第6 位。

    那么漢明碼的數(shù)量與數(shù)據(jù)位的數(shù)量之間有何比例呢？上面的例子中數(shù)據(jù)位是4 位，加上3 位漢明碼是7 位，而2 的3 次冪是8。這其中就存在一個(gè)規(guī)律，即2P≥P+D+1 ，其中P 代表漢明碼的個(gè)數(shù)，D 代表數(shù)據(jù)位的個(gè)數(shù)，比如4 位數(shù)據(jù)，加上1 就是5，而能大于5 的2 的冪數(shù)就是3 （23=8，22=4）。這樣，存儲(chǔ)工程師就能算出任何數(shù)據(jù)位時(shí)所需要的漢明碼位數(shù)：7 位數(shù)據(jù)時(shí)需要4 位漢明碼（24＞4+7+1），64 位數(shù)據(jù)時(shí)就需要7 位漢明碼（27＞64+7+1 ），大家可以依此推算。此時(shí)，它們的編碼規(guī)也與4 位時(shí)不一樣了。

    另外，漢明碼加插的位置也是有規(guī)律的。以四位數(shù)據(jù)為例，第一個(gè)是漢明碼是第一位，第二個(gè)是第二位，第三個(gè)是第四位，1、2、4 都是2 的整數(shù)冪結(jié)果，而這個(gè)冪次數(shù)是從0 開始的整數(shù)。這樣存儲(chǔ)工程師可以推斷出來，漢明碼的插入位置為1（20）、2（21）、4（22）、8（23）、16（24）、32（25）……
說完漢明碼，下面就開始介紹RAID 2 等級(jí)。

圖 1-7 RAID-2 結(jié)構(gòu)圖解

    RAID 2 等級(jí)介紹：

    由于漢明碼是位為基礎(chǔ)進(jìn)行校驗(yàn)的，那么在RAID2 中，一個(gè)硬盤在一個(gè)時(shí)間只存取一位的信息。沒錯(cuò)，就是這么恐怖。如圖中所示，左邊的為數(shù)據(jù)陣列，陣列中的每個(gè)硬盤一次只存儲(chǔ)一個(gè)位的數(shù)據(jù)。同理，右邊的陣列（存儲(chǔ)工程師稱之為校驗(yàn)陣列）則是存儲(chǔ)相應(yīng)的漢明碼，也是一位一個(gè)硬盤。所以RAID 2 中的硬盤數(shù)量取決于所設(shè)定的數(shù)據(jù)存儲(chǔ)寬度。如果是4 位的數(shù)據(jù)寬度（這由用戶決定），那么就需要4 個(gè)數(shù)據(jù)硬盤和3 個(gè)漢明碼校驗(yàn)硬盤，如果是64 位的位寬呢？從上文介紹的計(jì)算方法中，就可以算出來，數(shù)據(jù)陣列需要64 塊硬盤，校驗(yàn)陣列需要7 塊硬盤。

    在寫入時(shí)，RAID 2 在寫入數(shù)據(jù)位同時(shí)還要計(jì)算出它們的漢明碼并寫入校驗(yàn)陣列，讀取時(shí)也要對(duì)數(shù)據(jù)即時(shí)地進(jìn)行校驗(yàn)，最后再發(fā)向系統(tǒng)。通過上文的介紹，存儲(chǔ)工程師知道漢明碼只能糾正一個(gè)位的錯(cuò)誤，所以RAID 2 也只能允許一個(gè)硬盤出問題，如果兩個(gè)或以上的硬盤出問題，RAID 2 的數(shù)據(jù)就將受到破壞。但由于數(shù)據(jù)是以位為單位并行傳輸，所以傳輸率也相當(dāng)快。

    RAID 2 是早期為了能進(jìn)行即時(shí)的數(shù)據(jù)校驗(yàn)而研制的一種技術(shù)（這在當(dāng)時(shí)的RAID 0、1 等級(jí)中是無法做到的），從它的設(shè)計(jì)上看也是主要為了即時(shí)校驗(yàn)以保證數(shù)據(jù)安全，針對(duì)了當(dāng)時(shí)對(duì)數(shù)據(jù)即時(shí)安全性非常敏感的領(lǐng)域，如服務(wù)器、金融服務(wù)等。但由于花費(fèi)太大（其實(shí)，從上面的分析中可以看出如果數(shù)據(jù)位寬越大，用于校驗(yàn)陣列的相對(duì)投資就會(huì)越小，就如上面的4:3 與64:7）， 成本昂貴，目前已基本不再使用，轉(zhuǎn)而以更高級(jí)的即時(shí)檢驗(yàn)RAID 所代替，如RAID 3、5 等。

圖 1-8 RAID 2 特點(diǎn)

    本文版權(quán)歸作者及存儲(chǔ)在線所有，如需轉(zhuǎn)載，請與本站聯(lián)系。

多易