New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric
type: Item
instance of: scholarly article
title: New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric
author: Alireza Abdollahi
author: Javad Bagherian
author: Fatemeh Jafari
author: M. Khatami
author: F. Parvaresh
author: Reza Sobhani
published in: Cryptography and Communications
publication date: 2023-11-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/2303.02349
review text: The Kendall \(\tau\)-distance plays an important role in understanding the performance of specific codes used in flash memory storage. More precisely, for any two permutations \(\rho\) and \(\pi\), their \(\tau\)-distance is the minimum number of adjacent transpositions needed to write \(\rho \pi^{-1}\) as their product. A permutation code with minimum \(\tau\)-distance \(d\) can correct up to \(\frac{d-1}{2}\) errors caused by charge-constrained errors (occurring in flash memories). In this interesting paper the authors advances significantly current knowledge on these codes, thanks mainly to the following two results: \begin{itemize} \item[2.1] (existence of optimal codes) if \(d\) is such that graphical codes of minimum distance at least \(d\) exist, then those with minimum distance exactly \(d\) do exist. \item[1.1] (bounds on the size of optimal codes with \(\tau\)-distance \(d\) and length \(n\)) For all primes \(p\geq 11\), \[ P( p, 3)\leq (p-1)!-\frac{p}{3}+2\leq (p-1)!-2 \] \end{itemize} Some computational experiments complete the paper.
reviewed by: Massimiliano Sala
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 94B65
Mathematics Subject Classification ID: 68P30
zbMATH DE Number: 7763217
zbMATH Keywords: rank modulation
zbMATH Keywords: Kendall \(\tau\)-metric
zbMATH Keywords: permutation codes
MaRDI profile type: MaRDI publication profile
cites work: Codes in Permutations and Error Correction for Rank Modulation
cites work: Bounds on the Size of Permutation Codes With the Kendall $\tau $ -Metric
cites work: Codes, transforms and the spectrum of the symmetric group
cites work: Q3952291
cites work: Correcting Charge-Constrained Errors in the Rank-Modulation Scheme
cites work: Upper bounds on permutation codes via linear programming
cites work: New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
cites work: Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
DOI: 10.1007/S12095-023-00642-6
Recommended article: New upper bounds for the size of permutation codes via linear programming
Recommended article: New bounds of permutation codes under Hamming metric and Kendall's \(\tau \)-metric
Recommended article: Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric
Recommended article: Upper bounds on permutation codes via linear programming
Recommended article: Bounds on permutation codes of distance four
description: scientific article; zbMATH DE number 7763217