Computer Science – Information Theory
Scientific paper
2011-10-12
Computer Science
Information Theory
Submitted to IEEE Transactions on Information Theory
Scientific paper
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 a number of ways in which conventional error-correcting codes can be modified to correct errors in the Kendall space. Codes that we construct afford simple encoding and decoding algorithms of essentially the same complexity as required to correct errors in the Hamming metric. For instance, from binary BCH codes we obtain codes correcting $t$ Kendall errors in $n$ memory cells that support the order of $n!/(\log_2n!)^t$ messages, for any constant $t= 1,2,...$ We also construct families of 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 trade-off between the number of messages and the number of correctable Kendall errors approaches the optimal scaling rate. Finally, we list a number of possibilities for constructing codes of finite length, and give examples of rank modulation codes with specific parameters.
Barg Alexander
Mazumdar Arya
Zemor Gilles
No associations
LandOfFree
Constructions of Rank Modulation Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constructions of Rank Modulation Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructions of Rank Modulation Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-632610