Constructions of Rank Modulation Codes

DOI10.1109/TIT.2012.2221121zbMATH Open1364.94197arXiv1110.2557OpenAlexW2005913625MaRDI QIDQ2989421FDOQ2989421

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)

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.

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)

Cited In (5)

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

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)