Algorithms for the minimum weight of linear codes

Previous Article
AMC Home
This Issue
Next Article
Decoding of $2$D convolutional codes over an erasure channel

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

Abstract
Related Papers

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.
[2]	A. Betten, H. Fripertinger, A. Kerber, A. Wassermann and K.-H. Zimmermann, Codierungstheorie-Konstruktion und Anwendung linearer Codes, Springer-Verlag, 1998.
[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.
[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.
[5]	W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15 (1986), 948-957. doi: 10.1137/0215066.
[6]	J. Edmonds, Matroid partition, Math. Decis. Sci., 11 (1968), 335-345.
[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.
[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.
[9]	E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
[10]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
[11]	J. Oxley, Matroid Theory, 2nd edition, Oxford University Press, 2011. doi: 10.1093/acprof:oso/9780198566946.001.0001.
[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.

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.
[2]	A. Betten, H. Fripertinger, A. Kerber, A. Wassermann and K.-H. Zimmermann, Codierungstheorie-Konstruktion und Anwendung linearer Codes, Springer-Verlag, 1998.
[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.
[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.
[5]	W. H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM J. Comput., 15 (1986), 948-957. doi: 10.1137/0215066.
[6]	J. Edmonds, Matroid partition, Math. Decis. Sci., 11 (1968), 335-345.
[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.
[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.
[9]	E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
[10]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
[11]	J. Oxley, Matroid Theory, 2nd edition, Oxford University Press, 2011. doi: 10.1093/acprof:oso/9780198566946.001.0001.
[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.

[1]	Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022031
[2]	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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[3]	Toshiharu Sawashima, Tatsuya Maruta. Nonexistence of some ternary linear codes with minimum weight -2 modulo 9. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021052
[4]	I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[5]	Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$₄-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
[6]	Xueyan Wu. An algorithm for reversible information hiding of encrypted medical images in homomorphic encrypted domain. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1441-1455. doi: 10.3934/dcdss.2019099
[7]	Weiping Li, Haiyan Wu, Jie Yang. Intelligent recognition algorithm for social network sensitive information based on classification technology. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1385-1398. doi: 10.3934/dcdss.2019095
[8]	Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014
[9]	Mingfang Ding, Yanqun Liu, John Anthony Gear. An improved targeted climbing algorithm for linear programs. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 399-405. doi: 10.3934/naco.2011.1.399
[10]	Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial and Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[11]	Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417
[12]	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
[13]	Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control and Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012
[14]	Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 445-467. doi: 10.3934/naco.2021017
[15]	Fernando Casas, Cristina Chiralt. A Lie--Deprit perturbation algorithm for linear differential equations with periodic coefficients. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 959-975. doi: 10.3934/dcds.2014.34.959
[16]	Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[17]	Christopher Grumiau, Marco Squassina, Christophe Troestler. On the Mountain-Pass algorithm for the quasi-linear Schrödinger equation. Discrete and Continuous Dynamical Systems - B, 2013, 18 (5) : 1345-1360. doi: 10.3934/dcdsb.2013.18.1345
[18]	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
[19]	Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[20]	Nguyen Thi Bach Kim. Finite algorithm for minimizing the product of two linear functions over a polyhedron. Journal of Industrial and Management Optimization, 2007, 3 (3) : 481-487. doi: 10.3934/jimo.2007.3.481

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Petr Lisoněk Layla Trummer
on Google Scholar
Petr Lisoněk Layla Trummer

[Back to Top]