Improved Bounds on the Size of Permutation Codes Under Kendall τ-Metric

Abstract

In order to overcome the challenges caused by flash memories and also to protect against errors related to reading information stored in DNA molecules in the shotgun sequencing method, the rank modulation method has been proposed. In the rank modulation framework, codewords are permutations. In this paper, we study the largest size P(n, d) of permutation codes of length n, i.e., subsets of the set Sn of all permutations on {1, . . . , n} with the minimum distance at least d ∈ {1, . . . ,(Formula presented)} under the Kendall τ-metric. By presenting an algorithm and two theorems, we improve the known lower and upper bounds for P(n,d) . In particular, we show that P(n,d)=4 for all n ≥ 6 and (Formula presented) (Formula presented) < d ≤ (Formula presented) (Formula presented) . Additionally, we prove that for any prime number n and integer r ≤ − (Formula presented) , P(n,3) ≤ (n-1)! (Formula presented) (Formula presented) . This result greatly improves the upper bound of P(n,3) for all primes n ≥ 37 . © 1963-2012 IEEE.