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

On the minimum number of minimal codewords

  • * Corresponding author

    * Corresponding author 

The work of R. dela Cruz is supported by the Georg Forster Research Fellowship of the Alexander von Humboldt Foundation

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by
  • We study the minimum number of minimal codewords in linear codes using techniques from projective geometry. Minimal codewords have been used in decoding algorithms and cryptographic protocols. First, we derive a new lower bound on the number of minimal codewords. Then we give a formula for the minimum number of minimal codewords of linear codes for certain lengths and dimensions. We also determine the exact value of the minimum for a range of values of the length and dimension. As an application, we completed a table of the minimum number of minimal codewords for codes of length up to $ 15 $. Finally, we discuss an extension of the geometric approach to minimal subcode supports.

    Mathematics Subject Classification: Primary: 94B05, 94B27; Secondary: 94A60, 94B35.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  $ m_2(n,k) $ for $ 3\leq n\leq 15, 1\leq k\leq 9 $

    $ n/k $ 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    3 3 3
    4 4 4
    5 6 5 5
    6 7 6 6 6
    7 7 8 7 7 7
    8 8 9 8 8 8
    9 12 9 9 9 9 9
    10 14 10 10 10 10 10 10
    11 14 15 11 11 11 11 11 11
    12 15 15 13 12 12 12 12 12 12
    13 15 16 14 13 13 13 13 13 13 13
    14 15 16 14 15 14 14 14 14 14 14 14
    15 15 16 17 15 16 15 15 15 15 15 15 15
     | Show Table
    DownLoad: CSV
  • [1] E. Agrell, Voronoi Regions for binary linear block codes, IEEE Transactions on Information Theory, 42 (1996), 310-316.  doi: 10.1109/18.481810.
    [2] E. Agrell, On the Voronoi neighbor ratio for binary linear codes, IEEE Transactions on Information Theory, 44 (1998), 3064-3072.  doi: 10.1109/18.737535.
    [3] A. AlahmadiR. E. L. AldredR. dela CruzS. OkP. Solé and C. Thomassen, The minimum number of minimal codewords in an $[n, k]$-code and in graphic codes, Discrete Applied Mathematics, 184 (2015), 32-39.  doi: 10.1016/j.dam.2014.11.015.
    [4] A. AlahmadiR. E. L. AldredR. dela CruzP. Solé and C. Thomassen, The maximum number of minimal codewords in an $[n, k]$-code, Discrete Mathematics, 313 (2013), 1569-1574.  doi: 10.1016/j.disc.2013.03.023.
    [5] A. AlahmadiR. E. L. AldredR. dela CruzP. Solé and C. Thomassen, The maximum number of minimal codewords in long codes, Discrete Applied Mathematics, 161 (2013), 424-429.  doi: 10.1016/j.dam.2012.09.009.
    [6] G. N. Alfarano, M. Borello and A. Neri, A geometric characterization of minimal codes and their asymptotic performance, Advances in Mathematics of Communications, (2020). doi: 10.3934/amc.2020104.
    [7] A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Transactions on Information Theory, 44 (1998), 2010-2017.  doi: 10.1109/18.705584.
    [8] M. Bonini and M. Borello, Minimal linear codes arising from blocking sets, Journal of Algebraic Combinatorics, (2020). doi: 10.1007/s10801-019-00930-6.
    [9] Y. Borissov and N. Manev, Minimal codewords in linear codes, Serdica Mathematical Journal, 30 (2004), 303-324. 
    [10] T. Britz, Higher support matroids, Discrete Mathematics, 307 (2007), 2300-2308.  doi: 10.1016/j.disc.2006.12.001.
    [11] H. Chabanne, G. Cohen and A. Patey, Towards secure two-party computation from the wire-tap channel, in Proc. Information Security and Cryptology ICISC 2013, Lecture Notes in Comput. Sci., Vol. 8565, Springer, Cham, 2014, 34–46. doi: 10.1007/978-3-319-12160-4_3.
    [12] C. DingD. Kohel and S. Ling, Secret-sharing with a class of ternary codes, Theoretical Computer Science, 246 (2000), 285-298.  doi: 10.1016/S0304-3975(00)00207-3.
    [13] C. Ding and J. Yuan, Covering and secret sharing with linear codes, in Proc. 4th Int. Conf. on Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Comput. Sci., vol. 2731, Springer, Berlin, 2003, 11–25. doi: 10.1007/3-540-45066-1_2.
    [14] G. Y. DosaI. Szalkai and C. Laflamme, The maximum and minimum number of circuits and bases of matroids, Pure Mathematics and Applications, 15 (2006), 383-392. 
    [15] R. Entringer and P. Slater, On the maximum number of cycles in a graph, Ars Combinatoria, 11 (1981), 289-294. 
    [16] J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, Journal of Statistical Planning and Inference, 72 (1998), 355-380.  doi: 10.1016/S0378-3758(98)00043-3.
    [17] T.-Y. Hwang, Decoding linear block codes for minimizing word error rate, IEEE Transactions on Information Theory, 25 (1979), 733-737.  doi: 10.1109/TIT.1979.1056120.
    [18] R. Jurrius, Weight enumeration of codes from finite spaces, Designs, Codes and Cryptography, 63 (2012), 321-330.  doi: 10.1007/s10623-011-9557-2.
    [19] N. Kashyap, On the convex geometry of binary linear codes, preprint, (2006).
    [20] S. Kurz, LinCode - Computer Classification Of Linear Codes, preprint, (2019), arXiv: 1912.09357.
    [21] W. Lu, X. Wu and X. Cao, The Parameters of Minimal Linear Codes, preprint, (2019), arXiv: 1911.07648.
    [22] J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Workshop Inf. Theory, Sweden, (1993), 276–279.
    [23] J. SchillewaertL. Storme and J. A. Thas, Minimal codewords in Reed-Muller codes, Designs, Codes and Cryptography, 54 (2010), 273-286.  doi: 10.1007/s10623-009-9323-x.
    [24] C. Tang, Y. Qiu, Q. Liao, and Z. Zhou, Full Characterization of Minimal Linear Codes as Cutting Blocking Sets, preprint, (2020), arXiv: 1911.09867.
    [25] M. Tsfasman and S. Vladut, Geometric approach to higher weights, IEEE Transactions on Information Theory, 41 (1995), 1564-1588.  doi: 10.1109/18.476213.
    [26] V. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259.
    [27] K. Yasunaga and T. Fujiwara, Determination of the local weight distribution of binary linear block codes, IEEE Transactions on Information Theory, 52 (2006), 4444-4454.  doi: 10.1109/TIT.2006.881739.
  • 加载中

Tables(1)

SHARE

Article Metrics

HTML views(2708) PDF downloads(659) Cited by(0)

Access History

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return