A nearly optimal construction of flash codes

Abstract Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q dif-ferent values or levels. While increasing the cell level is easy, re-ducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes known as oating codes or ash codes have been de-signed in order to maximize the number of times that information stored in a ash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)q ash code C is a cod-ing scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0! 1 or 1! 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level tran-sitions in n cells is n(q1), and the write deciency of C, dened as (C) = n(q1) t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k> 6 and large n, the best previously known construction of ash codes achieves a write deciency of O(qk2). On the other hand, the best known lower bound on write deciency is (qk). In this paper, we pre-sent a new construction of ash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we rst im-prove upon the so-called indexed ash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write deciency of the resulting ash codes is O(qk log k) if q> log2 k, and at most O(k log 2 k) otherwise. I