Bounds on the Size of Permutation Codes With the Kendall <inline-formula> <tex-math notation="LaTeX">$\tau $ </tex-math></inline-formula>-Metric

Abstract

The rank modulation scheme has been proposed for efficient writing and storing data in nonvolatile memory storage. Error correction in the rank modulation scheme is done by considering permutation codes. In this paper, we consider codes in the set of all permutations on n elements, S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> , using the Kendall τ-metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose, we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall τ-metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> , where n>4 is a prime or 4≤n≤10 . We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence, we obtain a new upper bound on the size of codes in S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> with even minimum Kendall τ-distance. We present larger single-error-correcting codes than the known ones in S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sub> and S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">7</sub> .