CaltechAUTHORS
  A Caltech Library Service

Correcting Charge-Constrained Errors in the Rank-Modulation Scheme

Jiang, Anxiao (Andrew) and Bruck, Jehoshua and Schwartz, Moshe (2010) Correcting Charge-Constrained Errors in the Rank-Modulation Scheme. IEEE Transactions on Information Theory, 56 (5). pp. 2112-2120. ISSN 0018-9448. https://resolver.caltech.edu/CaltechAUTHORS:20100617-092653362

[img]
Preview
PDF - Published Version
See Usage Policy.

231Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20100617-092653362

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2010.2043764 DOIUNSPECIFIED
ORCID:
AuthorORCID
Bruck, Jehoshua0000-0001-8474-0812
Schwartz, Moshe0000-0002-1449-0026
Additional Information:© 2010 IEEE. Manuscript received April 12, 2009; revised October 07, 2009. Current version published April 21, 2010. This work was supported in part by the NSF CAREER Award CCF-0747415, in part by the NSF Grant ECCS-0802107, in part by the GIF Grant 2179-1785.10/2007, in part by the Caltech Lee Center for Advanced Networking, and in part by an NSF-NRI award. The material in this paper was presented in part at the 2008 IEEE International Symposium on Information Theory, Toronto, Canada, July 2008. The authors would like to thank the anonymous reviewers, who pointed out important previous work, and whose comments helped improve the presentation of the paper.
Funders:
Funding AgencyGrant Number
NSFCCF-0747415
NSFECCS-0802107
GIF2179-1785.10/2007
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
NSF- Nanoelectronics Research Initiative (NRI)UNSPECIFIED
Subject Keywords:Error-correcting codes; flash memory; Kendall's tau-metric; metric embeddings; permutations; rank modulation
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11256641
Issue or Number:5
Record Number:CaltechAUTHORS:20100617-092653362
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20100617-092653362
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18718
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:29 Jun 2010 18:28
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page