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
    0 references
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references