Name
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. 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TIT.2012.2221121 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
hamming codes,decoding,error correction codes,modulation coding,bose-chaudhuri-hocquenghem code,hamming metric,kendall tau distance,asymptotic analysis,decoding algorithm,encoding information,error-correcting code,flash memory devices,impulse noise,optimal scaling rate,parameter coding,rank modulation code,transmission line,codes in permutations,gray map,flash memory,rank modulation,transpositions | Hamming code,Discrete mathematics,Combinatorics,Concatenated error correction code,Block code,Kendall tau distance,Hamming distance,Raptor code,Linear code,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
59 | 2 | 0018-9448 |
Citations | PageRank | References |
21 | 1.09 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arya Mazumdar | 1 | 307 | 41.81 |
| Alexander Barg | 2 | 910 | 85.90 |
| G. Zemor | 3 | 232 | 16.71 |