Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2016 | public
Journal Article

Codes Correcting Erasures and Deletions for Rank Modulation

Abstract

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.

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.

Additional details

Created:
August 20, 2023
Modified:
October 17, 2023