American Institute of Mathematical Sciences

Advanced
February  2016, 10(1): 195-207. doi: 10.3934/amc.2016.10.195

Algorithms for the minimum weight of linear codes

Petr Lisoněk 1, and  Layla Trummer 1,

1. 

Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada, Canada

Received  December 2014 Revised  November 2015 Published  March 2016

We outline the algorithm for computing the minimum weight of a linear code over a finite field that was invented by A.~Brouwer and later extended by K.-H. Zimmermann. We show that matroid partitioning algorithms can be used to efficiently find a favourable (and sometimes best possible) sequence of information sets on which the Brouwer-Zimmermann algorithm operates. We present a new algorithm for computing the minimum weight of a linear code. We use a large set of codes to compare our new algorithm with the Brouwer-Zimmermann algorithm. We find that for about one third of codes in this sample set, our algorithm requires to generate fewer codewords than the Brouwer-Zimmermann algorithm.
Keywords: information set, Brouwer-Zimmermann algorithm, Linear code, minimum weight algorithm, matroid partition..
Mathematics Subject Classification: Primary: 94B05; Secondary: 05B3.
Citation: Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
References:
[1]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes, Springer-Verlag, 2006.  Google Scholar

[2]

A. Betten, H. Fripertinger, A. Kerber, A. Wassermann and K.-H. Zimmermann, Codierungstheorie-Konstruktion und Anwendung linearer Codes, Springer-Verlag, 1998. Google Scholar

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

A. Canteaut, V. Lallemand and M. Naya-Plasencia, Related-key attack on full-round PICARO, in Proc. 22nd Int. Conf. Sel. Areas Crypt. 2015 (eds. O. Dunkelman and L. Keliher), Springer, 2015. Google Scholar

[5]

W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15 (1986), 948-957. doi: 10.1137/0215066.  Google Scholar

[6]

J. Edmonds, Matroid partition, Math. Decis. Sci., 11 (1968), 335-345.  Google Scholar

[7]

M. Grassl, Searching for linear codes with large minimum distance, in Discovering Mathematics with Magma - Reducing the Abstract to the Concrete (eds. W. Bosma and J. Cannon), Springer, 2006, 287-313. doi: 10.1007/978-3-540-37634-7_13.  Google Scholar

[8]

M. Kiermaier and A. Wassermann, Minimum weights and weight enumerators of $\mathbb Z_4$-linear quadratic residue codes, IEEE Trans. Inf. Theory, 58 (2012), 4870-4883. doi: 10.1109/TIT.2012.2191389.  Google Scholar

[9]

E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.  Google Scholar

[10]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977. Google Scholar

[11]

J. Oxley, Matroid Theory, 2nd edition, Oxford University Press, 2011. doi: 10.1093/acprof:oso/9780198566946.001.0001.  Google Scholar

[12]

A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inf. Theory, 43 (1997), 1757-1766. doi: 10.1109/18.641542.  Google Scholar

show all references

References:
[1]

A. Betten, M. Braun, H. Fripertinger, A. Kerber, A. Kohnert and A. Wassermann, Error-Correcting Linear Codes, Springer-Verlag, 2006.  Google Scholar

[2]

A. Betten, H. Fripertinger, A. Kerber, A. Wassermann and K.-H. Zimmermann, Codierungstheorie-Konstruktion und Anwendung linearer Codes, Springer-Verlag, 1998. Google Scholar

[3]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.  Google Scholar

[4]

A. Canteaut, V. Lallemand and M. Naya-Plasencia, Related-key attack on full-round PICARO, in Proc. 22nd Int. Conf. Sel. Areas Crypt. 2015 (eds. O. Dunkelman and L. Keliher), Springer, 2015. Google Scholar

[5]

W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15 (1986), 948-957. doi: 10.1137/0215066.  Google Scholar

[6]

J. Edmonds, Matroid partition, Math. Decis. Sci., 11 (1968), 335-345.  Google Scholar

[7]

M. Grassl, Searching for linear codes with large minimum distance, in Discovering Mathematics with Magma - Reducing the Abstract to the Concrete (eds. W. Bosma and J. Cannon), Springer, 2006, 287-313. doi: 10.1007/978-3-540-37634-7_13.  Google Scholar

[8]

M. Kiermaier and A. Wassermann, Minimum weights and weight enumerators of $\mathbb Z_4$-linear quadratic residue codes, IEEE Trans. Inf. Theory, 58 (2012), 4870-4883. doi: 10.1109/TIT.2012.2191389.  Google Scholar

[9]

E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.  Google Scholar

[10]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977. Google Scholar

[11]

J. Oxley, Matroid Theory, 2nd edition, Oxford University Press, 2011. doi: 10.1093/acprof:oso/9780198566946.001.0001.  Google Scholar

[12]

A. Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inf. Theory, 43 (1997), 1757-1766. doi: 10.1109/18.641542.  Google Scholar

[1]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[2]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[3]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[4]

Xueyan Wu. An algorithm for reversible information hiding of encrypted medical images in homomorphic encrypted domain. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1441-1455. doi: 10.3934/dcdss.2019099
[5]

Weiping Li, Haiyan Wu, Jie Yang. Intelligent recognition algorithm for social network sensitive information based on classification technology. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1385-1398. doi: 10.3934/dcdss.2019095
[6]

Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014
[7]

Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399
[8]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[9]

Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417
[10]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[11]

Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control & Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012
[12]

Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021017
[13]

Fernando Casas, Cristina Chiralt. A Lie--Deprit perturbation algorithm for linear differential equations with periodic coefficients. Discrete & Continuous Dynamical Systems, 2014, 34 (3) : 959-975. doi: 10.3934/dcds.2014.34.959
[14]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[15]

Christopher Grumiau, Marco Squassina, Christophe Troestler. On the Mountain-Pass algorithm for the quasi-linear Schrödinger equation. Discrete & Continuous Dynamical Systems - B, 2013, 18 (5) : 1345-1360. doi: 10.3934/dcdsb.2013.18.1345
[16]

Wenjuan Jia, Yingjie Deng, Chenyang Xin, Xiaodong Liu, Witold Pedrycz. A classification algorithm with Linear Discriminant Analysis and Axiomatic Fuzzy Sets. Mathematical Foundations of Computing, 2019, 2 (1) : 73-81. doi: 10.3934/mfc.2019006
[17]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[18]

Nguyen Thi Bach Kim. Finite algorithm for minimizing the product of two linear functions over a polyhedron. Journal of Industrial & Management Optimization, 2007, 3 (3) : 481-487. doi: 10.3934/jimo.2007.3.481
[19]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021134
[20]

Nguyen Thi Bach Kim, Nguyen Canh Nam, Le Quang Thuy. An outcome space algorithm for minimizing the product of two convex functions over a convex set. Journal of Industrial & Management Optimization, 2013, 9 (1) : 243-253. doi: 10.3934/jimo.2013.9.243

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (91)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences