【正文】 i m ， j = m+1，這種情形和編碼的過程相似，在這里不再贅述。 我們假設(shè) 譯碼算法 的四種情 況： （ 1） i = m ， j = m+1，這種情形和編碼過程完全一樣，很顯然此算法可行； （ 2） i〈 m ， j = m，注意公共因子 S的校驗值是由公式（ 4）得到的，它 由對角線位 (i1m,0)， (i2m,1)，??， (i,m1)上的數(shù)值相異或 得到 。 定理一： EVENODD 譯碼算法 可以恢復任意 2 個數(shù)據(jù)塊出錯的數(shù)據(jù)。通過以上的運行過程我們可以發(fā)覺在整個算法運行當中 m 必須是素數(shù)。這意味著，對角校驗是奇校驗。 （ 2） im,j=m,一個冗余校數(shù)據(jù)塊和一個信息盤遭到損壞，為了能夠重新恢復 i 數(shù)據(jù)塊，首先恢復出參數(shù) S， 假定 1, ,0 ,0mla l m? ? ? ?然后通過下面的公式， i數(shù)據(jù)塊的信息符就可以重建 （ 3） im,j=m+1,這種情況， i 信息符數(shù)據(jù)塊可以根據(jù)平行校驗數(shù)據(jù)塊進行異或，得到恢復 （ 4） im,jm,遭到損壞的是兩個信息符的數(shù)據(jù)塊，不像前面三種情況那么簡單 首先 將 最后兩列校驗數(shù)據(jù)塊的信息符異或， 恢復參數(shù) S 然后計算 ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )0 1 1 0 1 1, , , , ,mmS S S S S S S S????，其中 然后按照下面的順序恢復 i， j 數(shù)據(jù)塊 的各個信息符 例：假設(shè)擁有下列 初始 數(shù)組，如表 4。例如下面的（ 7， 5）情況 表 3，碼字之間的最小距離就是 2，若第 2， 6 列出錯，是不能恢復的 。第一列的各奇偶校驗位正好是這一行 m 個信息位的異或運算，第二列的各奇偶校驗位是各自沿斜率為 1 的信息位的異或，再和 S 異或共同構(gòu)成的。 1 ( 1 )111 ( 1 )1 , 1 , 2 , 。 3) EVENODD碼中， m必須是素數(shù)，否則 EVENODD 碼不是 MDS 碼。這樣將在所有的數(shù)據(jù)塊中形成冗余以避免在重復寫操作時形成瓶頸。整個仿真過程將在一個界面友好的應(yīng)用軟件中實現(xiàn)。 RS 雖然在六十年代就提出來了，但是實際得到應(yīng)用差不多在八十年代。 row parity full parity parity column parity 圖 1 二維奇偶校驗編碼 糾雙錯 RS 碼 Reed Solomon(RS)是一類有很強糾錯能力的多進制 BCH 碼，也是一類典型的幾何碼。圖 1 顯示 的是一個二維編碼的策略和二維奇偶校驗碼。 目前，已有的適用于存儲系統(tǒng)的容錯技術(shù)主要有三種： 2D奇偶校驗編碼方案（二維奇偶校驗）， RS（ ReedSolomon）碼以及 EVENODD碼。它以一種簡單的方式越來越受到人們的青睞，并在各種系統(tǒng)中廣泛使用，尤其是磁盤陣列布局方案中。容錯技術(shù)是指系統(tǒng)對故障的容忍技術(shù)，也就是指處于工作狀態(tài)的系統(tǒng)中一個或多個關(guān)鍵部分發(fā)生故障或差錯時，能自動檢測與診斷，并能采取相應(yīng)措施 保證系統(tǒng)維持其規(guī)定功能或保持其功能在可接受的范圍內(nèi)的技術(shù)。一旦 IT 系統(tǒng)和數(shù)據(jù)遭到災(zāi)難性打擊，企業(yè)將面臨破產(chǎn)的威脅，因此數(shù)據(jù)資料的完好保存是企業(yè)在災(zāi)難后能夠繼續(xù)生存的保證。 Stability of system。 EVENODD碼仿真軟件的實現(xiàn)是理論運用于實際的又一典范。而采用 EVENODD 編碼算法的布局策略可以同時容許兩個數(shù)據(jù)塊同時出錯，可以很好的保證系統(tǒng)的穩(wěn)定性。因此它對 系統(tǒng)的可靠性提出了嚴峻的挑戰(zhàn)。在本論文中還對該仿真軟件的設(shè)計思路、開發(fā)過程、以及主要功能模塊的實現(xiàn)都進行了詳細的介紹。 Faulttolerant。同時企業(yè)對于數(shù)據(jù)可用性的要求也大為提高，因為即使是短時間的系統(tǒng)停機也將造成業(yè)務(wù)停頓和經(jīng)濟損失。在硬件失效或軟件錯誤的情況下，仍能夠繼續(xù)完成指定任務(wù)的系統(tǒng)稱為容錯系統(tǒng)。然而， EVENODD 碼理論的提出為容錯技術(shù)的發(fā)展做出了重要的貢獻。 相近課題研究 容錯技術(shù)在存儲系統(tǒng)中有著廣泛的應(yīng)用 。每個碼字不是一個組的成員，而是多個組的成員，進行容錯計算。 冗余數(shù)據(jù)的增加，必定會導致編 碼和譯碼計算量的增加，及 數(shù)據(jù)信息位和校驗信息位之間的比之變化。 Reed Solomon code 適合傳送信息符號，而不是比特。隨機破壞其中的一張或者兩張數(shù)據(jù)，利用 EVENODD 的譯碼算法將這2 張圖片的數(shù)據(jù)恢復出來。 另外我 們還對本原理做一些必要的假設(shè)： 1) 設(shè)存在 m+2 列數(shù)據(jù)塊，其中前 m個數(shù)據(jù)塊依次存有信息，校驗信息將存儲在最后兩列數(shù)據(jù)塊。為簡單起見，在本文中假設(shè)每一個標識位大小為1bit（不過在一些應(yīng)用程序當中，一個標識位可能大到 512 字節(jié)）。例如： am1,j = 0（ 0 ≤ j ≤ m+1，根據(jù)這個假設(shè)，數(shù)組大小現(xiàn)在是 m (m+2)） 。 EVENODD code 的編碼，設(shè) aij 表示位為第 i行第 j 列上的信息符，則奇偶校驗符按下列規(guī)則進行構(gòu)造： 從幾何上看， S 是由第 m 列開始沿斜率為 1 的信息位的異或構(gòu)成的。如果參數(shù) S忽略，則不能保證EVENODD code 的 MDS 性質(zhì)。下面簡單介紹一下 EVENODD 的譯碼算法， EVENODD code 譯碼算法（ Two Erasure Decoding Algorithm） 假定數(shù)據(jù)塊 i和 j 損壞， 0≤ ij≤ m+1,有下面四種情況： （ 1） i=m,j=m+1,兩個校驗數(shù)據(jù)塊遭到損壞，要恢復校驗數(shù)據(jù)塊，這和編碼方式一樣，只需要重新構(gòu)造一次就行。我們可以很容易地得到 S = 1 。 表 5 恢復數(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，所以算法停止。例如：如果 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 譯碼算法 可以恢復兩個數(shù)據(jù)塊的數(shù)據(jù)進行證明。因此，假設(shè)第 i 和 j 列出錯，01i j m? ? ? ?。經(jīng)過分析公式 （ 2）得到,kia的過程，我們可以推出能夠找到恢復第 i列數(shù)值的公式（ 5），一旦第 i列的值被恢復，這個算法就可以利用公式（ 1）得到第 m 列的值。 因此： 所以我們可以獲得： 公式 （ 11） 證明了公式 （ 3） 、 （ 7） 都能給出公共因子 S 的值。 第二步計算： 該公式是正確的，通過公式 （ 2） 和公式 （ 9） 可以得出。 （ 3）界面設(shè)計是實現(xiàn)友好的人機交互界面不可或缺的重要部分， EVENODD編碼的實現(xiàn)過程和結(jié)果都要通過該界面表現(xiàn)和保存。 ? 圖像載入：從本地計算機中讀取圖片文件，可以選擇本地計算機中的任何文件夾。 ? 圖像分割：從以圖像格式顯示的圖片中讀取像素并存儲在二維數(shù)組中，供以后處理使用 。 設(shè)計實現(xiàn)的策略及主要算法描述 在該軟件的實現(xiàn)過程中，基于面向?qū)ο蟪绦蛟O(shè)計思想，在 實現(xiàn)過程中，把每一個待處理的數(shù)據(jù)看作一個 對象，那么每個對象在實際的應(yīng)用中也就是一張圖片（也可以叫做一個數(shù)據(jù)塊）。在實現(xiàn)該算法過程中，假設(shè)接口為 5 個數(shù)據(jù)對象，由于在該算法中實際操作對象是一個 4 5 大小的數(shù)組，首先面對的問題是如何將對象中的數(shù)據(jù)讀出來并且將他們組合成符合規(guī)格的數(shù)組。根據(jù)公式（ 1）可以得到該處理單元產(chǎn)生的水平校驗位的值，根據(jù)公式（ 3）不難得出公共校驗因子 S ，再由公式（ 2）對角校驗值也就很容易的得到了。 //暫存運算過程中水平校驗位的數(shù)據(jù)值的轉(zhuǎn)置數(shù)據(jù) tempMatrix2= new int[tempMemory[0].getColumn()][tempMemory[0].getRow()]。 i 。 // 獲取對角校驗數(shù)據(jù)（公式 2） } //將修復的數(shù)據(jù)存入對象 (tempMatrix1, temp)。//對角冗余校驗對象實例化 } EVENODD 譯碼算法 1. 算法描述 EVENODD 譯碼算法是 EVENODD 碼中的關(guān)鍵，是使該碼能從理論運用到現(xiàn)實的基礎(chǔ)。由于每個數(shù)據(jù)塊被破壞的幾率是均等的，不同的數(shù)據(jù)塊被破壞，處理的方法也相應(yīng)有所不同。最后將每一個最小數(shù)據(jù)單元恢復的結(jié)果存儲到錯誤數(shù)據(jù)塊相應(yīng)的位置。將修復的數(shù)據(jù)傳入對應(yīng)的對象結(jié)束否是是否是否 圖 4(g) EVENODD譯碼流程圖 3. 算法實現(xiàn) 譯碼算法的實現(xiàn)如程序清單 3— 2 程序清單 32 EVENODD譯碼算法 protected void decode(){ if(error1 != 1 amp。//暫存正確 數(shù)據(jù)塊 的數(shù)據(jù) tempMatrix1 = new int[tempMemory[0].getColumn()][tempMemory[0].getRow()]。amp。 for(int i = 0 。//修復 數(shù)據(jù)塊 error1； tempMatrix2[i] = (dataCache, (dataCache))。 tempMemory[error2].read(temp)。amp。 int[][] tempCache = new int[tempMemory[0].getRow()][]。 i++){ tempCache = (tempMemory, i)。 l m 。 k++){ tempMatrix1[k][i] = s ^ dataCache[(k + error1 + m)%m][m + 1] 。 } } } } tempMemory[error1].read(tempMatrix1)。 for(int i = 0 。//水平異或 } (tempMatrix2, temp)。 error1 2) amp。 dataCache = new int[tempMemory[0].getRow()][m]。} } for(int i = 0 。 } (tempMatrix1, temp)。 i m 。 tempMemory[error2].read(temp)。amp。 dataCache = new int[tempMemory[0].getRow() + 1][m + 2]。 for(int i = 0 。 int[] sd = new int[m]。 j 。 u m 。amp。 l m 。 } } } /**修復數(shù)據(jù) */ k = (m (error2 error1) 1) % m。 } for(int j = 0 。 } } tempMemory[error1].read(tempMatrix1)。 } }else if(error2 == 1 amp。 int[][] tempMatrix = new int[tempMemory[0].getColumn()][tempMemory[0].getRow()]。amp。 } } for(int i = 0 。 } (tempMatrix, temp)。 i 。 tempMemory[error1].read(temp)。 (0)。在編碼功能的實現(xiàn)過程中，我們必須把輸入的圖片處理成 為適合該接口的數(shù)據(jù)。由于，每個對象數(shù)組的大小要遠遠大于 encode算法中所要求的 4 5數(shù)組。 在此值得說明的一點是，在圖片處理過程中像素是由 RGB 值構(gòu)成的，我們進行的對像素的編碼實際上是對 RGB值編碼，編碼后得到的冗余校驗數(shù)據(jù)將重新組合成新的像素。 節(jié)介紹了 EVENODD 譯碼算法的設(shè)計，從上面的敘述我們可以知道，譯碼算法的接口有兩種情況即 decode(pictureInComp[],int) 和decode(pictureInComp[],int,int)。 很 明顯 ，該軟件主要分為菜單欄、快捷鍵欄和數(shù)據(jù)顯示域三部分。否 則系統(tǒng)將對彈出對話框?qū)δ愕牟僮鬟M行提示，如圖 8。單擊“ Edit” → 選擇“ Encode”或者單擊 encode按鈕。選擇將要破壞的圖片對應(yīng)的復選框，單擊“ Edit” → 選擇“ Data_Destroy”或者單擊 destro