Optimal Permutation Codes and the Kendall's \(\tau\)-Metric

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_n\), using the Kendall's \(\tau\)-metric. We will consider either optimal codes such as perfect codes or concepts related to optimal codes. We prove that there are no perfect single-error-correcting codes in \(S_n\), where \(n>4\) is a prime or \(4\leq n\leq 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 consider optimal anticodes and diameter perfect codes in \(S_n\). As a consequence we obtain a new upper bound on the size of a code in \(S_n\) with even minimum Kendall's \(\tau\)-distance. We define some variations of the Kendall's \(\tau\)-metric and consider the related codes. Specifically, we present perfect single-error-correcting codes in \(S_5\) for these variations. Furthermore, using these variations we present larger codes than the known ones in \(S_5\) and \(S_7\) with the Kendall's \(\tau\)-metric. These codes have a large automorphism group.