Coding for Storage Systems
Jul 13, 2012
from 01:00 PM to 02:30 PM
|Where||ENGR. IV Bldg., Tesla Rm. 53-125|
|Contact Name||Prof. Lara Dolecek|
|Add event to calendar||
California Institute of Technology
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 ﬂash 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.
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.