On the ideal associated to a linear code

Irene  Márquez-Corbella; Edgar Martínez-Moro; Emilio  Suárez-Canedo

doi:10.3934/amc.2016003

Article Contents

2016, Volume 10, Issue 2: 229-254. Doi: 10.3934/amc.2016003

This issue Previous Article On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$ Next Article On self-dual cyclic codes of length $p^a$ over $GR(p^2,s)$

On the ideal associated to a linear code

1.
INRIA Paris-Rocquencourt, SECRET Project-Team, 78153 Le Chesnay Cedex
2.
Dpto. Matemática Aplicada, Universidad de Valladolid, Castilla
3.
Departament d'Enginyeria de la Informació i de les Comunicacions, Universitat Autònoma de Barcelona (UAB)

Received: May 31, 2013

Revised: January 31, 2015

Published: April 2016

Abstract Related Papers Cited by

Abstract

This article aims to explore the bridge between the algebraic structure of a linear code and the complete decoding process. To this end, we associate a specific binomial ideal $I_+(\mathcal C)$ to an arbitrary linear code. The binomials involved in the reduced Gröbner basis of such an ideal relative to a degree-compatible ordering induce a uniquely defined test-set for the code, and this allows the description of a Hamming metric decoding procedure. Moreover, the binomials involved in the Graver basis of $I_+(\mathcal C)$ provide a universal test-set which turns out to be a set containing the set of codewords of minimal support of the code.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 13P25; Secondary: 13P10.

Citation:

Related Papers

Cited by

References

[1]	M. Aliasgari, M. R. Sadeghi and D. Panario, Gröbner Bases for Lattices and an Algebraic Decoding Algorithm, IEEE Trans. Commun., 61 (2013), 1222-1230.
[2]	A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017.doi: 10.1109/18.705584.
[3]	A. Barg, Complexity issues in coding theory, in Handbook of Coding Theory, North-Holland, Amsterdam, 1998, 649-754.
[4]	E. R. Berlekamp, R. J. McEliece and H. C. A. Van Tilborg, On the inherent intractability of certain coding problems, IEEE Trans. Inf. Theory, IT-24 (1978), 384-386.
[5]	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.
[6]	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 Inf. Theory Workshop (ITW), 2010, 1-4.
[7]	J. Bruck and M. Naor, The hardness of decoding linear codes with preprocessing, IEEE Trans. Inf. Theory, 36 (1990), 381-385.doi: 10.1109/18.52484.
[8]	D. A. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 2007.doi: 10.1007/978-0-387-35651-8.
[9]	F. Di Biase and R. Urbanke, An algorithm to calculate the kernel of certain polynomial ring homomorphisms, Exper. Math., 4 (1995), 227-234.
[10]	D. Eisenbud and B. Sturmfels, Binomial ideals, Duke Math. J., 84 (1996), 1-45.doi: 10.1215/S0012-7094-96-08401-X.
[11]	J. C. Faugère, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput., 16 (193), 329-344. doi: 10.1006/jsco.1993.1051.
[12]	P. Fitzpatrick, Solving a multivariable congruence by change of term order, J. Symb. Comput., 24 (1997), 575-589.doi: 10.1006/jsco.1997.0153.
[13]	P. Fitzpatrick and J. Flynn, A Gröbner basis technique for Padé approximation, J. Symb. Comput., 13 (1992), 133-138.doi: 10.1016/S0747-7171(08)80087-9.
[14]	D. Ikegami and Y. Kaji, Maximum likelihood decoding for linear block codes using Grobner bases, IEICE Trans. Fund. Electron. Commun. Comput. Sci., E86-A (2003), 643-651.
[15]	R. A. Liebler, Implementing gradient descent decoding, Michigan Math. J., 58 (2009), 285-291.doi: 10.1307/mmj/1242071693.
[16]	I. Márquez-Corbella and E. Martínez-Moro, Algebraic structure of the minimal support codewords set of some linear codes, Adv. Math. Commun., 5 (2011), 233-244.doi: 10.3934/amc.2011.5.233.
[17]	I. Márquez-Corbella and E. Martínez-Moro, Decomposition of modular codes for computing test sets and Graver basis, Math. Comp. Sci., 6 (2012), 147-165.doi: 10.1007/s11786-012-0120-y.
[18]	E. Prange, Step-by-step decoding in groups with weight function. Part 1, Air Force Cambridge Res. Labs Hanscom AFB MA, 1961.
[19]	P. Samuel, Algebraic Theory of Numbers: Translated from the French by Allan J. Silberger, Dover, 2013.
[20]	B. Sturmfels, Gröbner Bases and Convex Polytopes, Amer. Math. Soc., Providence, 1996.