Advanced Search
Article Contents
Article Contents

Algebraic structure of the minimal support codewords set of some linear codes

Abstract Related Papers Cited by
  • It has been widely known that complete decoding for binary linear codes can be regarded as a linear integer programming problem with binary arithmetic conditions. Conti and Traverso [9] have proposed an algorithm which uses Gröbner bases to solve integer programming with ordinary integer arithmetic conditions. Ikegami and Kaji [12] extended the Conti-Traverso algorithm to solve integer programming with modulo arithmetic conditions. It is natural to consider for those problems the Graver basis associated to them which turns out to be the minimal cycles of the matroid associated to the code, i.e. minimal support codewords in the binary case and its geometry. This provides us a universal test set for the programs considered.
    Mathematics Subject Classification: Primary: 94B05, 13P25; Secondary: 13P10.


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

    A. Barg, Complexity issues in coding theory, in "Handbook of Coding Theory'' (eds. V. Pless and W. Huffman), Elsevier Science, I (1998), 649-754.


    E. R. Berlekamp, R. J. McEliece and H. C. A. van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inform. Theory, IT-24 (1978), 384-386.doi: 10.1109/TIT.1978.1055873.


    T. Bogart, A. N. Jensen and R. R. Thomas, The circuit ideal of a vector configuration, J. Algebra, 308 (2007), 518-542.doi: 10.1016/j.jalgebra.2006.07.025.


    M. Borges-Quintana, M. A. Borges-Trenard, P. Fitzpatrick and E. Martínez-Moro, Gröbner bases and combinatorics for binary codes, Appl. Algebra Engrg. Comm. Comput., 19 (2008), 393-411.doi: 10.1007/s00200-008-0080-2.


    M. Borges-Quintana, M. A. Borges-Trenard, I. Márquez-Corbella and E. Martínez-Moro, An algebraic view to gradient descent decoding, in "IEEE Information Theory Workshop 2010,'' Dublin, 2010.


    M. Borges-Quintana, M. A. Borges-Trenard and E. Martínez-Moro, A Gröbner bases structure associated to linear codes, J. Discrete Math. Sci. Cryptogr., 10 (2007), 151-191.


    Y. Borissov and N. Manev, Minimal codewords in linear codes, Serdica Math. J., 30 (2004), 303-324.


    J. Bruck and M. Naor, The hardness of decoding linear codes with preprocessing, IEEE Trans. Inform. Theory, 36 (1990), 381-385.doi: 10.1109/18.52484.


    P. Conti and C. Traverso, Buchberger algorithm and integer programming, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes,'' New Orleans, LA, (1991), 130-139.


    F. Di Biase and R. Urbanke, An algorithm to calculate the kernel of certain polynomial ring homomorphisms, Experiment. Math., 4 (1995), 227-234.


    T. Y. Hwang, Decoding linear block codes for minimizing word error rate, IEEE Trans. Inform. Theory, 25 (1979), 733-737.doi: 10.1109/TIT.1979.1056120.


    D. Ikegami and Y. Kaji, Maximum likelihood decoding for linear block codes using Gröbner bases, IEICE Trans. Fund. Electron. Commun. Comput. Sci., E86-A , 3 (2003), 643-651.


    R. Liebler, Implementing gradient descent decoding, Michigan Math. J., 58 (2009), 285-291.doi: 10.1307/mmj/1242071693.


    J. L. Massey, Minimal Codewords and Secret Sharing, in "Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory,'' (1993), 246-249.


    H. Ohsugi, D. Ikegami, T. Kitamura and T. Hibi, Gröbner bases bases of certain zero-dimensional ideals arising in coding theory, Adv. Appl. Math., 31 (2003), 420-432.doi: 10.1016/S0196-8858(03)00019-8.


    P. Pisón-Casares and A. Vigneron-Tenorio, On Lawrence semigroups, J. Symb. Comput., 43 (2008), 804-810.doi: 10.1016/j.jsc.2008.02.003.


    A. Schrijver, "Theory of Linear and Integer Programming,'' Wiley-Interscience, 1996.


    B. Sturmfels, "Gröbner Bases and Convex Polytopes,'' American Mathematical Society, Providence, RI, 1996.

  • 加载中

Article Metrics

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

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint