\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

New nonexistence results on perfect permutation codes under the hamming metric

  • * Corresponding author: Wenjuan Yin

    * Corresponding author: Wenjuan Yin
Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
  • [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. ChuC. 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. ColbournT. 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 TorreC. 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. DingF-W. FuT. 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. FarnoudV. 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. GaoY. 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. JiangM. 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øveT. T. LinS. 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. PavlidouA. J. H. VinckJ. 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. WangY. J. WangW. 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. WangY. W. ZhangY. 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.
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(4178) PDF downloads(663) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return