Coding Techniques to Extend the Lifetime of Flash Memories

NAND flash memory has become a widely used data storage technology. It uses rectangular arrays, or blocks of floating-gate transistors (commonly referred to as cells) to store information. The flash memory cells gradually wear out with repeated writing and erasing, referred to as program/erase (P/E) cycling, but the damage caused by P/E cycling is dependent on the programmed cell level. For example, in SLC flash memory, each cell has two different states, erased and programmed, represented by 1 and 0, respectively. Storing 1 in a cell causes less damage, or wear, than storing 0. More generally, in multilevel flash memories, the cell wear is an increasing function of the programmed cell level. The main research goal of this dissertation is to design new coding techniques that can extend the lifetime of flahs memories. The damage caused by programming the cell is usually modeled as a cost, and increasing the lifetime of flash memories can be converted to the problem of encoding information for use on channels with a cost constraint. This type of code is often referred to as a shaping code. Therefore in this dissertation we study rate-constrained shaping codes for noiseless costly channels. We systematically investigate the fundamental performance limits of fixed-to-variable length shaping codes from a rate and distribution perspective for a memoryless channel. Then, we study a recently proposed rate-1 direct shaping code and study its error propagation property. In addition, we consider shaping codes for finite-state noiseless costly channels. One observation from the above analysis is that an optimal shaping code for a memoryless channel generates a codeword sequence that approximates an i.i.d. process, and an optimal shaping code for a finite-state channel generates a codeword sequence that approximates a stationary Markov process. In this dissertation, we study the connection between shaping codes and distribution matching codes that map a sequence of i.i.d. source symbols into an output sequence that approximates an i.i.d. or a stationary Markov process. In the flash memory device, the bit error count (BEC) behavior varies significantly among pages. Therefore we propose a bad page detector, which predicts whether a page will become a ``bad'' page in the near future based on its current and previous BEC information. Two machine learning algorithms, based upon time-dependent neural network and long-short term memory architectures, are used to design the detector