New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric (Q6086190)
From MaRDI portal
scientific article; zbMATH DE number 7763217
Language | Label | Description | Also known as |
---|---|---|---|
English | New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric |
scientific article; zbMATH DE number 7763217 |
Statements
New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric (English)
0 references
9 November 2023
0 references
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.
0 references
rank modulation
0 references
Kendall \(\tau\)-metric
0 references
permutation codes
0 references