New nonexistence results on perfect permutation codes under the hamming metric

Xiang Wang; Wenjuan Yin

doi:10.3934/amc.2021058

Article Contents

2023, Volume 17, Issue 6: 1440-1452. Doi: 10.3934/amc.2021058

This issue Previous Article Rotational analysis of ChaCha permutation Next Article Generic constructions of MDS Euclidean self-dual codes via GRS codes

New nonexistence results on perfect permutation codes under the hamming metric

Xiang Wang^1, and
Wenjuan Yin^2, ,

1.
National Computer Network Emergency Response Technical Team/Coordination, Center of China (CNCERT/CC), Beijing, 100029, China
2.
School of Mathematical Sciences, Tiangong University, Tianjin, 300387, China

^* Corresponding author: Wenjuan Yin
^* Corresponding author: Wenjuan Yin

Received: March 2021

Revised: September 2021

Early access: December 6, 2021

Published online: December 6, 2021

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

Permutation codes under the Hamming metric are interesting topics due to their applications in power line communications and block ciphers. In this paper, we study perfect permutation codes in $ S_n $, the set of all permutations on $ n $ elements, under the Hamming metric. We prove the nonexistence of perfect $ t $-error-correcting codes in $ S_n $ under the Hamming metric, for more values of $ n $ and $ t $. Specifically, we propose 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 Hamming metric for some $ n $ and $ t = 1,2,3,4 $, or $ 2t+1\leq n\leq \max\{4t^2e^{-2+1/t}-2,2t+1\} $ for $ t\geq 2 $, or $ \min\{\frac{e}{2}\sqrt{n+2},\lfloor\frac{n-1}{2}\rfloor\}\leq t\leq \lfloor\frac{n-1}{2}\rfloor $ for $ n\geq 7 $, where $ e $ is the Napier's constant.

Keywords:

Mathematics Subject Classification: Primary: 94A15; Secondary: 68P30.

Citation:

Full Text(HTML)

Table 1. The values of $ (B^n(t),\frac{n!}{(n-t)!}) $ for $ 2\leq t\leq 4 $ and $ n\leq 10 $

$(B^n(t),\frac{n!}{(n-t)!})$	$n=5$	$n=6$	$n=7$	$n=8$	$n=9$	$n=10$
$t=2$	$(11,20)$	$(16,30)$	$(22,42)$	$(29,56)$	$(37,72)$	$(46,90)$
$t=3$	$-$	$-$	$(92,210)$	$(141,336)$	$(205,504)$	$(286,720)$
$t=4$	$-$	$-$	$-$	$-$	$(1339,3024)$	$(2176,5040)$

| Show Table

DownLoad: CSV

Table 2. The values of $ n_0(t) $, $ Un_0(t) $, and $ Ln_0(t) $ for $ 2\leq t\leq 10 $, or $ t = 100,200 $

$t$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$100$	$200$
$n_0(t)$	$5$	$9$	$15$	$22$	$30$	$39$	$49$	$61$	$73$	$5659$	$22181$
$Un_0(t)$	$10.5$	$18.5$	$28.4$	$30.4$	$42.9$	$52.5$	$62.8$	$75.2$	$88.2$	$5819.4$	$22528.4$
$Ln_0(t)$	$5$	$7$	$9.1$	$14.5$	$21.0$	$28.6$	$36.9$	$46.9$	$57.9$	$5465.8$	$21760.2$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Barg and A. Mazumdar, Codes in permutations and error correction for rank modulation, IEEE Trans. Inf. Theory, 56 (2010), 3158-3165. doi: 10.1109/TIT.2010.2048455.
[2]	I. F. Blake, Permutation codes for discrete channels (Corresp.), IEEE Trans. Inform. Theory, 20 (1974), 138-140. doi: 10.1109/TIT.1974.1055142.
[3]	I. F. Blake, Coding with permutations, Information and Control, 43 (1979), 1-19. doi: 10.1016/S0019-9958(79)90076-7.
[4]	S. Buzaglo and T. Etzion, Bounds on the size of permutation codes with the Kendall $\tau$-metric, IEEE Trans. Inf. Theory, 61 (2015), 3241-3250. doi: 10.1109/TIT.2015.2424701.
[5]	W. Chu, C. J. Colbourn and P. Dukes, Constructions for permutation codes in powerline communications, Des. Codes Cryptogr., 32 (2004), 51-64. doi: 10.1023/B:DESI.0000029212.52214.71.
[6]	C. J. Colbourn, T. Kløve and A. C. H. Ling, Permutation arrays for powerline communication and mutually orthogonal Latin squares, IEEE Trans. Inform. Theory, 50 (2004), 1289-1291. doi: 10.1109/TIT.2004.828150.
[7]	D. R. de la Torre, C. J. Colbourn and A. C. H. Ling, An application of permutation arrays to block ciphers, Congr. Numer., 145 (2000), 5-7.
[8]	M. Deza and H. Huang, Metrics on permutations, a survey, J. Combinat. Inf. Syst. Sci., 23 (1998), 173-185.
[9]	M. Deza and S. A. Vanstone, Bounds for permutation arrays, J. Statist. Plann. Inference, 2 (1978), 197-209. doi: 10.1016/0378-3758(78)90008-3.
[10]	C. Ding, F-W. Fu, T. Kløve and V. K.-W. Wei, Constructions of permutation arrays, IEEE Trans. Inf. Theory, 48 (2002), 977-980. doi: 10.1109/18.992812.
[11]	P. Dukes and N. Sawchuck, Bounds on permutation codes of distance four, J. Algebraic Combin., 31 (2010), 143-158. doi: 10.1007/s10801-009-0191-2.
[12]	F. Farnoud, V. Skachek and O. Milenkovic, Error-Correction in flash memories via codes in the Ulam metric, IEEE Trans. Inf. Theory, 59 (2013), 3003-3020. doi: 10.1109/TIT.2013.2239700.
[13]	P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combinatorial Theory, Series A, 22 (1977), 352-360. doi: 10.1016/0097-3165(77)90009-7.
[14]	F.-W. Fu and T. Kløve, Two constructions of permutations arrays, IEEE Trans. Inform. Theory, 50 (2004), 881-883. doi: 10.1109/TIT.2004.826659.
[15]	F. Gao, Y. Yang and G. N. Ge, An improvement on the Gilbert-Varshamov bound for permutation codes, IEEE Trans. Inform. Theory, 59 (2013), 3059-3063. doi: 10.1109/TIT.2013.2237945.
[16]	A. Jiang, M. Schwartz and J. Bruck, Error-correcting codes for rank modulation, Proc. IEEE Int. Symp. Information Theory, (2008), 6-11. doi: 10.1109/ISIT.2008.4595285.
[17]	A. Jiang, M. Schwartz and J. Bruck, Correcting charge-constrained errors in the rank-modulation scheme, IEEE Trans. Inf. Theory, 56 (2010), 2112-2120. doi: 10.1109/TIT.2010.2043764.
[18]	T. Kløve, T. T. Lin, S. C. Tsai and W. G. Tzeng, Permutation arrays under the Chebyshev distance, IEEE Trans. Inf. Theory, 56 (2010), 2611-2617. doi: 10.1109/TIT.2010.2046212.
[19]	J. Kong and M. Hagiwara, Nonexistence of perfect permutation codes in the Ulam metric, Proc. IEEE Int. Symp. Inf. Theory and its Applications, (2016), 691-695.
[20]	R. Montemanni and D. H. Smith, A new table of permutation codes, Des. Codes Cryptogr., 63 (2012), 241-253. doi: 10.1007/s10623-011-9551-8.
[21]	N. Pavlidou, A. J. H. Vinck, J. Yazdani and B. Honary, Power line communications: State of the art and future trends, IEEE Communications Magazine, 41 (2003), 34-40. doi: 10.1109/MCOM.2003.1193972.
[22]	M. Tait, A. Vardy and J. Verstraete, Asymptotic improvement of the Gilbert-Varshamov bound on the size of permutation codes, preprint, arXiv: 1311.4925, 2013.
[23]	H. Tarnanen, Upper bounds on permutation codes via linear programming, European J. Combin., 20 (1999), 101-114. doi: 10.1006/eujc.1998.0272.
[24]	A. J. H. Vinck, Coded modulation for power line communications, In AE Int. J. Electron. and Commun, (2011), 45-49.
[25]	X. Wang and F.-W. Fu, On the snake-in-the-box codes for rank modulation under Kendall's $\tau$-metric, Des. Codes Cryptogr., 83 (2017), 455-465. doi: 10.1007/s10623-016-0239-y.
[26]	X. Wang and F.-W. Fu, Snake-in-the-box codes under the $\ell_{\infty}$-metric for rank modulation, Des. Codes Cryptogr., 88 (2020), 487-503. doi: 10.1007/s10623-019-00693-y.
[27]	X. Wang, Y. J. Wang, W. J. Yin and F-W. Fu, Nonexistence of perfect permutation codes under the Kendall $\tau$-metric, Des. Codes Cryptogr., 89 (2021), 2511-2531. doi: 10.1007/s10623-021-00934-z.
[28]	X. Wang, Y. W. Zhang, Y. T. Yang and G. N. Ge, New bounds of permutation codes under Hamming metric and Kendall's $\tau$-metric, Des. Codes Cryptogr., 85 (2017), 533-545. doi: 10.1007/s10623-016-0321-5.
[29]	Y. Yehezkeally and M. Schwartz, Snake-in-the-box codes for rank modulation, IEEE Trans. Inf. Theory, 58 (2012), 5471-5483. doi: 10.1109/TIT.2012.2196755.
[30]	Y. W. Zhang and G. N. Ge, Snake-in-the-box codes for rank modulation under Kendall's $\tau$-metric, IEEE Trans. Inf. Theory, 62 (2016), 151-158. doi: 10.1109/TIT.2015.2502602.