【正文】 言 選題背景及意義 隨著企業(yè)信息系統(tǒng)的普及和整個(gè)社會(huì)電子商務(wù)的發(fā)展，現(xiàn)代企業(yè)的運(yùn)作越來越依賴于信息技術(shù)。同時(shí)企業(yè)對(duì)于數(shù)據(jù)可用性的要求也大為提高，因?yàn)榧词故嵌虝r(shí)間的系統(tǒng)停機(jī)也將造成業(yè)務(wù)停頓和經(jīng)濟(jì)損失。 容錯(cuò)技術(shù)是保證系統(tǒng)穩(wěn)定性的重要手段。在硬件失效或軟件錯(cuò)誤的情況下，仍能夠繼續(xù)完成指定任務(wù)的系統(tǒng)稱為容錯(cuò)系統(tǒng)。所有的容錯(cuò)手段都必須依賴于“保護(hù)性冗余”，即依賴于系統(tǒng)中冗余的部件和算法。然而， EVENODD 碼理論的提出為容錯(cuò)技術(shù)的發(fā)展做出了重要的貢獻(xiàn)。其核心運(yùn)算就是依據(jù)一定的規(guī)則將數(shù)據(jù)簡單相異或。 相近課題研究 容錯(cuò)技術(shù)在存儲(chǔ)系統(tǒng)中有著廣泛的應(yīng)用 。 2D 奇偶校驗(yàn)編碼方案 2D 奇偶編碼的碼字結(jié)構(gòu)為 n n 的二維陣列，總共有 N2 個(gè)信息位，其中校驗(yàn)信息位為2N 個(gè)，即水平校驗(yàn)和垂直校驗(yàn)，對(duì)矩陣的行和列分別進(jìn)行校驗(yàn)計(jì)算。每個(gè)碼字不是一個(gè)組的成員，而是多個(gè)組的成員，進(jìn)行容錯(cuò)計(jì)算。 單個(gè)的奇偶校驗(yàn)?zāi)軌蛉萑虇蝹€(gè)碼字出錯(cuò)，二維校驗(yàn)可以容忍任意的兩個(gè)碼字出錯(cuò)，而且如果增加一個(gè) full parity sever，可以容忍達(dá)到三個(gè)碼字出錯(cuò)。 冗余數(shù)據(jù)的增加，必定會(huì)導(dǎo)致編 碼和譯碼計(jì)算量的增加，及 數(shù)據(jù)信息位和校驗(yàn)信息位之間的比之變化。它首先是由里德（ Reed）和索洛蒙（ Solomon）應(yīng)用 MS 多相式于 1960 年構(gòu)造出來的。 Reed Solomon code 適合傳送信息符號(hào)，而不是比特。 在 1994 年，在 RAID6層，也稱為（ P+Q redundancy）：數(shù)據(jù)以塊為單位分割，然后采用編碼技術(shù)為糾雙錯(cuò) RS. 設(shè)每列信息位分別為 1 2 1 2 2( , , , ) , ( , , ) ,m m m mb b b b b b??，其兩列校驗(yàn)信息位 ( , )pq ， 兩個(gè)校驗(yàn)列的編碼方程為： 本課題要達(dá)到的設(shè)計(jì)目標(biāo) 本論文采用 EVENODD碼實(shí)現(xiàn)存儲(chǔ)系統(tǒng)的容錯(cuò)仿真。隨機(jī)破壞其中的一張或者兩張數(shù)據(jù)，利用 EVENODD 的譯碼算法將這2 張圖片的數(shù)據(jù)恢復(fù)出來。 2 EVENODD 碼 預(yù)先定義 為了方便本文后面的敘述，先定義本文一些符號(hào)記法： nm = j 表示 j ≡ n(mod m) （ 0 ≤ j ≤ m+1） 。 另外我 們還對(duì)本原理做一些必要的假設(shè)： 1) 設(shè)存在 m+2 列數(shù)據(jù)塊，其中前 m個(gè)數(shù)據(jù)塊依次存有信息，校驗(yàn)信息將存儲(chǔ)在最后兩列數(shù)據(jù)塊。 2) 設(shè) m 列數(shù)據(jù)塊中每一個(gè)數(shù)據(jù)塊只有 m1 行。為簡單起見，在本文中假設(shè)每一個(gè)標(biāo)識(shí)位大小為1bit（不過在一些應(yīng)用程序當(dāng)中，一個(gè)標(biāo)識(shí)位可能大到 512 字節(jié)）。因此若 m 不是素?cái)?shù)，可使用如下方法將它構(gòu)成素?cái)?shù)：若存儲(chǔ)任 意數(shù)量的數(shù)據(jù)塊而非必要的素?cái)?shù)，通過增加不帶任何信息的數(shù)據(jù)塊達(dá)到 m列的數(shù)據(jù)塊，其中 m 為素?cái)?shù)，那些多余的數(shù)據(jù)塊所有信息位都為 0。例如： am1,j = 0（ 0 ≤ j ≤ m+1，根據(jù)這個(gè)假設(shè)，數(shù)組大小現(xiàn)在是 m (m+2)） 。mk k m iim ik k m iipbq b k?? ? ???? ? ????? ? ? 編碼原理 EVENODD碼的碼字放在一個(gè) (m1)*(m+2)的陣列中， m 是素?cái)?shù)，其中信息放在 (m－ 1) m 的陣列中，最后兩列為奇偶校驗(yàn)信息符。 EVENODD code 的編碼，設(shè) aij 表示位為第 i行第 j 列上的信息符，則奇偶校驗(yàn)符按下列規(guī)則進(jìn)行構(gòu)造： 從幾何上看， S 是由第 m 列開始沿斜率為 1 的信息位的異或構(gòu)成的。 例 1 下面以 m＝ 5 為例顯示一個(gè)（ 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 個(gè)奇偶校驗(yàn)列是獨(dú)立得到的，當(dāng) m 是素?cái)?shù)時(shí)，滿足 Singleton bound,是一類 MDS，如 m 不是素?cái)?shù)時(shí)，不能保證 EVENODD 具有MDS 的性質(zhì)，例如下面的這種情況（ 6， 4）的情況 ， 表 2，碼字 之間的最小距離是 2，若 1，3 列丟失 ，不能 恢復(fù)原信息符。如果參數(shù) S忽略，則不能保證EVENODD code 的 MDS 性質(zhì)。 表 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碼糾雙列刪錯(cuò)的譯碼方法。下面簡單介紹一下 EVENODD 的譯碼算法， EVENODD code 譯碼算法（ Two Erasure Decoding Algorithm） 假定數(shù)據(jù)塊 i和 j 損壞， 0≤ ij≤ m+1,有下面四種情況： （ 1） i=m,j=m+1,兩個(gè)校驗(yàn)數(shù)據(jù)塊遭到損壞，要恢復(fù)校驗(yàn)數(shù)據(jù)塊，這和編碼方式一樣，只需要重新構(gòu)造一次就行。我們現(xiàn)在將利用譯碼算法恢復(fù)第 0 和 2個(gè)錯(cuò)誤數(shù)據(jù)塊的數(shù)據(jù)。我們可以很容易地得到 S = 1 。根據(jù)數(shù)組和公式（ 8）、（ 9），我們可以得到校驗(yàn)數(shù)組： (0)s = 0 1 0 1 0， (1)s = 0 1 0 1 0 現(xiàn)在我們開始一個(gè)遞歸來恢復(fù)丟失的數(shù)據(jù) ,0la 和 ,2la ， 0 ≤ l ≤ 3。 表 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? 因?yàn)?s = 4 = m1，所以算法停止。如果 m不是素?cái)?shù)，將會(huì)出現(xiàn) 遞歸在兩列數(shù)據(jù)未恢復(fù)完全之前停止。例如：如果 m = 4（不是素?cái)?shù)），接下來的數(shù)組如表 6，它的權(quán)值為 2（ the following array is in the code and it has weight 2）： 表 6 m不為素?cái)?shù)時(shí)的數(shù)組 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 這表明如果 m 不是素?cái)?shù)，代碼的最小距離為 2 （ the code has minimum distance 2） 譯碼原理證明 下面我們將對(duì) EVENODD 譯碼算法 可以恢復(fù)兩個(gè)數(shù)據(jù)塊的數(shù)據(jù)進(jìn)行證明。 證明：如果只有一列出錯(cuò)，我們可以利用剩余的正確校驗(yàn)位數(shù)據(jù)相異或進(jìn)行恢復(fù)。因此，假設(shè)第 i 和 j 列出錯(cuò)，01i j m? ? ? ?。這是一條唯一不與第 i 列相交的對(duì)角線（此時(shí)第 i 列無效）。經(jīng)過分析公式 （ 2）得到,kia的過程，我們可以推出能夠找到恢復(fù)第 i列數(shù)值的公式（ 5），一旦第 i列的值被恢復(fù)，這個(gè)算法就可以利用公式（ 1）得到第 m 列的值。 （ 4） i j m ，第一步通過公式（ 7）計(jì)算出共同因子 S，也就是公式（ 2）和公式（ 7）是等價(jià)的，但是公式（ 2）中存在未知的變量 i， j 的值，因此不能使用公式（ 2）直接得到共同因子 S，因此根據(jù)公式（ 1）和（ 3）可以得到下面的 式子（也就是 公式（ 7））： 因?yàn)?m－ 1 為偶數(shù)，所以（ m 1） S≡ 0 mod 2，又因?yàn)樽詈笠粋€(gè)虛擬的 m1行所有的值都為 0，即 1,mta? ＝ 0，因此可以得到： 21,=0 0( ( ))mmltlta?????所有水平校驗(yàn)列的值異或，也就是所有的 0 到 m1 列的數(shù)據(jù)（每列是 m1 行），所有數(shù)據(jù)位異或。 因此： 所以我們可以獲得： 公式 （ 11） 證明了公式 （ 3） 、 （ 7） 都能給出公共因子 S 的值。假設(shè)水平校驗(yàn)組 (0)s和對(duì)角校驗(yàn)組 (1)s 已經(jīng)分別由公式 （ 8） 、 （ 9） 獲得。 第二步計(jì)算： 該公式是正確的，通過公式 （ 2） 和公式 （ 9） 可以得出。 第三步，參數(shù) s 的值設(shè)置為 2( ) 1 mji? ? ? ? ? ，返回到第 2 步，根據(jù)算法可以得到： 2 2 2 1 2 1, 1 , ,0 0 0 0 0 02 1 2 1,0 0 0 02 1 2 1,0 0 0 0( ) ( ) ( ( ) ) ( ( ) )( ( ) ) ( 1 ) ( ( ) )( ( ) ) ( ( ) ) , 10mmmm m m m m ml m l t l t tl l l t l tm m m ml t l t tl t l tm m m ml t l t tl t l ta a S aa m S S aaa? ? ? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ????? ? ? ?? ? ? ????? ? ? ?? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?? ? ? ? ? ? 公 式 （ ）2 1 1 1,0 0 0 02 1 2 1 1, , 1 ,0 0 0 0 10 ( ( ) ) ( ( ) )( ( ) ) ( ( ) ) ( )mmm m m ml t l t tl t l tm m m m ml t l t t m t tl t l t taaa a a? ? ? ????? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?2 1 2 1 1, , 1 ,0 0 0 0 1( ( ) ) ( ( ) ) 1 1mm m m m ml t l t t m t tl t l t ta a a? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ? ? ? ， 公 式 （ ）, ( 1 )( ) 1 1 , (1 2 )m j mj i iaS? ? ? ? ? ? ? ?? 公 式,( ) 1 ( ) 1 ( ) , , 13m i m mj i j i j j i ja S a? ? ? ? ? ? ? ? ? ? ? ? ? ? ???(0) 公 式 （ ）,12 ( ) 1 2 ( ) 1 ( ) ,2 ( ) 1 2 ( ) 1 2 ( ) 1m j m mm j m m jj i j i j j i ij i j i j ia S aa S a? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ???（ ）(0)， 公 式 （ 14 ）， 公 式 （ 15 ） 3 軟件設(shè)計(jì)與目標(biāo) 設(shè)計(jì)目標(biāo)及內(nèi)容 對(duì)于本軟件的設(shè)計(jì)可以概述為以下三個(gè)方面： （ 1）編碼算法的設(shè)計(jì)是本軟件要實(shí)現(xiàn)的核心內(nèi)容，通過 EVENODD 編碼原理利用 5張?jiān)紙D片的數(shù)據(jù)生成 2 張冗余的校驗(yàn)數(shù)據(jù)。 （ 3）界面設(shè)計(jì)是實(shí)現(xiàn)友好的人機(jī)交互界面不可或缺的重要部分， EVENODD編碼的實(shí)現(xiàn)過程和結(jié)果都要通過該界面表現(xiàn)和保存。在正式進(jìn)行編碼之前必須對(duì)圖像進(jìn)行一些必要的處理以符合算法的接口標(biāo)準(zhǔn)。 ? 圖像載入：從本地計(jì)算機(jī)中讀取圖片文件，可以選擇本地計(jì)算機(jī)中的任何文件夾。 ? 圖像破壞：將圖片的數(shù)據(jù)全部破壞供 譯碼 使用。 ? 圖像分割：從以圖像格式顯示的圖片中讀取像素并存儲(chǔ)在二維數(shù)組中，供以后處理使用 。 2. 編碼 編碼功能是整個(gè)軟件進(jìn)行的關(guān)鍵，通過原始圖片生成 2 張冗余校驗(yàn)圖片，為 譯碼 過程的順利進(jìn)行做準(zhǔn)備。 設(shè)計(jì)實(shí)現(xiàn)的策略及主要算法描述 在該軟件的實(shí)現(xiàn)過程中，基于面向?qū)ο蟪绦蛟O(shè)計(jì)思想，在 實(shí)現(xiàn)過程中，把每一個(gè)待處理的數(shù)據(jù)看作一個(gè) 對(duì)象，那么每個(gè)對(duì)象在實(shí)際的應(yīng)用中也就是一張圖片（也可以叫做一個(gè)數(shù)據(jù)塊）。由于以上介紹的編碼過程都是針對(duì)單個(gè)數(shù)組的，所以在算法處理過程中，必須從每個(gè)對(duì)象中抽取一列組成單個(gè)的數(shù)據(jù)，將每個(gè) 4 5 大小的數(shù)組看作一個(gè)基本處理單元，然后按照編碼原理進(jìn)行算法的設(shè)計(jì)。在實(shí)現(xiàn)該算法過程中，假設(shè)接口為 5 個(gè)數(shù)據(jù)對(duì)象，由于在該算法中實(shí)際操作對(duì)象是一個(gè) 4 5 大小的數(shù)組，首