【正文】 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)容，通過(guò) EVENODD 編碼原理利用 5張?jiān)紙D片的數(shù)據(jù)生成 2 張冗余的校驗(yàn)數(shù)據(jù)。 （ 4） i j m ，第一步通過(guò)公式（ 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ù)位異或。 證明：如果只有一列出錯(cuò)，我們可以利用剩余的正確校驗(yàn)位數(shù)據(jù)相異或進(jìn)行恢復(fù)。根據(jù)數(shù)組和公式（ 8）、（ 9），我們可以得到校驗(yàn)數(shù)組： (0)s = 0 1 0 1 0， (1)s = 0 1 0 1 0 現(xiàn)在我們開(kāi)始一個(gè)遞歸來(lái)恢復(fù)丟失的數(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碼糾雙列刪錯(cuò)的譯碼方法。mk k m iim ik k m iipbq b k?? ? ???? ? ????? ? ? 編碼原理 EVENODD碼的碼字放在一個(gè) (m1)*(m+2)的陣列中， m 是素?cái)?shù)，其中信息放在 (m－ 1) m 的陣列中，最后兩列為奇偶校驗(yàn)信息符。 2) 設(shè) m 列數(shù)據(jù)塊中每一個(gè)數(shù)據(jù)塊只有 m1 行。 在 1994 年，在 RAID6層，也稱(chēng)為（ 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ò)仿真。 單個(gè)的奇偶校驗(yàn)?zāi)軌蛉萑虇蝹€(gè)碼字出錯(cuò)，二維校驗(yàn)可以容忍任意的兩個(gè)碼字出錯(cuò)，而且如果增加一個(gè) full parity sever，可以容忍達(dá)到三個(gè)碼字出錯(cuò)。其核心運(yùn)算就是依據(jù)一定的規(guī)則將數(shù)據(jù)簡(jiǎn)單相異或。 容錯(cuò)技術(shù)是保證系統(tǒng)穩(wěn)定性的重要手段。通過(guò)對(duì)其編碼和譯碼核心算法的調(diào)用，可以實(shí)現(xiàn)圖片、二進(jìn)制文件等格式的備份和恢復(fù)。 畢業(yè)設(shè)計(jì) ( 論文 ) 基于 糾錯(cuò)碼的 容錯(cuò)技術(shù)的研究 —— EVENODD 碼的設(shè)計(jì)與實(shí)現(xiàn) 論 文 作者 姓 名 ： 申 請(qǐng) 學(xué)位 專(zhuān) 業(yè) ： 申 請(qǐng) 學(xué)位 類(lèi) 別 ： 指導(dǎo)教師姓名（職稱(chēng)）： 論 文 提交 日 期 ： 基于糾錯(cuò)碼的容錯(cuò)技術(shù)的研究 —— EVENODD碼的設(shè)計(jì)與實(shí)現(xiàn) 摘 要 由于網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，存儲(chǔ)系統(tǒng)的規(guī)模變得越來(lái)越龐大。 關(guān)鍵詞： EVENODD編碼 ；容錯(cuò)技術(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。容錯(cuò)是指一個(gè)系統(tǒng)在發(fā)生故障時(shí)仍能正確完成指定任務(wù)的能力。因此對(duì) EVENODD 編碼的研究及其實(shí)現(xiàn)具有很強(qiáng)的現(xiàn)實(shí)意義。二維編碼策略是通過(guò)增加冗余 ，增加服務(wù)器的容錯(cuò)能力。利用隨意的 5張圖片模擬存儲(chǔ)系統(tǒng)中存儲(chǔ) 的 數(shù)據(jù)，然后利用 EVENODD 編碼技術(shù)，生成 2 個(gè)校驗(yàn)數(shù)據(jù)存于另外存儲(chǔ)設(shè)備中（即兩張校驗(yàn)圖片）。對(duì)于任意容量的數(shù)據(jù)塊，可以預(yù)先分割成 m1 行的塊分別進(jìn)行處理。兩列奇偶校驗(yàn)位是分別通過(guò)同一行的信息位或者給定斜率對(duì)角線(xiàn)的信息位異或而構(gòu)成的。這兩譯碼算法沒(méi)有有限域的計(jì)算操作，只需要簡(jiǎn)單異或操作，軟硬件實(shí)現(xiàn)簡(jiǎn)單。我們讓5( ) 1 3 2ms j i? ? ? ? ? ? ? ? ? ? ?，這時(shí)計(jì)算過(guò)程如表 5。根據(jù)異或的性質(zhì)我們 可以很容易知道這是完全可行的。 21 ,00( ( ))mmm l t tlta?????????所有的垂直校驗(yàn)列的值異或（除掉共同因子 S），從 0 到 m1（每列m 行，但最后一行的值為 0） ,因此也就是所有的 0 到 m－ 1 列所有數(shù)據(jù)位異或 。 （ 2） 譯碼 算法是體現(xiàn)運(yùn)用 EVENODD 原理能夠勝任將出錯(cuò)的兩個(gè)數(shù)據(jù)塊的數(shù)據(jù) 恢復(fù)的關(guān)鍵，也是體現(xiàn)了本原理在現(xiàn)實(shí)運(yùn)用中具有的高可靠性和高穩(wěn)定性。它是配合軟件的仿真而單獨(dú)設(shè)計(jì)的。 VENODD 編碼算法 1. 算法描述 EVENODD 編碼算法是產(chǎn)生冗余校驗(yàn)數(shù)據(jù)的核心算法。 tempMatrix1= new int[tempMemory[0].getColumn()][tempMemory[0].getRow()]。//獲取水平校驗(yàn)（公式 1） tempMatrix2[i] = (dataCache, (dataCache))。它是在尚未破壞的數(shù)據(jù)塊的數(shù)據(jù)的基礎(chǔ)上運(yùn)用譯碼原理進(jìn)行操作的。將恢復(fù)的值傳入相應(yīng)的數(shù)組 i ++ u ++k = ( k ( error 2 error 1 ) + m ) % m 。//充當(dāng)數(shù)組轉(zhuǎn)置時(shí)的臨時(shí)變量 if(error1 == 2 amp。//獲得對(duì)象元素中的數(shù)據(jù)中的每一列 ,組成一個(gè)數(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{//錯(cuò)誤 數(shù)據(jù)塊 不能找到 ( error : fail to find the error disk !!)。從而使每個(gè)待處理圖像組成一個(gè)對(duì)象數(shù)組。并且 在獲取圖片像素時(shí)，針對(duì)出錯(cuò)圖片的處理方法是直接將出錯(cuò)圖片的數(shù)據(jù)重新 賦為全部值是 0 的最大數(shù)組。 圖 7 軟件操作主 界 面