Codes in Permutations and Error Correction for Rank Modulation

DOI10.1109/TIT.2010.2048455MaRDI QIDQ5281383zbMATHOpenAlexFDO

Authors Alexander Barg, Arya Mazumdar

Publication date 27 July 2017

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

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

Mathematics Subject Classification ID

Combinatorial codes (94B25) Bounds on codes (94B65) Modulation and demodulation in information and communication theory (94A14)

Abstract: Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of $n$ elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of $n$. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.

Cited in

(25)

• Constructions for permutation codes in powerline communications
• Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Codes in the Space of Multisets—Coding for Permutation Channels With Impairments
• A note on permutation modulation
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric
• Optimal permutation anticodes with the infinity norm via permanents of \((0,1)\)-matrices
• A coding scheme for m-out-of-n codes
• Sorting on graphs by adjacent swaps using permutation groups
• New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric
• Coding for locality in reconstructing permutations
• Rank error-correcting pairs
• Metrics on permutations with the same peak set
• Voting rules as error-correcting codes
• Generation, Ranking and Unranking of Permutations based on the Mixed-Radix Codes
• Consolidation for compact constraints and Kendall tau LP decodable permutation codes
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Proof of a conjecture of Kløve on permutation codes under the Chebychev distance
• On the Capacity of Constrained Permutation Codes for Rank Modulation
• New nonexistence results on perfect permutation codes under the Hamming metric
• Modified order and stepsize strategies in Adams codes
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• Restriction conditions on \(\mathrm{PL}(7, 2)\) codes \((3 \le \vert\mathcal{G}_i\vert \le 7)\)
• Maximum-rank array codes and their application to crisscross error correction
• On maximum Lee distance codes

This page was built for publication: Codes in Permutations and Error Correction for Rank Modulation

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