A Caltech Library Service

Codes Correcting Erasures and Deletions for Rank Modulation

Gabrys, Ryan and Yaakobi, Eitan and Farnoud (Hassanzadeh), Farzad and Sala, Frederic and Bruck, Jehoshua and Dolecek, Lara (2016) Codes Correcting Erasures and Deletions for Rank Modulation. IEEE Transactions on Information Theory, 62 (1). pp. 136-150. ISSN 0018-9448. doi:10.1109/TIT.2015.2493147.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall τ, Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results.

Item Type:Article
Related URLs:
URLURL TypeDescription
Yaakobi, Eitan0000-0002-9851-5234
Farnoud (Hassanzadeh), Farzad0000-0002-8684-4487
Bruck, Jehoshua0000-0001-8474-0812
Dolecek, Lara0000-0003-3736-4345
Additional Information:© 2016 IEEE. Manuscript received June 2, 2015; accepted September 21, 2015. Date of publication October 26, 2015; date of current version December 18, 2015. Communicated by M. Schwartz, Associate Editor for Coding Techniques. This paper was presented at the IEEE International Symposium on Information Theory in 2014 [6] and [7]. This work was supported in part by the U.S.–Israel Binational Science Foundation, Jerusalem, Israel, under Grant 2010075, the Smart Scholarship, NSF under Grant CCF-1029030, Grant CCF-1150212, and Grant CIF-1218005, the NISE Program at SSC Pacific, NSF GRFP, and Intellectual Ventures. The authors thank two anonymous reviewers and the Associate Editor Prof. Moshe Schwartz for their valuable comments and suggestions.
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2010075
Smart ScholarshipUNSPECIFIED
NSF Graduate Research FellowshipUNSPECIFIED
Intellectual VenturesUNSPECIFIED
Subject Keywords:Coding theory, flash memories, rank modulation codes, permutation codes, deletion codes
Issue or Number:1
Record Number:CaltechAUTHORS:20160225-140310853
Persistent URL:
Official Citation:R. Gabrys, E. Yaakobi, F. Farnoud, F. Sala, J. Bruck and L. Dolecek, "Codes Correcting Erasures and Deletions for Rank Modulation," in IEEE Transactions on Information Theory, vol. 62, no. 1, pp. 136-150, Jan. 2016. doi: 10.1109/TIT.2015.2493147
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:64770
Deposited By: Tony Diaz
Deposited On:25 Feb 2016 22:16
Last Modified:10 Nov 2021 23:35

Repository Staff Only: item control page