UC San Diego

This dissertation addresses various problems related to data encoding and error-correction techniques to design more reliable and higher density digital data storage technologies. In the second chapter, the problem of rewriting for multilevel flash memories is considered and a novel construction method for WOM codes based on lattices is proposed. Using the continuous approximation, hyperbolic write-regions are shown to be sum-rate optimal for arbitrary number of writes. An algorithm that determines an optimal encoding scheme is proposed for the case of two cells. Using these ideas, WOM codes are proposed that achieve high sum-rates. In the third chapter, the problem of designing a block-precoder for a magnetic recording channel is considered with the objective of minimizing the error rate. The precoder design problem is equivalent to solving a quadratic assignment problem which is NP-complete in general. Precoders are constructed using a branch-and-bound technique with a reduced search space, as well as using a sub-optimal local search algorithm. Simulation results show that these block-precoders out- perform existing precoding techniques. The fourth chapter discusses a novel technique for using polar codes for partial response channels. Multiple polar codes of various rates are designed for memoryless channels estimated by removing the effects of intersymbol interference from the partial response channel. Data is encoded using these codes and the codewords are interleaved before transmission. Decoding is done sequentially using a multi- stage decoding technique. Simulation results demonstrate that the performance of these codes is comparable to LDPC codes. The fifth chapter studies the performance of stochastic decoding on LDPC code ensembles in the limit of infinite blocklength. Two methods to perform the density evolution for stochastic decoding are provided. Alternative descriptions of the variable node update in stochastic decoding are given and connections to other decoding algorithms are highlighted. The sixth chapter explores the performance of binary images of non-binary LDPC codes. For the binary erasure channel, it is shown that the collection of stopping sets for a non-binary LDPC code are a subset of the collection of stopping sets of its basic binary image. An efficient algorithm is proposed that eliminates these additional stopping sets by adding redundant parity checks to the basic binary images. Simulation results confirm that the few redundant checks are sufficient to match the performance of the original non-binary LDPC codes with lower complexity