Algorithms for the minimum weight of linear codes

Petr  Lisoněk; Layla  Trummer

doi:10.3934/amc.2016.10.195

Article Contents

2016, Volume 10, Issue 1: 195-207. Doi: 10.3934/amc.2016.10.195

This issue Previous Article Decoding of $2$D convolutional codes over an erasure channel Next Article

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

Received: November 30, 2014

Revised: October 31, 2015

Published: January 2016

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94B05; Secondary: 05B35.

Citation:

Related Papers

Cited by

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.