A Caltech Library Service

Correcting Charge-Constrained Errors in the Rank-Modulation Scheme

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)

See Usage Policy.


Use this Persistent URL to link to this item:


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)
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Group:Parallel and Distributed Systems Group
Subject Keywords:flash memory, rank modulation, errorcorrecting codes, permutations, metric embeddings, Kendall's τ-metric
Record Number:CaltechPARADISE:2009.ETR095
Persistent URL:
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.
ID Code:26126
Deposited By: Imported from CaltechPARADISE
Deposited On:21 Sep 2009
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page