Efficient encoding and decoding algorithm for a class of perfect single-deletion-correcting permutation codes

• DOI: 10.48550/arxiv.2411.08258
• Publication Date: 2024-01-01
• Authors: Gao, Minhan; Shum, Kenneth W.
• Keywords: FOS: Computer and information sciences; Computer Science - Information Theory; Information Theory (cs.IT); FOS: Mathematics; Mathematics - Combinatorics; Combinatorics (math.CO)

A permutation code is a nonlinear code whose codewords are permutation of a set of symbols. We consider the use of permutation code in the deletion channel, and consider the symbol-invariant error model, meaning that the values of the symbols that are not removed are not affected by the deletion. In 1992, Levenshtein gave a construction of perfect single-deletion-correcting permutation codes that attain the maximum code size. Furthermore, he showed in the same paper that the set of all permutations of a given length can be partitioned into permutation codes so constructed. This construction relies on the binary Varshamov-Tenengolts codes. In this paper we give an independent and more direct proof of Levenshtein's result that does not depend on the Varshamov-Tenengolts code. Using the new approach, we devise efficient encoding and decoding algorithms that correct one deletion.<br/>27 pages, 4 figures<br/>