American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021058
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  March 2021 Revised  September 2021 Early access December 2021

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: Perfect codes, Hamming metric, permutation codes.
Mathematics Subject Classification: Primary: 94A15; Secondary: 68P30.
Citation: Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, doi: 10.3934/amc.2021058
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.  Google Scholar

[2]

I. F. Blake, Permutation codes for discrete channels (Corresp.), IEEE Trans. Inform. Theory, 20 (1974), 138-140.  doi: 10.1109/TIT.1974.1055142.  Google Scholar

[3]

I. F. Blake, Coding with permutations, Information and Control, 43 (1979), 1-19.  doi: 10.1016/S0019-9958(79)90076-7.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

M. Deza and H. Huang, Metrics on permutations, a survey, J. Combinat. Inf. Syst. Sci., 23 (1998), 173-185.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[23]

H. Tarnanen, Upper bounds on permutation codes via linear programming, European J. Combin., 20 (1999), 101-114.  doi: 10.1006/eujc.1998.0272.  Google Scholar

[24]

A. J. H. Vinck, Coded modulation for power line communications, In AE Int. J. Electron. and Commun, (2011), 45-49. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[2]

I. F. Blake, Permutation codes for discrete channels (Corresp.), IEEE Trans. Inform. Theory, 20 (1974), 138-140.  doi: 10.1109/TIT.1974.1055142.  Google Scholar

[3]

I. F. Blake, Coding with permutations, Information and Control, 43 (1979), 1-19.  doi: 10.1016/S0019-9958(79)90076-7.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

M. Deza and H. Huang, Metrics on permutations, a survey, J. Combinat. Inf. Syst. Sci., 23 (1998), 173-185.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[23]

H. Tarnanen, Upper bounds on permutation codes via linear programming, European J. Combin., 20 (1999), 101-114.  doi: 10.1006/eujc.1998.0272.  Google Scholar

[24]

A. J. H. Vinck, Coded modulation for power line communications, In AE Int. J. Electron. and Commun, (2011), 45-49. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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)$
Table Options

Download as excel

$(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)$
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$
Table Options

Download as excel

$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$
[1]

B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[2]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[3]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223
[4]

Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061
[5]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[6]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[7]

Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[8]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465
[9]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[10]

Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385
[11]

Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006
[12]

Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013
[13]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295
[14]

Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149
[15]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425
[16]

Maura B. Paterson, Douglas R. Stinson. Splitting authentication codes with perfect secrecy: New results, constructions and connections with algebraic manipulation detection codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021054
[17]

David Keyes. $\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity. Advances in Mathematics of Communications, 2012, 6 (4) : 401-418. doi: 10.3934/amc.2012.6.401
[18]

Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[19]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373
[20]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (85)
  • HTML views (58)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy