American Institute of Mathematical Sciences

Advanced
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

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. Google Scholar

[2]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017. doi: 10.1109/18.705584.  Google Scholar

[3]

A. Barg, Complexity issues in coding theory, in Handbook of Coding Theory, North-Holland, Amsterdam, 1998, 649-754.  Google Scholar

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

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

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

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

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

[9]

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

[10]

D. Eisenbud and B. Sturmfels, Binomial ideals, Duke Math. J., 84 (1996), 1-45. doi: 10.1215/S0012-7094-96-08401-X.  Google Scholar

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

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

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

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

[15]

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

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

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

[18]

E. Prange, Step-by-step decoding in groups with weight function. Part 1, Air Force Cambridge Res. Labs Hanscom AFB MA, 1961. Google Scholar

[19]

P. Samuel, Algebraic Theory of Numbers: Translated from the French by Allan J. Silberger, Dover, 2013. Google Scholar

[20]

B. Sturmfels, Gröbner Bases and Convex Polytopes, Amer. Math. Soc., Providence, 1996.  Google Scholar

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. Google Scholar

[2]

A. Ashikhmin and A. Barg, Minimal vectors in linear codes, IEEE Trans. Inf. Theory, 44 (1998), 2010-2017. doi: 10.1109/18.705584.  Google Scholar

[3]

A. Barg, Complexity issues in coding theory, in Handbook of Coding Theory, North-Holland, Amsterdam, 1998, 649-754.  Google Scholar

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

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

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

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

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

[9]

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

[10]

D. Eisenbud and B. Sturmfels, Binomial ideals, Duke Math. J., 84 (1996), 1-45. doi: 10.1215/S0012-7094-96-08401-X.  Google Scholar

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

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

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

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

[15]

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

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

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

[18]

E. Prange, Step-by-step decoding in groups with weight function. Part 1, Air Force Cambridge Res. Labs Hanscom AFB MA, 1961. Google Scholar

[19]

P. Samuel, Algebraic Theory of Numbers: Translated from the French by Allan J. Silberger, Dover, 2013. Google Scholar

[20]

B. Sturmfels, Gröbner Bases and Convex Polytopes, Amer. Math. Soc., Providence, 1996.  Google Scholar

[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 & 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 & 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 & 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]

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
[12]

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
[13]

K. Schittkowski. Optimal parameter selection in support vector machines. Journal of Industrial & Management Optimization, 2005, 1 (4) : 465-476. doi: 10.3934/jimo.2005.1.465
[14]

Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial & Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[15]

Lauri Harhanen, Nuutti Hyvönen. Convex source support in half-plane. Inverse Problems & Imaging, 2010, 4 (3) : 429-448. doi: 10.3934/ipi.2010.4.429
[16]

Florian Dumpert. Quantitative robustness of localized support vector machines. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3947-3956. doi: 10.3934/cpaa.2020174
[17]

Yubo Yuan, Weiguo Fan, Dongmei Pu. Spline function smooth support vector machine for classification. Journal of Industrial & Management Optimization, 2007, 3 (3) : 529-542. doi: 10.3934/jimo.2007.3.529
[18]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[19]

Armin Lechleiter. Explicit characterization of the support of non-linear inclusions. Inverse Problems & Imaging, 2011, 5 (3) : 675-694. doi: 10.3934/ipi.2011.5.675
[20]

Hong-Gunn Chew, Cheng-Chew Lim. On regularisation parameter transformation of support vector machines. Journal of Industrial & Management Optimization, 2009, 5 (2) : 403-415. doi: 10.3934/jimo.2009.5.403

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (144)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences