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.

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

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.

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

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]

Daniele Bartoli, Lins Denaux. Minimal codewords arising from the incidence of points and hyperplanes in projective spaces. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021061

[3]

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

[4]

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

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

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 0.935

Article outline

Figures and Tables

[Back to Top]