Advances in Mathematics of Communications (AMC)

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

Pages: 233 - 244, Volume 5, Issue 2, May 2011      doi:10.3934/amc.2011.5.233

       Abstract        References        Full Text (404.9K)       Related Articles       

Irene Márquez-Corbella - Dpto. Álgebra, Geometría y Topología, Universidad de Valladolid, Castilla, Spain (email)
Edgar Martínez-Moro - Dpto. Matemática Aplicada, Universidad de Valladolid, Castilla, Spain (email)

Abstract: 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.

Keywords:  Minimal codewords, modular/integer programming, Gröbner basis.
Mathematics Subject Classification:  Primary: 94B05, 13P25; Secondary: 13P10.

Received: April 2010;      Revised: December 2010;      Available Online: May 2011.