Codes in Permutations and Error Correction for Rank Modulation

DOI10.1109/TIT.2010.2048455zbMATH Open1366.94657arXiv0908.4094OpenAlexW2128970384MaRDI QIDQ5281383FDOQ5281383

Authors: Alexander Barg, Arya Mazumdar 

Publication date: 27 July 2017

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

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.

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)

Cited In (25)

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

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)