Fault-tolerant Of Storage Systems And Array Codes

Fault-tolerant is an important issue to a large-scale storage systems. Coding theory provides an effective way to improve the reliability of data storage system.Accounting into the system's fault tolerance, coding computational complexity, and update complexity of storage systems, a class of binary array codes is regard as a good solution. But comparing to communication coding theory, there are no such a solid theoretical foundation and rich results to array codes. At present, only some 2-erasure array codes are used in storage systems, and the code length of those array codes are usually limited to prime numbers in order to achieve those optimal performance. Moreover, they are usually hard to be expanded to the multiple fault-tolerant case.This thesis firstly summarizes the current commonly used 2-erasure array codes,then gives a systematic definitions of array codes with the language of combinatorics. Base on the definitions,we give a standardized representation of array codes,and then study some basic characteristics of array codes.In order to construct exactly codes for specific optimized goals,the thesis studies two basic classes array codes,they are:1.Parity-dividable array code:In order to illustrate the law of this structure, the thesis; develops a kind of permutation-vector algebra as a research tool. With this tool,we find out the relations between the parity map permutation's circle structure and the code's fault-tolerant ability. With the well-known combinatorial structure--latin square, we construct a class of 2-erasure codes which is proved to be the expansion of several known 2-erasure codes. Further-more,with permutation-vector algebra, we gives the multi-fault-tolerant construction of LS-code. In addition, to break the limit of the short code length,we construct a class of codes named Cascade-Latin code.2.Cyclic array codes.The thesis gives some basic structures of cyclic array codes.Base on this, we study the longest lowest-density array codes. First we gives the upper bound to the code length of those codes. With a well known combinatorics structure:"NRB" (Near Resolv-able Balanced Incomplete Block Designs), the article presents a 3-erasure longest lowest-density array codes named T-code.Finally, from the overall perspective, the thesis analyze the reliability of storage system base on FULL-2 code. The analysis point out that those non-MDS codes are also has good performance in some case.The article try to build a systematic theory frame to the array codes. This is very useful to the further research.