2013/10/21 by Sarit Buzaglo, Tuvi Etzion, Buzaglo, Sarit +1
Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1310.5515
openalex publication_date 2013/10/21 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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, Sn, using the Kendall's τ-metric. We prove that there are no perfect single-error-correcting codes in Sn, 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 S5. Finally, we examine the existence problem of diameter perfect codes in Sn and obtain a new upper bound on the size of a code in Sn with even minimum Kendall's τ-distance.