Combinatorial and algebraic coding techniques for flash memory storage

Error-correcting codes are used to achieve reliable and efficient transmission when storing or sending information across a noisy channel. This thesis investigates a mathematical approach to coding techniques for storage devices such as flash memory storage, although many of the resulting codes and coding schemes can be applied in other contexts. The main contributions of this work include the design of efficient codes and decoding algorithms using discrete structures such as graphs and finite geometries, and developing a variety of strategies for adapting codes to a multi-level setting. Information storage devices are prone to errors over time, and the frequency of such errors increases as the storage medium degrades. Flash memory storage technology has become ubiquitous in devices that require high-density storage. In this work we discuss two methods of coding that can be used to address the eventual degradation of the memory. The first method is rewriting codes, a generalization of codes for write-once memory (WOM), which can be used to prolong the lifetime of the memory. We present constructions of binary and ternary rewriting codes using the structure of finite Euclidean geometries. We also develop strategies for reusing binary WOM codes on multi-level cells, and we prove results on the performance of these strategies. The second method to address errors in memory storage is to use error-correcting codes. We present an LDPC code implementation method that is inspired by bit-error patterns in flash memory. Using this and the binary image mapping for nonbinary codes, we design structured nonbinary LDPC codes for storage. We obtain performance results by analyzing the probability of decoding error and by using the graph-based structure of the codes