Jiang, Anxiao (Andrew) and Schwartz, Moshe and Bruck, Jehoshua (2009) Correcting Charge-Constrained Errors in the Rank-Modulation Scheme. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2009.ETR095
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2009.ETR095
We investigate error-correcting codes for a novel storage technology for flash memories, the rank-modulation scheme. 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 binary codes in the Hamming metric as well as q-ary 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.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Subject Keywords:||flash memory, rank modulation, errorcorrecting codes, permutations, metric embeddings, Kendall's τ-metric|
|Official Citation:||Anxiao (Andrew) Jiang, Moshe Schwartz, and Jehoshua Bruck. Correcting Charge-Constrained Errors in the Rank-Modulation Scheme. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR095]|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||21 Sep 2009|
|Last Modified:||26 Dec 2012 13:54|
Repository Staff Only: item control page