Nonexistence of perfect permutation codes under the Kendall -metric

DOI10.1007/S10623-021-00934-ZMaRDI QIDQ2234465zbMATH OpenOpenAlexFDO

Authors Xiang Wang, Yuanjie Wang, Wenjuan Yin, Fangwei Fu

Publication date 19 October 2021

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

perfect codespermutation codesflash memoryKendall \(\tau\)-metric

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorial codes (94B25)

Abstract: In the rank modulation scheme for flash memories, permutation codes have been studied. In this paper, we study perfect permutation codes in $S_n$, the set of all permutations on $n$ elements, under the Kendall au-Metric. We answer one open problem proposed by Buzaglo and Etzion. That is, proving the nonexistence of perfect codes in $S_n$, under the Kendall au-metric, for more values of $n$. Specifically, we present the recursive formulas for the size of a ball with radius $r$ in $S_n$ under the Kendall au-metric. Further, We prove that there are no perfect $t$-error-correcting codes in $S_n$ under the Kendall $au$-metric for some $n$ and $t$=2,3,4,or 5.

Recommendations

• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• New theoretical bounds and constructions of permutation codes under block permutation metric
• Permutation codes with specified packing radius
• A bound on permutation codes

Cites work

• Bounds on the Size of Permutation Codes With the Kendall <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>-Metric
• Codes in Permutations and Error Correction for Rank Modulation
• Constructions of Snake-in-the-Box Codes for Rank Modulation
• Correcting Charge-Constrained Errors in the Rank-Modulation Scheme
• Error-Correction in Flash Memories via Codes in the Ulam Metric
• Metrics on permutations, a survey
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• Permutation Arrays Under the Chebyshev Distance
• Rank Modulation for Flash Memories
• Snake-in-the-Box Codes for Rank Modulation
• Snake-in-the-Box Codes for Rank Modulation Under Kendall’s $\tau $ -Metric
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Systematic Error-Correcting Codes for Rank Modulation

Cited in

(8)

• Reconstruction of permutations distorted by single Kendall \(\tau\)-errors
• New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric
• Consolidation for compact constraints and Kendall tau LP decodable permutation codes
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• Nonexistence of perfect permutation codes under the $$\ell _{\infty }$$-metric
• scientific article; zbMATH DE number 1021808 (Why is no real title available?)
• New nonexistence results on perfect permutation codes under the Hamming metric
• Theoretical bounds and constructions of codes in the generalized Cayley metric

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric

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