【正文】 NODD碼實現(xiàn)存儲系統(tǒng)的容錯仿真。利用隨意的 5張圖片模擬存儲系統(tǒng)中存儲 的 數(shù)據(jù)，然后利用 EVENODD 編碼技術(shù)，生成 2 個校驗數(shù)據(jù)存于另外存儲設(shè)備中（即兩張校驗圖片）。隨機破壞其中的一張或者兩張數(shù)據(jù)，利用 EVENODD 的譯碼算法將這2 張圖片的數(shù)據(jù)恢復(fù)出來。整個仿真過程將在一個界面友好的應(yīng)用軟件中實現(xiàn)。 2 EVENODD 碼 預(yù)先定義 為了方便本文后面的敘述，先定義本文一些符號記法： nm = j 表示 j ≡ n(mod m) （ 0 ≤ j ≤ m+1） 。例如： 75 = 2， 25 = 3。 另外我 們還對本原理做一些必要的假設(shè)： 1) 設(shè)存在 m+2 列數(shù)據(jù)塊，其中前 m個數(shù)據(jù)塊依次存有信息，校驗信息將存儲在最后兩列數(shù)據(jù)塊。這樣將在所有的數(shù)據(jù)塊中形成冗余以避免在重復(fù)寫操作時形成瓶頸。 2) 設(shè) m 列數(shù)據(jù)塊中每一個數(shù)據(jù)塊只有 m1 行。對于任意容量的數(shù)據(jù)塊，可以預(yù)先分割成 m1 行的塊分別進行處理。為簡單起見，在本文中假設(shè)每一個標識位大小為1bit（不過在一些應(yīng)用程序當中，一個標識位可能大到 512 字節(jié)）。 3) EVENODD碼中， m必須是素數(shù)，否則 EVENODD 碼不是 MDS 碼。因此若 m 不是素數(shù)，可使用如下方法將它構(gòu)成素數(shù)：若存儲任 意數(shù)量的數(shù)據(jù)塊而非必要的素數(shù)，通過增加不帶任何信息的數(shù)據(jù)塊達到 m列的數(shù)據(jù)塊，其中 m 為素數(shù)，那些多余的數(shù)據(jù)塊所有信息位都為 0。 4) 為了譯碼描述方便， EVENODD 碼增加一行信息位，數(shù)據(jù)全為 0。例如： am1,j = 0（ 0 ≤ j ≤ m+1，根據(jù)這個假設(shè)，數(shù)組大小現(xiàn)在是 m (m+2)） 。 1 ( 1 )111 ( 1 )1 , 1 , 2 , 。mk k m iim ik k m iipbq b k?? ? ???? ? ????? ? ? 編碼原理 EVENODD碼的碼字放在一個 (m1)*(m+2)的陣列中， m 是素數(shù)，其中信息放在 (m－ 1) m 的陣列中，最后兩列為奇偶校驗信息符。兩列奇偶校驗位是分別通過同一行的信息位或者給定斜率對角線的信息位異或而構(gòu)成的。 EVENODD code 的編碼，設(shè) aij 表示位為第 i行第 j 列上的信息符，則奇偶校驗符按下列規(guī)則進行構(gòu)造： 從幾何上看， S 是由第 m 列開始沿斜率為 1 的信息位的異或構(gòu)成的。第一列的各奇偶校驗位正好是這一行 m 個信息位的異或運算，第二列的各奇偶校驗位是各自沿斜率為 1 的信息位的異或，再和 S 異或共同構(gòu)成的。 例 1 下面以 m＝ 5 為例顯示一個（ 7， 5） EVENODD 的編碼，如表 1 表 1 EVENODD編碼 a1 a2 a3 a4 a5 a1+a2+a3+a4+a5 S+a1+b5+c4+d3 b1 b2 b3 b4 b5 b1+b2+b3+b4+b5 S+a2+b1+c3+d4 c1 c2 c3 c4 c5 c1+c2+c3+c4+c5 S+a3+b2+c1+d5 d1 d2 d3 d4 d5 d1+d2+d3+d4+d5 S+a4+b3+c2+d1 其中 S=a5+b4+c3+d2 （ 1） 從 EVENODD 編碼的結(jié)構(gòu)可以看出， 2 個奇偶校驗列是獨立得到的，當 m 是素數(shù)時，滿足 Singleton bound,是一類 MDS，如 m 不是素數(shù)時，不能保證 EVENODD 具有MDS 的性質(zhì)，例如下面的這種情況（ 6， 4）的情況 ， 表 2，碼字 之間的最小距離是 2，若 1，3 列丟失 ，不能 恢復(fù)原信息符。 表 2 （ 6， 4）數(shù)組 （ 2） 在兩列 冗余校驗中，其中有一列的冗余校驗和參數(shù) S 進行以后，參數(shù) S（ m1,1） ,(m3,2),… (0,m1)可能是奇或偶，也是由于這個原因， 稱這類陣列碼為 EVENODD code。如果參數(shù) S忽略，則不能保證EVENODD code 的 MDS 性質(zhì)。例如下面的（ 7， 5）情況 表 3，碼字之間的最小距離就是 2，若第 2， 6 列出錯，是不能恢復(fù)的 。 表 3 （ 7， 5）數(shù)組 b b b b b b b b b b b b b b b b b b b b b b a b b b a b a b a b 0 0 b b b b 0 0 a b a b 0 0 1, 01, 1 ,011,1,1230 2 , 0 1 ,mi m i ttmi m i t t mtmm t ttaaa a SSai m j m???? ? ? ????????? ? ???? ? ? ? ? ?公 式 （ ）， 公 式 （ ）， 公 式 （ ）并 且 xm=x mod n EVENODD 碼譯碼算法 在這一節(jié)將介紹 EVENODD碼糾雙列刪錯的譯碼方法。這兩譯碼算法沒有有限域的計算操作，只需要簡單異或操作，軟硬件實現(xiàn)簡單。下面簡單介紹一下 EVENODD 的譯碼算法， EVENODD code 譯碼算法（ Two Erasure Decoding Algorithm） 假定數(shù)據(jù)塊 i和 j 損壞， 0≤ ij≤ m+1,有下面四種情況： （ 1） i=m,j=m+1,兩個校驗數(shù)據(jù)塊遭到損壞，要恢復(fù)校驗數(shù)據(jù)塊，這和編碼方式一樣，只需要重新構(gòu)造一次就行。 （ 2） im,j=m,一個冗余校數(shù)據(jù)塊和一個信息盤遭到損壞，為了能夠重新恢復(fù) i 數(shù)據(jù)塊，首先恢復(fù)出參數(shù) S， 假定 1, ,0 ,0mla l m? ? ? ?然后通過下面的公式， i數(shù)據(jù)塊的信息符就可以重建 （ 3） im,j=m+1,這種情況， i 信息符數(shù)據(jù)塊可以根據(jù)平行校驗數(shù)據(jù)塊進行異或，得到恢復(fù) （ 4） im,jm,遭到損壞的是兩個信息符的數(shù)據(jù)塊，不像前面三種情況那么簡單 首先 將 最后兩列校驗數(shù)據(jù)塊的信息符異或， 恢復(fù)參數(shù) S 然后計算 ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )0 1 1 0 1 1, , , , ,mmS S S S S S S S????，其中 然后按照下面的順序恢復(fù) i， j 數(shù)據(jù)塊 的各個信息符 例：假設(shè)擁有下列 初始 數(shù)組，如表 4。我們現(xiàn)在將利用譯碼算法恢復(fù)第 0 和 2個錯誤數(shù)據(jù)塊的數(shù)據(jù)。 表 4 初始數(shù)據(jù) ? 0 ? 1 0 1 1 ? 1 ? 0 0 0 1 ？ 1 ? 0 0 1 1 ？ 1 ? 1 1 0 0 11 , 1 1 ,0( ) 4mmmi m i l llS a a?? ? ? ? ? ? ? ??? ? ? ， 公 式 （ ）1, 1 , 1 ,0( ) 0 2 5mmmk i i m k i l lllia S a a k m?? ? ? ? ? ? ? ???? ? ? ? ? ? ?， ， 公 式 （ ）,0 0 2 6mk i k lllka a k m??? ? ? ? ? ， 公 式 （ ）22, , 100( ) ( ) 7mml m l mllS a a?? ???? ? ? ? ， 公 式 （ ）( 0 ),0,1( 1 ), 1 ,0,8( ) 9mmu u lll i jmu u m u l lll i jSaS S a a???? ? ? ?????? ? ? ?， 公 式 （ ）， 公 式 （ ）( 1 )1,( 0 ), ( ) , , ,( 1 ) ( ) 1 0 0 1( 2 )( 3 ) ( ) 1 , 2mmm m ls j s j i i s i s s jjsmS e t s j i a n d a for l mLe t a a a n d a S aS e t s s j i if s m the n sto p e lse g o to ste pS?? ? ? ?? ? ?? ? ? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ? 第一步要做的就是 找到公共因子 S，即將這個數(shù)組最后兩列相異或。我們可以很容易地得到 S = 1 。這意味著，對角校驗是奇校驗。根據(jù)數(shù)組和公式（ 8）、（ 9），我們可以得到校驗數(shù)組： (0)s = 0 1 0 1 0， (1)s = 0 1 0 1 0 現(xiàn)在我們開始一個遞歸來恢復(fù)丟失的數(shù)據(jù) ,0la 和 ,2la ， 0 ≤ l ≤ 3。我們讓5( ) 1 3 2ms j i? ? ? ? ? ? ? ? ? ? ?，這時計算過程如表 5。 表 5 恢復(fù)數(shù)據(jù)過 程 2,2 4 0a SD?? 2 ,0 2 2 , 2 0a SH a? ? ? 0s? 0 ,2 2 2 ,0 0a SD a? ? ? 0 ,0 0 0 , 2 0a SH a? ? ? 3s? 3 ,2 0 0 ,0 0a SD a? ? ? 3 ,0 3 3 ,2 1a SH a? ? ? 1s? 1,2 3 3 ,0 0a SD a? ? ? 1,0 1 1,2 1a SH a? ? ? 4s? 因為 s = 4 = m1，所以算法停止。通過以上的運行過程我們可以發(fā)覺在整個算法運行當中 m 必須是素數(shù)。如果 m不是素數(shù)，將會出現(xiàn) 遞歸在兩列數(shù)據(jù)未恢復(fù)完全之前停止。我們將在后面的證明中很好地利用 m 是素數(shù)的這個條件。例如：如果 m = 4（不是素數(shù)），接下來的數(shù)組如表 6，它的權(quán)值為 2（ the following array is in the code and it has weight 2）： 表 6 m不為素數(shù)時的數(shù)組 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 這表明如果 m 不是素數(shù)，代碼的最小距離為 2 （ the code has minimum distance 2） 譯碼原理證明 下面我們將對 EVENODD 譯碼算法 可以恢復(fù)兩個數(shù)據(jù)塊的數(shù)據(jù)進行證明。 定理一： EVENODD 譯碼算法 可以恢復(fù)任意 2 個數(shù)據(jù)塊出錯的數(shù)據(jù)。 證明：如果只有一列出錯，我們可以利用剩余的正確校驗位數(shù)據(jù)相異或進行恢復(fù)。根據(jù)異或的性質(zhì)我們 可以很容易知道這是完全可行的。因此，假設(shè)第 i 和 j 列出錯，01i j m? ? ? ?。 我們假設(shè) 譯碼算法 的四種情 況： （ 1） i = m ， j = m+1，這種情形和編碼過程完全一樣，很顯然此算法可行； （ 2） i〈 m ， j = m，注意公共因子 S的校驗值是由公式（ 4）得到的，它 由對角線位 (i1m,0)， (i2m,1)，??， (i,m1)上的數(shù)值相異或 得到 。這是一條唯一不與第 i 列相交的對角線（此時第 i 列無效）。因此所有的對角線都有相同的公共因子 S。經(jīng)過分析公式 （ 2）得到,kia的過程，我們可以推出能夠找到恢復(fù)第 i列數(shù)值的公式（ 5），一旦第 i列的值被恢復(fù)，這個算法就可以利用公式（ 1）得到第 m 列的值。 （ 3） i m ， j = m+1，這種情形和編碼的過程相似，在這里不再贅述。 （ 4） i j m ，第一步通過公式（ 7）計算出共同因子 S，也就是公式（ 2）和公式（ 7）是等價的，但是公式（ 2）中存在未知的變量 i， j 的值，因此不能使用公式（ 2）直接得到共同因子 S，因此根據(jù)公式（ 1）和（ 3）可以得到下面的 式子（也就是 公式（ 7））： 因為 m－ 1 為偶數(shù)，所以（ m 1） S≡ 0 mod 2，又因為最后一個虛擬的 m1行所有的值都為 0，即 1,mta? ＝ 0，因此可以得到： 21,=0 0( ( ))mmltlta?????所有水平校驗列的值異或，也就是所有的 0 到 m1 列的數(shù)據(jù)（每列是 m1 行），所有數(shù)據(jù)位異或。 21 ,00( ( ))mmm l t tlta?????????所有的垂直校驗列的值異或（除掉共同因子 S），從 0 到 m1（每列m 行，但最后一行的值為 0） ,因此也就是所有的 0 到 m－ 1 列所有數(shù)據(jù)位異或 。 因此： 所以我們可以獲得： 公式 （ 11） 證明了公式 （ 3） 、 （ 7） 都能給出公共因子 S 的值。 下面我們必須證明這個算法只能唯一恢復(fù)第 i列和第 j 列的數(shù)據(jù)。假設(shè)水平校驗組 (0)s和對角校驗組 (1)s 已經(jīng)分別由公式 （ 8） 、 （ 9） 獲得。 第一步給 s 賦初值 s = (j i)1m 得到 s。 第二步計算： 該公式是正確的，通過公式 （ 2） 和公式 （ 9） 可以得出。一旦我們首先計算出1,mi j ja ??，我們可以通過公式 （ 13） 計算出 公式（ 13）的正確性，根據(jù)公式（ 1）和公式（ 8）可以得到。 第三步，參數(shù) s 的值設(shè)置為 2( ) 1 mji? ? ? ? ? ，返回到第 2 步，根據(jù)算法可以得到： 2 2 2 1 2 1, 1 , ,0 0 0 0 0 0