CaltechTHESIS
  A Caltech Library Service

Coding for Information Storage

Citation

Wang, Zhiying (2013) Coding for Information Storage. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/TFHZ-RW88. https://resolver.caltech.edu/CaltechTHESIS:05312013-123819501

Abstract

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r 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 Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, 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 two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Information theory, coding theory, flash memory, distributed storage
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Bruck, Jehoshua
Thesis Committee:
  • Bruck, Jehoshua (chair)
  • Hassibi, Babak
  • Effros, Michelle
  • Ho, Tracey C.
  • Winfree, Erik
Defense Date:14 March 2013
Record Number:CaltechTHESIS:05312013-123819501
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:05312013-123819501
DOI:10.7907/TFHZ-RW88
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7792
Collection:CaltechTHESIS
Deposited By: Zhiying Wang
Deposited On:03 Jun 2013 21:06
Last Modified:07 Jun 2023 17:24

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page