【正文】 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è)計與目標 設(shè)計目標及內(nèi)容 對于本軟件的設(shè)計可以概述為以下三個方面： （ 1）編碼算法的設(shè)計是本軟件要實現(xiàn)的核心內(nèi)容，通過 EVENODD 編碼原理利用 5張原始圖片的數(shù)據(jù)生成 2 張冗余的校驗數(shù)據(jù)。 （ 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ù)位異或。 證明：如果只有一列出錯，我們可以利用剩余的正確校驗位數(shù)據(jù)相異或進行恢復。根據(jù)數(shù)組和公式（ 8）、（ 9），我們可以得到校驗數(shù)組： (0)s = 0 1 0 1 0， (1)s = 0 1 0 1 0 現(xiàn)在我們開始一個遞歸來恢復丟失的數(shù)據(jù) ,0la 和 ,2la ， 0 ≤ l ≤ 3。 表 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碼糾雙列刪錯的譯碼方法。mk k m iim ik k m iipbq b k?? ? ???? ? ????? ? ? 編碼原理 EVENODD碼的碼字放在一個 (m1)*(m+2)的陣列中， m 是素數(shù)，其中信息放在 (m－ 1) m 的陣列中，最后兩列為奇偶校驗信息符。 2) 設(shè) m 列數(shù)據(jù)塊中每一個數(shù)據(jù)塊只有 m1 行。 在 1994 年，在 RAID6層，也稱為（ P+Q redundancy）：數(shù)據(jù)以塊為單位分割，然后采用編碼技術(shù)為糾雙錯 RS. 設(shè)每列信息位分別為 1 2 1 2 2( , , , ) , ( , , ) ,m m m mb b b b b b??，其兩列校驗信息位 ( , )pq ， 兩個校驗列的編碼方程為： 本課題要達到的設(shè)計目標 本論文采用 EVENODD碼實現(xiàn)存儲系統(tǒng)的容錯仿真。 單個的奇偶校驗能夠容忍單個碼字出錯，二維校驗可以容忍任意的兩個碼字出錯，而且如果增加一個 full parity sever，可以容忍達到三個碼字出錯。其核心運算就是依據(jù)一定的規(guī)則將數(shù)據(jù)簡單相異或。 容錯技術(shù)是保證系統(tǒng)穩(wěn)定性的重要手段。通過對其編碼和譯碼核心算法的調(diào)用，可以實現(xiàn)圖片、二進制文件等格式的備份和恢復。 畢業(yè)設(shè)計 ( 論文 ) 基于 糾錯碼的 容錯技術(shù)的研究 —— EVENODD 碼的設(shè)計與實現(xiàn) 論 文 作者 姓 名 ： 申 請 學位 專 業(yè) ： 申 請 學位 類 別 ： 指導教師姓名（職稱）： 論 文 提交 日 期 ： 基于糾錯碼的容錯技術(shù)的研究 —— EVENODD碼的設(shè)計與實現(xiàn) 摘 要 由于網(wǎng)絡技術(shù)的迅猛發(fā)展，存儲系統(tǒng)的規(guī)模變得越來越龐大。 關(guān)鍵詞： EVENODD編碼 ；容錯技術(shù) ；系統(tǒng)穩(wěn)定性； java編譯技術(shù) Research of Fault Tolerance Technology based on Error Correcting Code —— The Design and Implementation of EVENODD Codes Abstract With the fast development of work technique, the scale of storage system bees bigger and bigger. So, it is an austere challenge to the system. But the data placement strategy of EVENODD which has the ability to simultaneously correct two error data blocks can ensure the stability of the system. It has been extensively used in the RAID( Redundant Arrays of Independent Disks) technology. In the thesis encoding and decoding algorithms of EVENODD codes are introduced. Moreover decoding algorithms are analyzed and proven. At the same time, the software of EVENODD emulator is developed by java technology .The idea of design, the process of development and the design of main function blocks are proposed. It is an apotheosis which uses theory in the real world. Pictures and binary files can be backed up and recovered by EVENODD codes. Key words: EVENODD。容錯是指一個系統(tǒng)在發(fā)生故障時仍能正確完成指定任務的能力。因此對 EVENODD 編碼的研究及其實現(xiàn)具有很強的現(xiàn)實意義。二維編碼策略是通過增加冗余 ，增加服務器的容錯能力。利用隨意的 5張圖片模擬存儲系統(tǒng)中存儲 的 數(shù)據(jù)，然后利用 EVENODD 編碼技術(shù)，生成 2 個校驗數(shù)據(jù)存于另外存儲設(shè)備中（即兩張校驗圖片）。對于任意容量的數(shù)據(jù)塊，可以預先分割成 m1 行的塊分別進行處理。兩列奇偶校驗位是分別通過同一行的信息位或者給定斜率對角線的信息位異或而構(gòu)成的。這兩譯碼算法沒有有限域的計算操作，只需要簡單異或操作，軟硬件實現(xiàn)簡單。我們讓5( ) 1 3 2ms j i? ? ? ? ? ? ? ? ? ? ?，這時計算過程如表 5。根據(jù)異或的性質(zhì)我們 可以很容易知道這是完全可行的。 21 ,00( ( ))mmm l t tlta?????????所有的垂直校驗列的值異或（除掉共同因子 S），從 0 到 m1（每列m 行，但最后一行的值為 0） ,因此也就是所有的 0 到 m－ 1 列所有數(shù)據(jù)位異或 。 （ 2） 譯碼 算法是體現(xiàn)運用 EVENODD 原理能夠勝任將出錯的兩個數(shù)據(jù)塊的數(shù)據(jù) 恢復的關(guān)鍵，也是體現(xiàn)了本原理在現(xiàn)實運用中具有的高可靠性和高穩(wěn)定性。它是配合軟件的仿真而單獨設(shè)計的。 VENODD 編碼算法 1. 算法描述 EVENODD 編碼算法是產(chǎn)生冗余校驗數(shù)據(jù)的核心算法。 tempMatrix1= new int[tempMemory[0].getColumn()][tempMemory[0].getRow()]。//獲取水平校驗（公式 1） tempMatrix2[i] = (dataCache, (dataCache))。它是在尚未破壞的數(shù)據(jù)塊的數(shù)據(jù)的基礎(chǔ)上運用譯碼原理進行操作的。將恢復的值傳入相應的數(shù)組 i ++ u ++k = ( k ( error 2 error 1 ) + m ) % m 。//充當數(shù)組轉(zhuǎn)置時的臨時變量 if(error1 == 2 amp。//獲得對象元素中的數(shù)據(jù)中的每一列 ,組成一個數(shù)組 tempMatrix1[i] = (dataCache)。 error1 2) amp。 i tempMemory[0].getColumn()。 k m 1 。 dataCache = new int[tempMemory[0].getRow()][m]。amp。 i++ ){//獲取前 m+1 行的正確數(shù)據(jù) if(i != error1){corectObj[j++] = (pictureInComp)tempMemory[i].clone()。 for(int i = 0 。 error1 2)amp。 tempMatrix2 = new int[tempMemory[0].getRow()][tempMemory[0].getColumn()]。 for(int j = 0 。 l++)//求 sh if(l != error1 amp。 l != error2){ sd[u] = sd[u] ^ dataCache[(u l + m)%m][l]。 tempMatrix2[j][i] = dataCache[j][error2]。 int[][] dataCache = new int[tempMemory[0].getRow()][m]。 i++){ if(i != error1){ corectObj[j++]=(pictureInComp)tempMemory[i].clone()。 for(int i = 0 。 } }else{//錯誤 數(shù)據(jù)塊 不能找到 ( error : fail to find the error disk !!)。從而使每個待處理圖像組成一個對象數(shù)組。并且 在獲取圖片像素時，針對出錯圖片的處理方法是直接將出錯圖片的數(shù)據(jù)重新 賦為全部值是 0 的最大數(shù)組。 圖 7 軟件操作主 界 面