Efficient encoding and decoding algorithm for a class of perfect single-deletion-correcting permutation codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913576840593408 |
|---|---|
| author | Gao, Minhan Shum, Kenneth W. |
| author_facet | Gao, Minhan Shum, Kenneth W. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08258 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient encoding and decoding algorithm for a class of perfect single-deletion-correcting permutation codes Gao, Minhan Shum, Kenneth W. Information Theory Combinatorics 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. |
| title | Efficient encoding and decoding algorithm for a class of perfect single-deletion-correcting permutation codes |
| topic | Information Theory Combinatorics |
| url | https://arxiv.org/abs/2411.08258 |