Coding for Flash Memory

Flash memories are by far the most important non—volatile memories (NVMs), accounting for 90% of the NVM market. Billions of flash memories are used in mobile, embedded and mass—storage systems because of their high performance and physical durability. Well known applications of flash memories include solid—state drives (SSDs), cell phones, digital cameras, USB flash drives, sensors, and many more. Based on the well—studied floating—gate technology, the dominance of flash memories will continue.

There exist, however, critical challenges that limit the improvement of flash—memory performance with respect to their speed, longevity, reliability and power efliciency. A flash memory uses the charge stored in floating—gate cells to represent data; and to remove charge from any cell, a whole block of cells (about 105 ~ 106 cells) must be erased altogether and reprogrammed. This makes the writing speed and power efliciency (for data modification) very low compared to reading. A flash memory block guarantees to endure only about 104 ~ 105 erasures before it breaks down, which significantly limits its longevity. Since data are written into cells via charge injection, and the over—injection of charge into any cell leads to the very expensive block erasure/reprogramming operation, cells have to be programmed very conservatively using multiple rounds of programming, which significantly reduces the writing speed. Furthermore, when the charge levels in cells are disturbed by various noise mechanisms, the high cost of block erasure prevents the errors from being physically corrected in place, which constrains the reliability of data. All these challenges become even more pronounced when more bits are stored in cells (by using more charge levels) for higher storage capacity.

In this project, the Pls explored new coding strategies to combat these significant challenges, and to sub» stantially improve the performance of flash memories. The research addressed spanned a wide variety of areas, including graph theory, metric embeddings, information theory, coding theory, group theory, and more. The re» search focused on two key new areas: (1) coding for rewriting, in which the research team studied the rewriting operation (ie, the operation of modifying data) without the need to use expensive block erasures. The research products included the design and analysis of rewriting schemes that combine error correcting capabilities. (2) rank modulation coding schemes, in which the research team studied novel methods for data representation using the order of cells’ charge levels — instead of their absolute values — to store data, so that cells can be programmed very efficiently and robustly. The research products included efficient coding schemes for flash memory based on rank modulation.

The applicative potential of this research is immense. All research products relate to practical aspects of systems involving flash memory, spanning the whole spectrum from the physical level to the information-theoretic level. The rank—modulation scheme alleviates some of the physical—level problems of data reliability, device aging, and storage capacity. Above it, rewriting codes tackle the problem of rapid cell saturation. Finally, the error-correction allows better performance in terms of error-rate. Since there is an obvious trade-off between the different system parameters, the results enable to push the limiting performance envelope of flash memory, creating faster, smaller, cheaper, and more reliable devices.