Novel Coding Strategies for Multi-Level Non-Volatile Memories

Non-volatile memories (NVMs) are the most important modern data storage technology. Despite their significant advantages, NVMs suffer from poor reliability due to issues such as voltage drift over time, overwriting, and inter-cell coupling. This thesis applies coding-theoretic techniques to NVMs in order to improve their reliability and extend their lifetimes. In particular, we focus on two classes of problems: those related to the use of thresholds to read memory cells, and those related to inter-cell coupling in the data representation scheme known as rank modulation. The first part of the thesis develops the concept of dynamic thresholds. In NVMs, reading stored data is typically done by comparing cell values against a set of predetermined, fixed threshold references. However, due to common NVM problems, fixed threshold usage often results in significant asymmetric errors. To combat these problems, the notion of dynamic thresholds was recently introduced. Such thresholds are allowed to change in order to react to changes in cell value distributions. Thus far, dynamic thresholds have been applied to the reading of binary sequences in memories with single-level cells (SLCs). In this work, the use of dynamic thresholds for multi-level cell (MLC) memories is explored. A general scheme to compute and apply dynamic thresholds is provided. We derive a series of performance results, based on both practical considerations and theoretical analysis. We show that the proposed threshold scheme compares favorably with the best-possible threshold scheme. Finally, we develop error-correcting codes that are tailored to take advantage of the properties of dynamic thresholds. Code constructions are provided for different channel models, including those allowing limited and unlimited numbers of errors of varying magnitude limitations. The second part of this thesis is focused on the application of constrained coding to rank modulation. Rank modulation is an MLC NVM scheme where information is represented by the rankings of charge levels in an entire block of cells, rather than the absolute charge level of any particular cell. This scheme resolves certain NVM problems, including write-asymmetry, as it allows for a transition from any information state to any other solely through the addition of charge to an appropriate subset of cells. However, the scheme still suffers from inter-cell coupling errors. Such errors are due to inadvertent charge level increases in cells whose neighboring cells have significantly larger levels. We introduce constraints that mitigate the inter-cell coupling problem in rank modulation. These constraints typically limit the differences between the ranks of neighboring elements in a permutation, and thus limit the charge level differences between adjacent cells, reducing inter-cell coupling effects. In particular, we analyze the single neighbor k-constraint, where neighboring cells' ranks cannot differ by more than k. We provide the best-known bounds for the sizes of sets meeting this constraint, and, for certain cases where the parameter k involves a constant term, we derive exact expressions. We perform an asymptotic analysis. Lastly, we introduce an efficient scheme that allows us to systematically generate constrained permutations