Coding Techniques for Data-Storage Systems

Citation

Cassuto, Yuval (2008) Coding Techniques for Data-Storage Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/38ZT-QT95. https://resolver.caltech.edu/CaltechETD:etd-01242008-134459

Abstract

As information-bearing objects, data-storage systems are natural consumers of information-theoretic ideas. For many issues in data-storage systems, the best trade-off between cost, performance and reliability, passes through the application of error-correcting codes. Error-correcting codes that are specialized for data-storage systems is the subject studied by this thesis. On the practical side, central challenges of storage systems are addressed, both at the individual-device level and higher at the enterprise level for disk arrays. The results for individual devices include a new coding paradigm for Multi-Level Flash storage that benefits storage density and access speed, and also a higher-throughput algorithm for decoding Reed-Solomon codes with large decoding radii. The results for storage arrays address models and constructions to combat correlated device failures, and also introduce new highly-regular array-code constructions with optimal redundancy and updates. On the theoretical side, the research stretches across multiple layers of coding theory innovation: new codes for new error models, new codes for existing error models, and new decoding techniques for known codes. To bridge the properties and constraints of practical systems with the mathematical language of coding theory, new well-motivated models and abstractions are proposed. Among them are the models of t asymmetric limited-magnitude errors and clustered erasures. Later, after maximizing the theory's power in addressing the abstractions, the performance of storage systems that employ the new schemes is analytically validated.

Thesis Files