Rewriting Schemes for Flash Memory

Flash memory is a leading storage media with excellent features such as random access and high storage density. However, it also faces significant reliability and endurance challenges. In flash memory, the charge level in the cells can be easily increased, but removing charge requires an expensive erasure operation. In this thesis we study rewriting schemes that enable the data stored in a set of cells to be rewritten by only increasing the charge level in the cells. We consider two types of modulation scheme; a convectional modulation based on the absolute levels of the cells, and a recently-proposed scheme based on the relative cell levels, called rank modulation. The contributions of this thesis to the study of rewriting schemes for rank modulation include the following: we •propose a new method of rewriting in rank modulation, beyond the previously proposed method of “push-to-the-top”; •study the limits of rewriting with the newly proposed method, and derive a tight upper bound of 1 bit per cell; •extend the rank-modulation scheme to support rankings with repetitions, in order to improve the storage density; •derive a tight upper bound of 2 bits per cell for rewriting in rank modulation with repetitions; •construct an efficient rewriting scheme that asymptotically approaches the upper bound of 2 bit per cell. The next part of this thesis studies rewriting schemes for a conventional absolute-levels modulation. The considered model is called “write-once memory” (WOM). We focus on WOM schemes that achieve the capacity of the model. In recent years several capacity-achieving WOM schemes were proposed, based on polar codes and randomness extractors. The contributions of this thesis to the study of WOM scheme include the following: we •propose a new capacity-achievingWOM scheme based on sparse-graph codes, and show its attractive properties for practical implementation; &#82