TY - JOUR

T1 - Constructions of rank modulation codes

AU - Mazumdar, Arya

AU - Barg, Alexander

AU - Zemor, Gilles

PY - 2013

Y1 - 2013

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. As our main set of results, we present several general constructions of codes in permutations that cover a broad range of code parameters. In particular, we show a number of ways in which conventional error-correcting codes can be modified to correct errors in the Kendall space. Our constructions are nonasymptotic and afford simple encoding and decoding algorithms of essentially the same complexity as required to correct errors in the Hamming metric. As an example, from binary Bose-Chaudhuri-Hocquenghem codes, we obtain codes correcting t Kendall errors in n memory cells that support the order of n!/(\log{2}n!)t messages, for any constant t=1,2,\ldots. We give many examples of rank modulation codes with specific parameters. Turning to asymptotic analysis, we construct families of rank modulation codes that correct a number of errors that grows with n at varying rates, from \Theta (n) to \Theta (n{2}). One of our constructions gives rise to a family of rank modulation codes for which the tradeoff between the number of messages and the number of correctable Kendall errors approaches the optimal scaling rate.

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. As our main set of results, we present several general constructions of codes in permutations that cover a broad range of code parameters. In particular, we show a number of ways in which conventional error-correcting codes can be modified to correct errors in the Kendall space. Our constructions are nonasymptotic and afford simple encoding and decoding algorithms of essentially the same complexity as required to correct errors in the Hamming metric. As an example, from binary Bose-Chaudhuri-Hocquenghem codes, we obtain codes correcting t Kendall errors in n memory cells that support the order of n!/(\log{2}n!)t messages, for any constant t=1,2,\ldots. We give many examples of rank modulation codes with specific parameters. Turning to asymptotic analysis, we construct families of rank modulation codes that correct a number of errors that grows with n at varying rates, from \Theta (n) to \Theta (n{2}). One of our constructions gives rise to a family of rank modulation codes for which the tradeoff between the number of messages and the number of correctable Kendall errors approaches the optimal scaling rate.

KW - Codes in permutations

KW - Gray map

KW - Kendall tau distance

KW - flash memory

KW - rank modulation

KW - transpositions

UR - http://www.scopus.com/inward/record.url?scp=84872584607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84872584607&partnerID=8YFLogxK

U2 - 10.1109/TIT.2012.2221121

DO - 10.1109/TIT.2012.2221121

M3 - Article

AN - SCOPUS:84872584607

SN - 0018-9448

VL - 59

SP - 1018

EP - 1029

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 2

M1 - 6317187

ER -