Error correcting codes for rank modulation
Abstract
We investigate error-correcting codes for a novel storage technology, which we call the rank-modulation scheme. In this scheme, a set of n cells stores information in the permutation induced by the different levels of the individual cells. The resulting scheme eliminates the need for discrete cell levels, and overshoot errors when programming cells (a serious problem that reduces the writing speed), as well as mitigates the problem of asymmetric errors. In this discussion, the properties of error correction in rank modulation codes are studied. We show that the adjacency graph of permutations is a subgraph of a multi-dimensional array of a special size, a property that enables code designs based on Lee-metric codes and L1-metric codes. We present a one-error-correcting code whose size is at least half of the optimal size. We also present additional error-correcting codes and some related bounds.
Subject
714/773365/185.03
714/781
H03M 13/033
H03M 13/19
G06F 11/1072
H04L 1/0057
G11C 2211/5634
G11C 7/1006
G11C 29/00
Collections
Citation
Jiang, Anxiao; Schwartz, Moshe; Bruck, Jehoshua (2012). Error correcting codes for rank modulation. United States. Patent and Trademark Office; Texas A&M University. Libraries. Available electronically from https : / /hdl .handle .net /1969 .1 /176998.