On the ideal associated to a linear code

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

May 2016, 10(2): 229-254. doi: 10.3934/amc.2016003

On the ideal associated to a linear code

Irene Márquez-Corbella ^1, , Edgar Martínez-Moro ^2, and Emilio Suárez-Canedo ^3,

1.	INRIA Paris-Rocquencourt, SECRET Project-Team, 78153 Le Chesnay Cedex, France
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), Spain

Received June 2013 Revised February 2015 Published April 2016

Abstract
Related Papers

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: Gröbner bases, minimal support codewords., Graver bases.

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

Citation: Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

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 (): 329. 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.

show all references

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 (): 329. 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.

[1]	Ismara Álvarez-Barrientos, Mijail Borges-Quintana, Miguel Angel Borges-Trenard, Daniel Panario. Computing Gröbner bases associated with lattices. Advances in Mathematics of Communications, 2016, 10 (4) : 851-860. doi: 10.3934/amc.2016045
[2]	Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046
[3]	Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[4]	Arnulf Jentzen, Felix Lindner, Primož Pušnik. On the Alekseev-Gröbner formula in Banach spaces. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4475-4511. doi: 10.3934/dcdsb.2019128
[5]	Romar dela Cruz, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. On the minimum number of minimal codewords. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020130
[6]	Piotr Pokora, Tomasz Szemberg. Minkowski bases on algebraic surfaces with rational polyhedral pseudo-effective cone. Electronic Research Announcements, 2014, 21: 126-131. doi: 10.3934/era.2014.21.126
[7]	Seok-Jin Kang and Jae-Hoon Kwon. Quantum affine algebras, combinatorics of Young walls, and global bases. Electronic Research Announcements, 2002, 8: 35-46.
[8]	Sergei Avdonin, Julian Edward. Controllability for a string with attached masses and Riesz bases for asymmetric spaces. Mathematical Control and Related Fields, 2019, 9 (3) : 453-494. doi: 10.3934/mcrf.2019021
[9]	Anna Chiara Lai, Paola Loreti. Robot's finger and expansions in non-integer bases. Networks and Heterogeneous Media, 2012, 7 (1) : 71-111. doi: 10.3934/nhm.2012.7.71
[10]	Abderrazek Karoui. A note on the construction of nonseparable wavelet bases and multiwavelet matrix filters of $L^2(\R^n)$, where $n\geq 2$. Electronic Research Announcements, 2003, 9: 32-39.
[11]	Daniele Bartoli, Lins Denaux. Minimal codewords arising from the incidence of points and hyperplanes in projective spaces. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021061
[12]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[13]	Somphong Jitman, San Ling, Ekkasit Sangwisut. On self-dual cyclic codes of length $p^a$ over $GR(p^2,s)$. Advances in Mathematics of Communications, 2016, 10 (2) : 255-273. doi: 10.3934/amc.2016004
[14]	K. Schittkowski. Optimal parameter selection in support vector machines. Journal of Industrial and Management Optimization, 2005, 1 (4) : 465-476. doi: 10.3934/jimo.2005.1.465
[15]	Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial and Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[16]	Lauri Harhanen, Nuutti Hyvönen. Convex source support in half-plane. Inverse Problems and Imaging, 2010, 4 (3) : 429-448. doi: 10.3934/ipi.2010.4.429
[17]	Florian Dumpert. Quantitative robustness of localized support vector machines. Communications on Pure and Applied Analysis, 2020, 19 (8) : 3947-3956. doi: 10.3934/cpaa.2020174
[18]	Yubo Yuan, Weiguo Fan, Dongmei Pu. Spline function smooth support vector machine for classification. Journal of Industrial and Management Optimization, 2007, 3 (3) : 529-542. doi: 10.3934/jimo.2007.3.529
[19]	Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[20]	Armin Lechleiter. Explicit characterization of the support of non-linear inclusions. Inverse Problems and Imaging, 2011, 5 (3) : 675-694. doi: 10.3934/ipi.2011.5.675

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Irene Márquez-Corbella Edgar Martínez-Moro Emilio Suárez-Canedo
on Google Scholar
Irene Márquez-Corbella Edgar Martínez-Moro Emilio Suárez-Canedo

[Back to Top]