Codes in permutations and error correction for rank modulation

Alexander Barg, Arya Mazumdar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of n elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of n. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages854-858
Number of pages5
DOIs
StatePublished - Aug 23 2010
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8103

Other

Other2010 IEEE International Symposium on Information Theory, ISIT 2010
CountryUnited States
CityAustin, TX
Period6/13/106/18/10

Fingerprint Dive into the research topics of 'Codes in permutations and error correction for rank modulation'. Together they form a unique fingerprint.

  • Cite this

    Barg, A., & Mazumdar, A. (2010). Codes in permutations and error correction for rank modulation. In 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings (pp. 854-858). [5513604] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2010.5513604