Advanced Search
Article Contents
Article Contents

Algorithms for the minimum weight of linear codes

Abstract Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • [1]

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


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


    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.


    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.


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


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


    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.


    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.


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


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


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


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(147) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint