doi: 10.3934/amc.2020130

On the minimum number of minimal codewords

1. 

Institute of Mathematics, University of the Philippines Diliman, 1101 Quezon City, Philippines

2. 

Mathematisches Institut, University of Bayreuth, D-95440 Bayreuth, Germany

* Corresponding author

Received  May 2020 Revised  October 2020 Published  January 2021

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

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.

Citation: Romar dela Cruz, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. On the minimum number of minimal codewords. Advances in Mathematics of Communications, doi: 10.3934/amc.2020130
References:
[1]

E. Agrell, Voronoi Regions for binary linear block codes, IEEE Transactions on Information Theory, 42 (1996), 310-316.  doi: 10.1109/18.481810.  Google Scholar

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

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

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

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

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

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

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

[9]

Y. Borissov and N. Manev, Minimal codewords in linear codes, Serdica Mathematical Journal, 30 (2004), 303-324.   Google Scholar

[10]

T. Britz, Higher support matroids, Discrete Mathematics, 307 (2007), 2300-2308.  doi: 10.1016/j.disc.2006.12.001.  Google Scholar

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

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

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

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

[15]

R. Entringer and P. Slater, On the maximum number of cycles in a graph, Ars Combinatoria, 11 (1981), 289-294.   Google Scholar

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

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

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

[19]

N. Kashyap, On the convex geometry of binary linear codes, preprint, (2006). Google Scholar

[20]

S. Kurz, LinCode - Computer Classification Of Linear Codes, preprint, (2019), arXiv: 1912.09357. Google Scholar

[21]

W. Lu, X. Wu and X. Cao, The Parameters of Minimal Linear Codes, preprint, (2019), arXiv: 1911.07648. Google Scholar

[22]

J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Workshop Inf. Theory, Sweden, (1993), 276–279. Google Scholar

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

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

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

[26]

V. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259.  Google Scholar

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

show all references

References:
[1]

E. Agrell, Voronoi Regions for binary linear block codes, IEEE Transactions on Information Theory, 42 (1996), 310-316.  doi: 10.1109/18.481810.  Google Scholar

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

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

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

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

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

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

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

[9]

Y. Borissov and N. Manev, Minimal codewords in linear codes, Serdica Mathematical Journal, 30 (2004), 303-324.   Google Scholar

[10]

T. Britz, Higher support matroids, Discrete Mathematics, 307 (2007), 2300-2308.  doi: 10.1016/j.disc.2006.12.001.  Google Scholar

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

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

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

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

[15]

R. Entringer and P. Slater, On the maximum number of cycles in a graph, Ars Combinatoria, 11 (1981), 289-294.   Google Scholar

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

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

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

[19]

N. Kashyap, On the convex geometry of binary linear codes, preprint, (2006). Google Scholar

[20]

S. Kurz, LinCode - Computer Classification Of Linear Codes, preprint, (2019), arXiv: 1912.09357. Google Scholar

[21]

W. Lu, X. Wu and X. Cao, The Parameters of Minimal Linear Codes, preprint, (2019), arXiv: 1911.07648. Google Scholar

[22]

J. L. Massey, Minimal codewords and secret sharing, in Proc. 6th Joint Swedish-Russian Workshop Inf. Theory, Sweden, (1993), 276–279. Google Scholar

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

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

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

[26]

V. Wei, Generalized Hamming weights for linear codes, IEEE Transactions on Information Theory, 37 (1991), 1412-1418.  doi: 10.1109/18.133259.  Google Scholar

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

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

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[2]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[3]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[4]

Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169

[5]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[6]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[7]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[8]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[9]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[10]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[11]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[12]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]