Search

The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: 1) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and 2) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank-modulation with rewriting. The key benefits of the new scheme include: 1) the ability to store close to 2 bit per cell on each write with minimal impact on the lifetime of the memory and 2) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory codes that were proposed recently. [ABSTRACT FROM PUBLISHER]

The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile memories. In this paper, we explore $[n,k,d]$ systematic error-correcting codes for rank modulation. Such codes have length $n$ , $k$ information symbols, and minimum distance $d$ . Systematic codes have the benefits of enabling efficient information retrieval in conjunction with memory-scrubbing schemes. We study systematic codes for rank modulation under Kendall’s $\tau $ -metric as well as under the $\ell _\infty $ -metric. In Kendall’s $\tau $ -metric, we present $[k+2,k,3]$ systematic codes for correcting a single error, which have optimal rates, unless systematic perfect codes exist. We also study the design of multierror-correcting codes, and provide a construction of $[k+t+1,k,2t+1]$ systematic codes, for large-enough $k$ . We use nonconstructive arguments to show that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. Finally, in the $\ell _\infty $ -metric, we construct two $[n,k,d]$ systematic multierror-correcting codes, the first for the case of $d=O(1)$ and the second for $d=\Theta (n)$ . In the latter case, the codes have the same asymptotic rate as the best codes currently known in this metric. [ABSTRACT FROM PUBLISHER]

We investigate error-correcting codes for a the rank-modulation scheme with an application to flash memory devices. In this scheme, a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, overcomes overshoot errors when programming cells (a serious problem that reduces the writing speed), and mitigates the problem of asymmetric errors. In this paper, we study the properties of error-correcting codes for charge-constrained errors in the rank-modulation scheme. In this error model the number of errors corresponds to the minimal number of adjacent transpositions required to change a given stored permutation to another erroneous one--a distance measure known as Kendall's τ-distance. We show bounds on the size of such codes, and use metric-embedding techniques to give constructions which translate a wealth of knowledge of codes in the Lee metric to codes over permutations in Kendall's τ-metric. Specifically, the one-error-correcting codes we construct are at least half the ball-packing upper bound. [ABSTRACT FROM AUTHOR]