郭斯彥臺灣大學：電機工程學研究所林語亭Lin, Yu-TingYu-TingLin2007-11-262018-07-062007-11-262018-07-062004http://ntur.lib.ntu.edu.tw//handle/246246/53175隨著網際網路及各種多媒體資料庫的發展，一個大型的儲存系統(如大型磁碟陣列系統)可以說是越來越重要，除了必須提供高速的介面供使用者存取，還必須提供非常穩定的資料保存環境，以防寶貴的資料因為各種可能的狀況而喪失。為了達到如此的目的，釵h系統容錯的方式便應運而生。我們希望能透過硬體或軟體的方式，使得資訊能夠可靠且正確的來做傳遞或是保存以因應各種可能使資料受到威脅的可能狀況(諸如熱雜訊、機器故障、不佳的保存環境或傳播通道等)。在各種容錯技術中，又以錯誤更正碼為最重要。不同的錯誤更正碼常被設計用來適應在各種不同的環境中，以因應各種環境可能遇到的資訊喪失。 本論文將提出的針對”大型磁碟陣列系統”所設計的特用”里德所羅門碼”演算法，便是使用發展已趨成熟的里德所羅門碼，針對大型磁碟陣列系統特有的環境所做的特別改良與設計，用來因應兩顆以上磁碟同時失效的狀況in RAID system，使失效硬碟的資料能夠完整的恢復，使系統能在不中斷的狀況下正常的運作。Because of rapid development of inter-net and multi-media data bases, need for a big storage system becomes more and more important. The advanced storage system must provide rapid data processing ability and stable storage environment in order to avoid data losing. For the purpose mentioned above, many fault-tolerant methods are derived. We hope that information can be transmitted and stored correctly by some methods using software or hardware when there are disturbances, like heat noise, broken machine, noisy transmitting channel and so on. Error control coding is the most important method within all error concealing methods. Different error correcting codes are designed in different environments in order to avoid error losing. In the thesis, we will use Reed Solomon Code which is designed according to properties of advanced RAID system to handle two disk failures in RAID system. Therefore, the failed data in disks can be recovered and system still can work as usual without broken.Contents Chinese Abstract English Abstract 1 Introduction ...…………...…………………………………………………………1 1.1 Motivation and Purpose of the Thesis……………………….…………….…..2 1.2 RAID (Redundant Array of Inexpensive Disks)………………………………3 1.2.1 RAID 0………………………………………………………………...4 1.2.2 RAID 1…………………………………………………………..…….4 1.2.3 RAID 0+1……………………………………………………………...6 1.2.4 RAID 5………………………………………………………………...6 1.2.5 RAID 6………………………………………………………………...7 1.3 Proposed algorithm and contributions ………………………………………...8 1.4 Organization of the thesis……………………………………………………...8 2 Introduction of Reed Solomon Code…………………………………………..10 2.1 Basic properties of RS codes……………………………………………………..11 2.2 The basic concepts of finite field and BCH codes….............................................12 2.2.1 Finite Field……………………………………………………………..12 2.2.2 The construction of ………………………………………….15 2.2.3 BCH bound (Designed Distance)………………………………………19 2.3 Basic Design flow and Encoding of RS Codes…………………………………..19 2.3.1 Basic Design of RS codes……………………………………………...19 2.3.2 Systematic coding………………………………………………..…….21 2.4 Decoding of RS Codes…………………………………………………………...23 2.4.1 Peterson-Gorenstein-Zierler decoding algorithm………………………23 2.4.2 Decoding agorithms used in industrial circles……………………..…..25 3 Construction of RAID6 system………………………………………………...28 3.1 Data Mapping from Hard disks to RS code……………………………………...28 3.2 Design flow and Data writing (Encoding of RS codes)………………………….30 3.2.1 Basic Design flow and encoding…………………………………...…..30 3.2.2 Data Update…………………………………………………………….32 3.2.3 Shortened Code………………………………………………………...33 3.3 Data reading(Decoding of RS codes)…………………………………………….34 4 System Optimization and Related Circuits Design……………………..…….39 4.1 Circuits Design for Multiplier……………………………………………………40 4.1.1 General Multiplier……………………………………………………...40 4.1.2 Constant Multiplier……………………………………….……………42 4.2 System Optimization and Circuits Implementation of RS code Codec for RAID 6 Architectur……………..……………………………………………44 4.2.1 Selection of Roots for Generator Polynomial………………………….44 4.2.2 Design for RS Encoder…………………………………………………45 4.2.3 Design of RS Decoder………………………………………………..51 5 Comparisons and analysis with the existing RAID-6 algorithm……………..54 5.1 EvenOdd Code………………………………………………………………..….54 5.2 comparisons between EvenOdd Code and RS Code…………………………..…57 5.2.1 data mapping…………………………………………………………...58 5.2.2 Update Complexity…………………………………………………….58 5.2.3 Analysis of coding computation……………………………………...59 5.3 A comparison sheet.………………………………………………………………62 6 Conclusions and Future works…………………………………………………64 6.1 conclusions……………………………………………………………...………..64 6.2 Future work………………………………………………………………………65 Reference Appendix cm.java – construction of the list of constant multipliers in gp.java – to compute the number of XOR gates used by encoding. List of Figures 1.1:Block diagram of a typical data transmission or storage system……………….....2 1.2 RAID level 0………………………………………………………………………4 1.3 RAID level 1……………………………………………………………………....5 1.4 RAID level 0+1……………………………………………………………………5 1.5 RAID level 6………………………………………………………………………7 2.1: The mathematical background of RS codes……………………………………..12 2.2:Systematic coding………………………………………………………………..22 2.3:Decoding flow of Reed Solomon Code………………………………………….26 3.1:Encode m(x) by RS Encoder……………………………………………………..29 3.2:Data Mapping…………………………………………………………………….29 4.1: Circuit diagram for a general multiplier in GF(24 )……………………………..41 4.2: Logic-circuit diagram of ……………………………………………….42 4.3: General CRC division circuits………………………………………………..…46 4.4:Circuit to solve 2 erasures……………………………………………………..…52 5.1: Structure of EvenOdd Code……………………………………………………..55 5.2: Encoding of an (7,5) EvenOdd Code…………………………………………....56 5.3: Decoding of an (7,5) EvenOdd Code (2-erasures)……………………………....56 5.4: 3-Dimention structure of EvenOdd Code……………………………………..…58 5.5:The number of XOR gates to encode m bytes of RS code……………………….60 5.6:The number of XOR gates to encode m*(m-1) bytes…………………………....61 List of Tables 2.1:Operation Table for GF(3)………………………………………………………..14 2.2:Primitive polynomials……………………………………………………………16 2.3:elements in ……………………………………………………………..17 3.1:Elements in …………………………………………………………….30 4.1:Elements in GF(24 )………………………………………………………………39 4.2:List of Contant Multiplier for ………………………………………….44 4.3:List of Checksum Table…………………………………………………………..48 5.1: a comparison sheet between RS code and EvenOdd Code…………………...…63671825 bytesapplication/pdfen-US錯誤更正碼可靠度里德所羅門碼磁碟陣列RAIDreliabilityReed Solomon CodeRSthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53175/1/ntu-93-R91921089-1.pdf