Nonexistence of perfect permutation codes under the Kendall -metric

DOI10.1007/S10623-021-00934-ZzbMATH Open1492.94215arXiv2011.01600OpenAlexW3196492959MaRDI QIDQ2234465FDOQ2234465

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)

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.

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

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

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)

Cites Work

• Rank Modulation for Flash Memories
• Permutation Arrays Under the Chebyshev Distance
• Snake-in-the-Box Codes for Rank Modulation
• Bounds on the Size of Permutation Codes With the Kendall <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>-Metric
• Error-Correction in Flash Memories via Codes in the Ulam Metric
• Metrics on permutations, a survey
• Codes in Permutations and Error Correction for Rank Modulation
• Correcting Charge-Constrained Errors in the Rank-Modulation Scheme
• Snake-in-the-box codes under the \(\ell_{\infty}\)-metric for rank modulation
• Snake-in-the-Box Codes for Rank Modulation Under Kendall’s $\tau $ -Metric
• Constructions of Snake-in-the-Box Codes for Rank Modulation
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
• 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
• Title not available (Why is that?)
• New nonexistence results on perfect permutation codes under the Hamming metric
• Theoretical bounds and constructions of codes in the generalized Cayley metric

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)