Dissertation Defense- Nattakan PuttarakDissertation Defense: Nattakan Puttarak
Topic: Coding for disk storages: Disk arrays, Flash memory, and Distributed Storage Networks
Committee members: Prof. Tiffany Jing Li (Chair and advisor)
Prof. Meghanad D. Wagh
Prof. Shalinee Kishore
Prof. Liang Cheng
Date and location: Friday, July, 15th, 2011, 9.30am-11.30am, PA360
The explosive demand for digital data storage with a higher areal density, a larger storage capacity, a higher reliability and fault tolerance, easier accessibility, cheaper management and better scalability, poses tremendous challenge on the storage industry. This doctoral research explores emerging coding technologies that will potentially lead to new and better storage systems to meet some of the above demanding goals. In this dissertation, we consider three important storage systems: hard disk arrays, distributed storage networks, and flash memories. However, the coding for disk storages and the one for flash memories are different in terms of coding technology, implementation, and complexity. Thus, coding techniques to construct error/erasure-correcting code (ECC) for disk storages and flash memories are different.
In the case of disk arrays, we demonstrate the idea of constructing and class of nested codes, termed complete-graph-of-ring (CGR) graphs, and use them to form a class of optimal array codes, termed CGR codes, that are maximum distance separable (MDS). Systematic and concrete construction methods for CGR codes and their dual codes are developed and it is shown that these codes not only deliver optimal erasure protection with low complexity, but they also provide a rich array of code rates and code lengths. The CGR array codes are also presented as the systematic low-density (sparse) array codes shown by the generator matrix and parity-check matrix. For distributed storage networks, we develop hierarchical strategies to achieve good erasure protection. By dividing the entire system in layered clusters and designing appropriate erasure coding for each layer, we show that a good trade-off between protection capability, redundancy overhead, communication overhead, and computational complexity can be achieved.
In the case of flash memories, the new coding schemes are designed to best map cell states to data bits and vice versa. Our goal is to maximize the writing time in each cell state before a block-erased process is required. We demonstrate an idea which allows some two-bit updates to be represented by only one cell raise (rather than two cell raises) and the new performance metric called word-write. We also introduce the word-write efficiency and optimal in our proposed codes, termed the word-efficient bit-efficient (WEBE) code and the word-optimal bit-optimal (WOBO) code. In addition, we introduce the flash marker (FM) code to reserve a set of cells for the most written bits in order to avoid a block erasure. From all of the above, we have beaten the conventional performance bound and opened new possibilities for data representation in flash memories.