(轉)漢明碼簡介
Hamming Code ECC (漢明碼錯誤檢測與修正)
現在存儲工程師要接觸到RAID 系統中最為復雜的等級之一。RAID 2 之所以復雜就是因為它采用了早期的錯誤檢測與修正技術----漢明碼(Hamming Code )校驗技術。因此在介紹RAID 2 之前有必要講講漢明碼的原理。
漢明碼的原理:
圖 1-5 針對4 位數據的漢明碼編碼示意圖
漢明碼是一個在原有數據中插入若干校驗碼來進行錯誤檢查和糾正的編碼技術。以典型的4 位數據編碼為例,漢明碼將加入3 個校驗碼,從而使實際傳輸的數據位達到7 個(位),它們的位置如果把上圖中的位置橫過來就是:
圖 1-6 漢明碼原理
注:Dx中的x是2的整數冪(下面的冪都是指整數冪)結果,多少冪取決于碼位,D1是0次冪,D8是3次冪,想想二進制編碼就知道了
現以數據碼1101 為例講講漢明碼的編碼原理,此時D8=1、D4=1、D2=0、D1=1,在P1 編碼時,先將D8、D4、D1 的二進制碼相加,結果為奇數3,漢明碼對奇數結果編碼為1,偶數結果為0,因此P1 值為1,D8+D2+D1=2 ,為偶數,那么P2 值為0,D4+D2+D1=2 ,為偶數,P3 值為0。這樣,參照上文的位置表,漢明碼處理的結果就是1010101 。在這個4 位數據碼的例子中,存儲工程師可以發現每個漢明碼都是以三個數據碼為基準進行編碼的。圖示就是它們的對應表(圖1-6 ):
從編碼形式上,存儲工程師可以發現漢明碼是一個校驗很嚴謹的編碼方式。在這個例子中,通過對4 個數據位的3 個位的3 次組合檢測來達到具體碼位的校驗與修正目的(不過只允許一個位出錯,兩個出錯就無法檢查出來了,這從下面的糾錯例子中就能體現出來)。在校驗時則把每個漢明碼與各自對應的數據位值相加,如果結果為偶數(糾錯代碼為0)就是正確,如果為奇數(糾錯代碼為1)則說明當前漢明碼所對應的三個數據位中有錯誤,此時再通過其他兩個漢明碼各自的運算來確定具體是哪個位出了問題。
還是剛才的1101 的例子,正確的編碼應該是1010101 ,如果第三個數據位在傳輸途中因干擾而變成了1,就成了1010111 。檢測時,P1+D8+D4+D1 的結果是偶數4,第一位糾錯代碼為0,正確。P1+D8+D2+D1 的結果是奇數3,第二位糾錯代碼為1,有錯誤。P3+D4+D2+D1 的結果是奇數3,第三但糾錯代碼代碼為1,有錯誤。那么具體是哪個位有錯誤呢?三個糾錯代碼從高到低排列為二進制編碼110 ,換算成十進制就是6,也就是說第6 位數據錯了,而數據第三位在漢明碼編碼后的位置正好是第6 位。
那么漢明碼的數量與數據位的數量之間有何比例呢?上面的例子中數據位是4 位,加上3 位漢明碼是7 位,而2 的3 次冪是8。這其中就存在一個規律,即2P≥P+D+1 ,其中P 代表漢明碼的個數,D 代表數據位的個數,比如4 位數據,加上1 就是5,而能大于5 的2 的冪數就是3 (23=8,22=4)。這樣,存儲工程師就能算出任何數據位時所需要的漢明碼位數:7 位數據時需要4 位漢明碼(24>4+7+1),64 位數據時就需要7 位漢明碼(27>64+7+1 ),大家可以依此推算。此時,它們的編碼規也與4 位時不一樣了。
另外,漢明碼加插的位置也是有規律的。以四位數據為例,第一個是漢明碼是第一位,第二個是第二位,第三個是第四位,1、2、4 都是2 的整數冪結果,而這個冪次數是從0 開始的整數。這樣存儲工程師可以推斷出來,漢明碼的插入位置為1(20)、2(21)、4(22)、8(23)、16(24)、32(25)……