Article Contents
Article Contents

# Algorithms for the minimum weight of linear codes

• 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.
Mathematics Subject Classification: Primary: 94B05; Secondary: 05B35.

 Citation:

•  [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.