On the Labeling Problem of Permutation Group Codes Under the Infinity Metric

DOI10.1109/TIT.2012.2204035zbMATH Open1364.94686arXiv1102.2702OpenAlexW2024722282WikidataQ59902907 ScholiaQ59902907MaRDI QIDQ2989749FDOQ2989749

Authors: Itzhak Tamo, Moshe Schwartz 

Publication date: 8 June 2017

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

Abstract: Codes over permutations under the infinity norm have been recently suggested as a coding scheme for correcting limited-magnitude errors in the rank modulation scheme. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding/decoding procedures, and then optimize the code's minimal distance via relabeling. We formally define the relabeling problem, and show that all codes may be relabeled to get a minimal distance at most 2. The decision problem of whether a code may be relabeled to distance 1 is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved hard to approximate. Finally, we consider general bounds on the relabeling problem. We specifically show the optimal relabeling distance of cyclic groups. A specific case of a general probabilistic argument is used to show $agl(p)$ may be relabeled to a minimal distance of $p-O(sqrtplnp)$.

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

Mathematics Subject Classification ID

Combinatorial codes (94B25) Bounds on codes (94B65)

Cited In (3)

• Covering radius of permutation groups with infinity-norm
• Equidistant permutation group codes
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric

This page was built for publication: On the Labeling Problem of Permutation Group Codes Under the Infinity Metric

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