Gröbner bases and combinatorics for binary codes

DOI10.1007/S00200-008-0080-2zbMATH Open1192.94130arXivmath/0509164OpenAlexW2044900678MaRDI QIDQ985374FDOQ985374

E. Martínez-Moro, Mijail Borges-Quintana, Miguel Angel Borges-Trenard, Patrick Fitzpatrick

Publication date: 5 August 2010

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Abstract: In this paper we introduce a binomial ideal derived from a binary linear code. We present some applications of a Gr"obner basis of this ideal with respect to a total degree ordering. In the first application we give a decoding method for the code. By associating the code with the set of cycles in a graph, we can solve the problem of finding all codewords of minimal length (minimal cycles in a graph), and show how to find a minimal cycle basis. Finally we discuss some results on the computation of the Gr"obner basis.

Full work available at URL: https://arxiv.org/abs/math/0509164

Recommendations

• scientific article
• A decoding algorithm for binary linear codes using Groebner bases
• On the decoding of cyclic codes using Gröbner bases
• A Gröbner representation for linear codes
• Gröbner bases of certain zero-dimensional ideals arising in coding theory

zbMATH Keywords

cycle basesbinary codesGröbner bases

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Combinatorial codes (94B25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• A Gröbner basis technique for Padé approximation
• Solving a multivariable congruence by change of term order
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing Gröbner bases by FGLM techniques in a non-commutative setting
• On a Gröbner bases structure associated to linear codes
• A Gröbner representation for linear codes
• Bounds for the degrees in the Nullstellensatz
• Union of all the minimum cycle bases of a graph
• Error-Correction Capability of Binary Linear Codes
• Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
• Title not available (Why is that?)

Cited In (18)

• Linear label code of a root lattice using Gröbner bases
• Trial Set and Gröbner Bases for Binary Codes
• An application of Möller's algorithm to coding theory
• On the Fan Associated to a Linear Code
• Gröbner bases of certain zero-dimensional ideals arising in coding theory
• Heuristic decoding of linear codes using commutative algebra
• Gröbner representations of binary matroids
• On the ideal associated to a linear code
• Characteristic vector and weight distribution of a linear code
• Algebraic Modelling of Covering Arrays
• Computing sharp recovery structures for locally recoverable codes
• Binomial coefficient codes over GF(2)
• Gröbner bases over commutative rings and applications to coding theory
• Decomposition of modular codes for computing test sets and Graver basis
• Computing Gröbner bases associated with lattices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounded distance decoding of linear error-correcting codes with Gröbner bases

This page was built for publication: Gröbner bases and combinatorics for binary codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q985374)