Constructions of rank modulation codes

Arya Mazumdar, Alexander Barg, Gilles Zémor

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

11 Scopus citations

Abstract

Rank modulation is a way of encoding information to correct errors in flash memory devices as well as impulse noise in transmission lines. Modeling rank modulation involves construction of packings of the space of permutations equipped with the Kendall tau distance. We present several general constructions of codes in permutations that cover a broad range of code parameters. In particular, we show that a code that corrects Hamming errors can be used to construct a code for correcting Kendall errors. For instance, from BCH codes we obtain codes correcting t Kendall errors in n memory cells that support the order of n!/ logt n! messages, for any τ = 1, 2,⋯ We also construct families of codes that correct a number of errors that grows with n at varying rates, from (n) to Θ(n2).

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages869-873
Number of pages5
DOIs
StatePublished - 2011
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Publication series

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

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
CountryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

Fingerprint Dive into the research topics of 'Constructions of rank modulation codes'. Together they form a unique fingerprint.

Cite this