Computer Science – Information Theory
Scientific paper
2009-07-20
Computer Science
Information Theory
Scientific paper
We study error-correcting codes for permutations under the infinity norm, motivated by a novel storage scheme for flash memories call rank modulation. In this scheme, a set of $n$ flash cells are combined to create a single virtual multi-level cell. Information is stored in the permutation induced by the cell charge levels. Spike errors, which are characterized by a limited-magnitude change in cell charge levels, correspond to a low-distance change under the infinity norm. We define codes protecting against spike errors, called limited-magnitude rank-modulation codes (LMRM codes), and present several constructions for these codes, some resulting in optimal codes. These codes admit simple recursive, and sometimes direct, encoding and decoding procedures. We also provide lower and upper bounds on the maximal size of LMRM codes both in the general case, and in the case where the codes form a subgroup of the symmetric group. In the asymptotic analysis, the codes we construct out-perform the Gilbert-Varshamov-like bound estimate.
Schwartz Moshe
Tamo Itzhak
No associations
LandOfFree
Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-696231