The Taub Faculty of Computer Science Events and Talks

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. In this setup data is represented by permutations in Sn, where Sn is the symmetric group of order n. Error-correction in the rank modulation scheme is done by considering codes in Sn, usually under the Kendall's tau-metric. The Kendall's tau-metric between two permutations is the minimum number of adjacent transpositions required in order to change one to the other. The main challenge in this context is to find lower and upper bounds on the size of a permutation code with minimum Kendall's tau-distance d. One example for such an upper bound is the sphere packing bound. Codes that achieve this bound with equality are called perfect. However, only few trivial perfect codes are known and it is an open problem to determine wheter or not such codes exist. If d is even then a code of minimum distance d cannot be perfect. In this case, diameter perfect codes should be considered. Another challenge is to construct codes that have efficient encoding and decoding algorithms. This motivated the study of systematic codes for permutations. In a systematic permutation code of size k!, every permutation in Sk is a subsequence of exactly one codeword. Oned of the main goals in a systematic error-correcting code for pemutations, is to reduce the number of redundancy symbols. In this talk we study perfect permutation codes under the Kendall's tau-metric and the extended notion of diameter perfect code. We also study systematic permutation codes and present a construction of systematic error-correcting codes in which the number of redundancy symbols is relatively small.