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

Algorithms for the minimum weight of linear codes

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.
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.  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), (2015).   Google Scholar

[5]

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

[6]

J. Edmonds, Matroid partition,, Math. Decis. Sci., 11 (1968), 335.   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), (2006), 287.  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.  doi: 10.1109/TIT.2012.2191389.  Google Scholar

[9]

E. L. Lawler, Combinatorial Optimization: Networks and Matroids,, Holt, (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.  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.  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), (2015).   Google Scholar

[5]

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

[6]

J. Edmonds, Matroid partition,, Math. Decis. Sci., 11 (1968), 335.   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), (2006), 287.  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.  doi: 10.1109/TIT.2012.2191389.  Google Scholar

[9]

E. L. Lawler, Combinatorial Optimization: Networks and Matroids,, Holt, (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.  doi: 10.1109/18.641542.  Google Scholar

[1]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[2]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049

[3]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[4]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[5]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[6]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[7]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[8]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[9]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[10]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[11]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]