UC San Diego

Flash memories are, by far, the most important type of non -volatile memory in use today. They are employed widely in mobile, embedded, and mass-storage applications, and the growth in this sector continues at a staggering pace. Moreover, since flash memories do not suffer from the mechanical limitations of magnetic disk drives, solid- state drives have the potential to upstage the magnetic recording industry in the foreseeable future. The research goal of this dissertation is the discovery of new coding theory methods that supports efficient design of flash memories. Flash memory is comprised of blocks of cells, wherein each cell can take on q ̲> 2 levels. While increasing the cell level is easy, reducing its level can be accomplished only by erasing an entire block. Such block erasures are not only time-consuming, but also degrade the memory lifetime. Our main contribution in this research is the design of rewriting codes that maximize the number of times that information can be written prior to incurring a block erasure. Examples of such coding schemes are flash/floating codes and buffer codes, introduced by Jiang and Bruck et al. in 2007, and WOM- codes that were presented by Rivest and Shamir almost three decades ago. The overall goal in these codes is to maximize the amount of information written to a fixed number of cells in a fixed number of writes. Furthermore, the design of error-correcting codes in flash memories is extensively studied. It is shown how to modify WOM-codes to support an error-correction capability. Motivated by the asymmetry of the error behavior of flash memories and the work by Cassuto et al., a coding scheme to correct asymmetric errors is presented. An extensive empirical database of errors was used to develop a comprehensive understanding of the error behavior as well as to design specific error-correcting codes for flash memories. This research on flash memories is expanded to other directions. Wear leveling techniques are widely used in flash memories in order to reduce and balance block erasures. It is shown that coding schemes to be used in these techniques can significantly reduce the number block erasures incurred during data movement. Also, the design of parallel cell programming algorithms is studied for the specific constraints and behavior of flash cells