Search

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]