May  2011, 5(2): 233-244. doi: 10.3934/amc.2011.5.233

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

1. 

Dpto. Álgebra, Geometría y Topología, Universidad de Valladolid, Castilla, Spain

2. 

Dpto. Matemática Aplicada, Universidad de Valladolid, Castilla, Spain

Received  April 2010 Revised  December 2010 Published  May 2011

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.
Citation: 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
References:
[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.

[2]

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.

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

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

[8]

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.

[9]

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.

[10]

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

[11]

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.

[12]

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.

[13]

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

[14]

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

[15]

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.

[16]

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.

[17]

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

[18]

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

show all references

References:
[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.

[2]

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.

[3]

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.

[4]

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.

[5]

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.

[6]

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.

[7]

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

[8]

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.

[9]

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.

[10]

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

[11]

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.

[12]

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.

[13]

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

[14]

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

[15]

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.

[16]

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.

[17]

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

[18]

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

[1]

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

[2]

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

[3]

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

[4]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[5]

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

[6]

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

[7]

Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439

[8]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[9]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[10]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[11]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[12]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[13]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

[14]

Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179

[15]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[16]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[17]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[18]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[19]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128

[20]

Fanwen Meng, Kiok Liang Teow, Kelvin Wee Sheng Teo, Chee Kheong Ooi, Seow Yian Tay. Predicting 72-hour reattendance in emergency departments using discriminant analysis via mixed integer programming with electronic medical records. Journal of Industrial and Management Optimization, 2019, 15 (2) : 947-962. doi: 10.3934/jimo.2018079

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (93)
  • HTML views (0)
  • Cited by (9)

[Back to Top]