On the minimum number of minimal codewords

Romar dela Cruz; Michael Kiermaier; Sascha Kurz; Alfred Wassermann

doi:10.3934/amc.2020130

Article Contents

2023, Volume 17, Issue 2: 333-341. Doi: 10.3934/amc.2020130

This issue Previous Article Codes with few weights arising from linear sets Next Article A new class of optimal wide-gap one-coincidence frequency-hopping sequence sets

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
^* Corresponding author

Received: May 2020

Revised: October 2020

Early access: January 2021

Published: April 2023

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Related Papers

Cited by

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. Alahmadi, R. E. L. Aldred, R. dela Cruz, S. Ok, P. 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. Alahmadi, R. E. L. Aldred, R. dela Cruz, P. 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. Alahmadi, R. E. L. Aldred, R. dela Cruz, P. 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. Ding, D. 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. Dosa, I. 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. Schillewaert, L. 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.