TY - GEN
T1 - Constructions of rank modulation codes
AU - Mazumdar, Arya
AU - Barg, Alexander
AU - Zémor, Gilles
PY - 2011
Y1 - 2011
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=80054820464&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80054820464&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2011.6034261
DO - 10.1109/ISIT.2011.6034261
M3 - Conference contribution
AN - SCOPUS:80054820464
SN - 9781457705953
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 869
EP - 873
BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Y2 - 31 July 2011 through 5 August 2011
ER -