Constructions of Rank Modulation Codes

DOI10.1109/TIT.2012.2221121MaRDI QIDQ2989421zbMATHOpenAlexFDO

Authors Arya Mazumdar, Alexander Barg, Gilles Zémor

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.2557

Mathematics Subject Classification ID

Other types of codes (94B60) Modulation and demodulation in information and communication theory (94A14)

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 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!/(lo{g}_{2}n!{)}^t$ messages, for any constant $t=1,2,\mathrm{...}$ 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.

Cited in

(5)

• Snake-in-the-Box Codes for Rank Modulation
• Optimal Permutation Recovery in Permuted Monotone Matrix Model
• Consolidation for compact constraints and Kendall tau LP decodable permutation codes
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• On the Capacity of Constrained Permutation Codes for Rank Modulation

This page was built for publication: Constructions of Rank Modulation Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989421)