Coding for Storage Systems

Zhiying Wang

California Institute of Technology

 Abstract:

We will present two topics: partial rank modulation for flash memory and optimal rebuilding for RAID. Rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose partial rank modulation, where only part of the n cells are used to represent data.

We present Gray codes spanning all possible partial-rank states and using only “push-to-the-top” operations. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In this talk we will show that the lower bound of 1/2 is achievable and that the result can be generalized to optimally rebuild an arbitrary number of parities.

Biography:

Zhiying Wang is a graduate student in Department of Electrical Engineering at Caltech. She is a member of Paradise Laboratory which is headed by her adviser, Professor Shuki Bruck.  She earned her Bachelor's Degree in Department of Electronic Engineering at Tsinghua University, Beijing. Her research interest includes information theory, error-correcting codes and coding for storage devices.