\`x^2+y_1+z_12^34\`
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.

    Citation:

    \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.

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

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return