Perfect permutation codes with the Kendall's τ-metric

Abstract

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile 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's τ-metric. 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 also prove that if such a code exists for n which is not a prime then the code should have some uniform structure. We define some variations of the Kendall's τ-metric and consider the related codes and specifically we prove the existence of a perfect single-error-correcting code in S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sub> . Finally, we examine the existence problem of diameter perfect codes in S <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> and obtain a new upper bound on the size of a code 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's τ-distance.