Nonexistence of perfect permutation codes under the Kendall $$\tau $$-metric
| Autor: | Xiang Wang, Fang-Wei Fu, Yuanjie Wang, Wenjuan Yin |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Polynomial (hyperelastic model)
Code (set theory) Hardware_MEMORYSTRUCTURES Mathematics::Combinatorics Hamming bound Computer Science - Information Theory Applied Mathematics Open problem Computer Science Applications Combinatorics Permutation Metric (mathematics) Rank (graph theory) Ball (mathematics) Mathematics |
| Zdroj: | Designs, Codes and Cryptography. 89:2511-2531 |
| ISSN: | 1573-7586 0925-1022 |
| DOI: | 10.1007/s10623-021-00934-z |
| Popis: | In the rank modulation scheme for flash memories, permutation codes have been studied. In this paper, we study perfect permutation codes in $$S_n$$ , the set of all permutations on n elements, under the Kendall $$\tau $$ -metric. We answer one open problem proposed by Buzaglo and Etzion. That is, proving the nonexistence of perfect codes in $$S_n$$ , under the Kendall $$\tau $$ -metric, for more values of n. Specifically, we present the polynomial representation of the size of a ball in $$S_n$$ under the Kendall $$\tau $$ -metric for some radius r, and obtain some sufficient conditions of the nonexistence of perfect permutation codes. Further, we prove that there does not exist a perfect t-error-correcting code in $$S_n$$ under the Kendall $$\tau $$ -metric for some n and $$t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink