CaltechAUTHORS
  A Caltech Library Service

Systematic Error-Correcting Codes for Rank Modulation

Zhou, Hongchao and Schwartz, Moshe and Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2014) Systematic Error-Correcting Codes for Rank Modulation. IEEE Transactions on Information Theory, 61 (1). pp. 17-32. ISSN 0018-9448. https://resolver.caltech.edu/CaltechAUTHORS:20150202-150301749

[img] PDF - Submitted Version
See Usage Policy.

211Kb

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

Abstract

The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile memories. In this paper, we explore [n, k, d] systematic error-correcting codes for rank modulation. Such codes have length n, k information symbols, and minimum distance d. Systematic codes have the benefits of enabling efficient information retrieval in conjunction with memory-scrubbing schemes. We study systematic codes for rank modulation under Kendall's T-metric as well as under the ℓ∞-metric. In Kendall's T-metric, we present [k + 2, k, 3] systematic codes for correcting a single error, which have optimal rates, unless systematic perfect codes exist. We also study the design of multierror-correcting codes, and provide a construction of [k + t + 1, k, 2t + 1] systematic codes, for large-enough k. We use nonconstructive arguments to show that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. Finally, in the ℓ∞-metric, we construct two [n, k, d] systematic multierror-correcting codes, the first for the case of d = 0(1) and the second for d = Θ(n). In the latter case, the codes have the same asymptotic rate as the best codes currently known in this metric.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2014.2365499DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6937135PublisherArticle
http://www.paradise.caltech.edu/papers/etr112.pdfRelated ItemTechnical Report
http://arxiv.org/abs/1310.6817arXivDiscussion Paper
ORCID:
AuthorORCID
Schwartz, Moshe0000-0002-1449-0026
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2014 IEEE. Manuscript received October 25, 2013; revised August 14, 2014; accepted October 12, 2014. Date of publication October 28, 2014; date of current version December 22, 2014. This work was supported in part by the U.S.- Israel Binational Science Foundation under Grant 2010075, in part by the National Science Foundation (NSF) under Grant CCF-1218005, in part by the NSF CAREER under Award CCF-0747415, and in part by the NSF under Grant CCF-1217944. This paper was presented at the 2012 IEEE International Symposium on Information Theory.
Group:Parallel and Distributed Systems Group
Funders:
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010075
NSFCCF-1218005
NSFCCF-0747415
NSFCCF-1217944
Subject Keywords:Flash memory, rank modulation, error correcting codes, permutations, metric embeddings, Kendall’s τ -metric, ℓ∞-metric, systematic codes
Issue or Number:1
Record Number:CaltechAUTHORS:20150202-150301749
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20150202-150301749
Official Citation:Hongchao Zhou; Schwartz, M.; Jiang, A.A.; Bruck, J., "Systematic Error-Correcting Codes for Rank Modulation," Information Theory, IEEE Transactions on , vol.61, no.1, pp.17,32, Jan. 2015 doi: 10.1109/TIT.2014.2365499
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:54307
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:04 Feb 2015 00:30
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page