On coding efficiency for flash memories

Xudong Ma

Abstract

Flash memory cells degrade with each erase cycle, limiting device longevity. This work establishes a formal information-theoretic framework for "coding efficiency"—defined as the information stored per unit of erase cost. By modeling flash as a multi-level Write-Once-Memory (WOM), we derive fundamental upper and lower bounds for this efficiency, demonstrating a necessary trade-off between instantaneous payload and total lifetime capacity.

Introduction

Unlike traditional magnetic storage, flash memory is a consumable resource. Each cell consists of a floating-gate transistor where programming (adding electrons) is relatively simple, but erasure (removing electrons) requires high voltages that physically degrade the silicon. Most commercial flash can survive only 5,000 to 100,000 erase cycles. Because erasures occur at the block level while programming occurs at the page level, flash memory behaves similarly to Write-Once-Memory (WOM). This paper seeks to maximize the total information stored over the entire lifetime of a flash device by optimizing coding schemes relative to the "cost of erasure."

Theoretical Framework and Methodology

The study models a flash block as $N$ cells, each capable of holding $K$ voltage levels. Programming is modeled as a process that can only decrease the voltage level, necessitating an erase to reset.

To determine the limits of performance, the author employs several information-theoretic tools:

  1. Achievability: Using random binning and typical sequences, the paper defines the conditions under which a sequence of data rates can be reliably recorded between erases.
  2. Optimization: Lagrangian multipliers are used to solve a relaxed optimization problem, yielding a closed-form expression for the theoretical maximum efficiency.
  3. Lower Bounds: A specific multi-stage random coding scheme is constructed, where cells are restricted to shifting between adjacent states, providing a practical "floor" for achievable efficiency.

The Efficiency-Payload Trade-off

A central insight of this research is the fundamental trade-off between payload and efficiency. If a system attempts to maximize the data stored in a single write (high payload), it exhausts the cell's "voltage budget" rapidly, leading to low overall coding efficiency. Conversely, recording data in smaller increments allows for significantly higher total information density over the cell's life.

Upper and lower bounds for coding efficiency as a function of payload.

As shown in Figure 1, the upper bound (blue dashed line) and lower bound (red solid line) for a 3-bit (TLC) flash cell both exhibit a sharp decline as payload increases. At very low payloads, coding efficiency can theoretically exceed 14 bits per unit cost, but this advantage diminishes as the payload approaches the cell's physical capacity.

Key Results and Implications

The paper proves that as the number of cells $N$ approaches infinity, the optimal coding efficiency can also approach infinity, provided the payload per write is sufficiently small. It provides specific formulas for calculating cost and rate functions based on a tuning parameter $eta$, which allows system designers to balance speed (payload) against longevity (efficiency).

Limitations and Future Work

While providing a rigorous theoretical foundation, the model assumes statistical independence between messages in different rounds, which may not hold in real-world file systems. Furthermore, the random coding arguments used to prove achievability do not immediately translate to low-latency hardware implementations. Future research should focus on developing practical, low-complexity codes—such as Polar or LDPC codes—that can approach these theoretical efficiency bounds in physical hardware.

Summary updated

BibTeX
@inproceedings{ma2012coding,
  author = {Xudong Ma},
  title = {{On coding efficiency for flash memories}},
  booktitle = {Sarnoff Symposium},
  year = {2012},
  doi = {10.1109/sarnof.2012.6222744},
}
Figure