Nonexistence of perfect permutation codes under the Kendall \(\tau\)-metric. (English) Zbl 1492.94215
Summary: 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 S. Buzaglo and T. Etzion [IEEE Trans. Inf. Theory 61, No. 6, 3241–3250 (2015; Zbl 1359.94784)]. 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\), or \(\frac{5}{8}\dbinom{n}{2} < 2t+1\le\dbinom{n}{2}\).
MSC:
| 94B25 | Combinatorial codes |
| 68P30 | Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) |
Citations:
Zbl 1359.94784Software:
OEISReferences:
| [1] | Barg, A.; Mazumdar, A., Codes in permutations and error correction for rank modulation, IEEE Trans. Inf. Theory, 56, 3158-3165 (2010) · Zbl 1366.94657 · doi:10.1109/TIT.2010.2048455 |
| [2] | Buzaglo, S.; Etzion, T., Bounds on the size of permutation codes with the Kendall \(\tau \)-metric, IEEE Trans. Inf. Theory, 61, 3241-3250 (2015) · Zbl 1359.94784 · doi:10.1109/TIT.2015.2424701 |
| [3] | Deza, M.; Huang, H., Metrics on permutations, a survey, J. Comb. Inf. Syst. Sci., 23, 173-185 (1998) · Zbl 1217.05038 |
| [4] | Farnoud, F.; Skachek, V.; Milenkovic, O., Error-correction in falsh memories via codes in the Ulam metric, IEEE Trans. Inf. Theory, 59, 3003-3020 (2013) · Zbl 1364.94711 · doi:10.1109/TIT.2013.2239700 |
| [5] | Gerschgorin, S., Uber die abgrenzung der eigenwerte einer matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk., 7, 749-754 (1931) · JFM 57.1340.06 |
| [6] | Horvitz, M.; Etzion, T., Constructions of snake-in-the-box codes for rank modulation, IEEE Trans. Inf. Theory, 60, 7016-7025 (2014) · Zbl 1360.94376 · doi:10.1109/TIT.2014.2359193 |
| [7] | Jiang, A.; Mateescu, R.; Schwartz, M.; Bruck, J., Rank modulation for flash memories, IEEE Trans. Inf. Theory, 55, 2659-2673 (2009) · Zbl 1367.94121 · doi:10.1109/TIT.2009.2018336 |
| [8] | Jiang, A.; Schwartz, M.; Bruck, J., Correcting charge-constrained errors in the rank-modulation scheme, IEEE Trans. Inf. Theory, 56, 2112-2120 (2010) · Zbl 1366.94767 · doi:10.1109/TIT.2010.2043764 |
| [9] | Kløve, T.; Lin, TT; Tsai, SC; Tzeng, WG, Permutation arrays under the Chebyshev distance, IEEE Trans. Inf. Theory, 56, 2611-2617 (2010) · Zbl 1366.94761 · doi:10.1109/TIT.2010.2046212 |
| [10] | Sloane N.J.A.: The On-Line Encyclopedia of Integer Sequences. \(A008302\). Triangle of Mahonian numbers \(T(n,k)\). |
| [11] | Vijayakumaran, S., Largest permutation codes with the Kendall \(\tau \)-metric in \(S_5\) and \(S_6\), IEEE Commun. Lett., 20, 1912-1915 (2016) · doi:10.1109/LCOMM.2016.2591003 |
| [12] | Wang, X.; Fu, F-W, On the snake-in-the-box codes for rank modulation under Kendall’s \(\tau \)-metric, Des. Codes Cryptogr., 83, 455-465 (2017) · Zbl 1364.68190 · doi:10.1007/s10623-016-0239-y |
| [13] | Wang, X.; Fu, F-W, Snake-in-the-box codes under the \(\ell_{\infty }\)-metric for rank modulation, Des. Codes Cryptogr., 88, 487-503 (2020) · Zbl 1429.68071 · doi:10.1007/s10623-019-00693-y |
| [14] | Wang, X.; Zhang, YW; Yang, YT; Ge, GN, New bounds of permutation codes under Hamming metric and Kendall’s \(\tau \)-metric, Des. Codes Cryptogr., 85, 533-545 (2017) · Zbl 1417.94117 · doi:10.1007/s10623-016-0321-5 |
| [15] | Yehezkeally, Y.; Schwartz, M., Snake-in-the-box codes for rank modulation, IEEE Trans. Inf. Theory, 58, 5471-5483 (2012) · Zbl 1364.94648 · doi:10.1109/TIT.2012.2196755 |
| [16] | Zhang, YW; Ge, GN, Snake-in-the-box codes for rank modulation under Kendall’s \(\tau \)-metric, IEEE Trans. Inf. Theory, 62, 151-158 (2016) · Zbl 1359.94918 · doi:10.1109/TIT.2015.2502602 |
| [17] | Zhou H., Jiang A., Bruck J.: Systematic error-correcting codes for rank modulation. In: Proceedings on IEEE International Symposium in Information Theory, pp. 2978-2982 (2012). |
| [18] | Zhou, H.; Schwartz, M.; Jiang, A.; Bruck, J., Systematic error-correcting codes for rank modulation, IEEE Trans. Inf. Theory, 61, 17-32 (2015) · Zbl 1359.94878 · doi:10.1109/TIT.2014.2365499 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
