【正文】 畢業(yè)設(shè)計 ( 論文 ) 基于 糾錯碼的 容錯技術(shù)的研究 —— EVENODD 碼的設(shè)計與實現(xiàn) 論 文 作者 姓 名 ： 申 請 學(xué)位 專 業(yè) ： 申 請 學(xué)位 類 別 ： 指導(dǎo)教師姓名（職稱）： 論 文 提交 日 期 ： 基于糾錯碼的容錯技術(shù)的研究 —— EVENODD碼的設(shè)計與實現(xiàn) 摘 要 由于網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，存儲系統(tǒng)的規(guī)模變得越來越龐大。因此它對 系統(tǒng)的可靠性提出了嚴(yán)峻的挑戰(zhàn)。而采用 EVENODD 編碼算法的布局策略可以同時容許兩個數(shù)據(jù)塊同時出錯，可以很好的保證系統(tǒng)的穩(wěn)定性。它已經(jīng)被廣泛應(yīng)用在 RAID（ Redundant Arrays of Independent Disks）等技術(shù)中。本論文從 EVENODD 編碼原理出發(fā)，詳細(xì)介紹了 EVENODD 的編碼和 譯碼 過程，以及從理論上對該譯碼的算法進(jìn)行了分析證明，同時使用 java編譯技術(shù)實現(xiàn)了該編碼過程的仿真。在本論文中還對該仿真軟件的設(shè)計思路、開發(fā)過程、以及主要功能模塊的實現(xiàn)都進(jìn)行了詳細(xì)的介紹。 EVENODD碼仿真軟件的實現(xiàn)是理論運用于實際的又一典范。通過對其編碼和譯碼核心算法的調(diào)用，可以實現(xiàn)圖片、二進(jìn)制文件等格式的備份和恢復(fù)。 關(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。 Faulttolerant。 Stability of system。 Java technology 目 錄 論文總頁數(shù)： 31 頁 1 引言 .................................................................. 6 選題背景及意義 ...................................................... 6 相近課題研究 ....................................................... 6 2D奇偶校驗編碼方案 ............................................. 6 糾雙錯 RS碼 ..................................................... 7 本課題要達(dá)到的設(shè)計目標(biāo) .............................................. 7 2 EVENODD碼 ............................................................. 7 預(yù)先定義 ........................................................... 7 編碼原理 ........................................................... 8 EVENODD碼譯碼算法 .................................................. 9 譯碼原理證明 ...................................................... 10 3 軟件設(shè)計與目標(biāo) ....................................................... 12 設(shè)計目標(biāo)及內(nèi)容 ..................................................... 12 軟件總體功能結(jié)構(gòu) ................................................... 12 功能結(jié)構(gòu)圖 ..................................................... 12 功能說明 ...................................................... 12 設(shè)計實現(xiàn)的策略及主要算法描述 ....................................... 13 VENODD編碼算法 ................................................ 13 EVENODD 譯碼算法 ............................................... 15 算法接口實現(xiàn) ...................................................... 25 編碼功能接口設(shè)計 ............................................... 26 編碼功能接口流程圖 ............................................. 26 譯碼功能接口設(shè)計 ............................................... 26 譯碼功能接口設(shè)計流程圖 ......................................... 26 4 軟件操作說明 ......................................................... 29 打開 .............................................................. 29 編碼 .............................................................. 30 數(shù)據(jù)破壞 .......................................................... 30 譯碼 .............................................................. 31 其余功能 .......................................................... 31 結(jié) 論 .................................................................. 31 參考文獻(xiàn) .................................................................. 31 致 謝 .................................................................. 33 聲 明 .................................................................. 33 1 引言 選題背景及意義 隨著企業(yè)信息系統(tǒng)的普及和整個社會電子商務(wù)的發(fā)展，現(xiàn)代企業(yè)的運作越來越依賴于信息技術(shù)。越來越多的關(guān)鍵數(shù)據(jù)被存儲在計算機系統(tǒng)中，這些數(shù)據(jù)的丟失和損壞將對企業(yè)造成難以估量 的損失。同時企業(yè)對于數(shù)據(jù)可用性的要求也大為提高，因為即使是短時間的系統(tǒng)停機也將造成業(yè)務(wù)停頓和經(jīng)濟損失。一旦 IT 系統(tǒng)和數(shù)據(jù)遭到災(zāi)難性打擊，企業(yè)將面臨破產(chǎn)的威脅，因此數(shù)據(jù)資料的完好保存是企業(yè)在災(zāi)難后能夠繼續(xù)生存的保證。 容錯技術(shù)是保證系統(tǒng)穩(wěn)定性的重要手段。容錯是指一個系統(tǒng)在發(fā)生故障時仍能正確完成指定任務(wù)的能力。在硬件失效或軟件錯誤的情況下，仍能夠繼續(xù)完成指定任務(wù)的系統(tǒng)稱為容錯系統(tǒng)。容錯技術(shù)是指系統(tǒng)對故障的容忍技術(shù)，也就是指處于工作狀態(tài)的系統(tǒng)中一個或多個關(guān)鍵部分發(fā)生故障或差錯時，能自動檢測與診斷，并能采取相應(yīng)措施 保證系統(tǒng)維持其規(guī)定功能或保持其功能在可接受的范圍內(nèi)的技術(shù)。所有的容錯手段都必須依賴于“保護(hù)性冗余”，即依賴于系統(tǒng)中冗余的部件和算法。所謂“冗余”指的是如果系統(tǒng)是無缺陷的，那么這些部件和算法是不需要的。然而， EVENODD 碼理論的提出為容錯技術(shù)的發(fā)展做出了重要的貢獻(xiàn)。它以一種簡單的方式越來越受到人們的青睞，并在各種系統(tǒng)中廣泛使用，尤其是磁盤陣列布局方案中。其核心運算就是依據(jù)一定的規(guī)則將數(shù)據(jù)簡單相異或。因此對 EVENODD 編碼的研究及其實現(xiàn)具有很強的現(xiàn)實意義。 相近課題研究 容錯技術(shù)在存儲系統(tǒng)中有著廣泛的應(yīng)用 。 目前，已有的適用于存儲系統(tǒng)的容錯技術(shù)主要有三種： 2D奇偶校驗編碼方案（二維奇偶校驗）， RS（ ReedSolomon）碼以及 EVENODD碼。 2D 奇偶校驗編碼方案 2D 奇偶編碼的碼字結(jié)構(gòu)為 n n 的二維陣列，總共有 N2 個信息位，其中校驗信息位為2N 個，即水平校驗和垂直校驗，對矩陣的行和列分別進(jìn)行校驗計算。例如，假定信息位 X是兩個不同的組 C1 和 C2 兩個組的成員，在 C1 組超過 k 個信息位出錯，但是 C2 中少于 k個信息位出錯，那么 X可以通過 C2來恢復(fù)。每個碼字不是一個組的成員，而是多個組的成員，進(jìn)行容錯計算。圖 1 顯示 的是一個二維編碼的策略和二維奇偶校驗碼。 單個的奇偶校驗?zāi)軌蛉萑虇蝹€碼字出錯，二維校驗可以容忍任意的兩個碼字出錯，而且如果增加一個 full parity sever，可以容忍達(dá)到三個碼字出錯。二維編碼策略是通過增加冗余 ，增加服務(wù)器的容錯能力。 冗余數(shù)據(jù)的增加，必定會導(dǎo)致編 碼和譯碼計算量的增加，及 數(shù)據(jù)信息位和校驗信息位之間的比之變化。 row parity full parity parity column parity 圖 1 二維奇偶校驗編碼 糾雙錯 RS 碼 Reed Solomon(RS)是一類有很強糾錯能力的多進(jìn)制 BCH 碼，也是一類典型的幾何碼。它首先是由里德（ Reed）和索洛蒙（ Solomon）應(yīng)用 MS 多相式于 1960 年構(gòu)造出來的。它不僅可以糾正突發(fā)錯誤 , 還可以糾正隨機錯誤 , 特別適用于糾正信號的突發(fā)錯誤。 Reed Solomon code 適合傳送信息符號，而不是比特。 RS 雖然在六十年代就提出來了，但是實際得到應(yīng)用差不多在八十年代。 在 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 ， 兩個校驗列的編碼方程為： 本課題要達(dá)到的設(shè)計目標(biāo) 本論文采用 EVE