doi: 10.3934/amc.2020130
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.

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 Early access 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]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233

[2]

Stefka Bouyuklieva, Zlatko Varbanov. Some connections between self-dual codes, combinatorial designs and secret sharing schemes. Advances in Mathematics of Communications, 2011, 5 (2) : 191-198. doi: 10.3934/amc.2011.5.191

[3]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[4]

Gérard Cohen, Sihem Mesnager, Hugues Randriam. Yet another variation on minimal linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 53-61. doi: 10.3934/amc.2016.10.53

[5]

Bagher Bagherpour, Shahrooz Janbaz, Ali Zaghian. Optimal information ratio of secret sharing schemes on Dutch windmill graphs. Advances in Mathematics of Communications, 2019, 13 (1) : 89-99. doi: 10.3934/amc.2019005

[6]

Kristian Bjerklöv, Russell Johnson. Minimal subsets of projective flows. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 493-516. doi: 10.3934/dcdsb.2008.9.493

[7]

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

[8]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[9]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[10]

Ryutaroh Matsumoto. Strongly secure quantum ramp secret sharing constructed from algebraic curves over finite fields. Advances in Mathematics of Communications, 2019, 13 (1) : 1-10. doi: 10.3934/amc.2019001

[11]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[12]

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

[13]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[14]

Carlos Durán, Diego Otero. The projective Cartan-Klein geometry of the Helmholtz conditions. Journal of Geometric Mechanics, 2018, 10 (1) : 69-92. doi: 10.3934/jgm.2018003

[15]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[16]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[17]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001

[18]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127

[19]

Carlos Durán, Diego Otero. The projective symplectic geometry of higher order variational problems: Minimality conditions. Journal of Geometric Mechanics, 2016, 8 (3) : 305-322. doi: 10.3934/jgm.2016009

[20]

Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (101)
  • HTML views (302)
  • Cited by (0)

[Back to Top]