Groebner Bases for Linear Codes

Error-correcting codes are used to enable reliable delivery of digital data over unreliable communication channels. This typically involves to add extra bits to make the transmission of data more robust to disturbance present on the transmission channel. In particular, linear codes provide an extra structure that allows an efficient encoding of the data.

Recently, Fitzpatrick et al. have associated binomial ideals with binary linear codes. Groebner basis computations were used for decoding and to solve several problems related to graphs associated with the code.

More recently, we have emphasized that linear codes over prime fields can be described by binomial ideals each of which given as the sum of a toric ideal and a non-prime ideal. This description allows to study linear codes by methods from commutative algebra and algebraic geometry. The strength of this approach lies in the fact that the investigations can be made over any field and so particularly over an algebraically closed field of characteristic 0, which is the most comfortable situation in commutative algebra and algebraic geometry.

First, minimal generators of the binomial ideal of a code have been studied. The situation has turned out to be quite similar to the toric case. In the binary situation, the Graver bases, the universal Groebner bases, and the set of circuits of the binomial ideal are essentially equal.

Second, we have shown that the binomial ideal associated with a linear code has a very natural Groebner basis with respect to the lexicographic order requiring that any monomial containing one of the information symbols is larger than any monomial containing only parity check symbols. We have also illustrated that Groebner bases for linear codes provide a very compact representation of the encoding and decoding functions.

Third, we have studied the affine varieties of the binomial ideals associated with linear codes and minimal primary decompositions of these ideals.

Finally, we have described the binomial ideals of linear codes in terms of their syzygy modules and the corresponding finite free resolutions.

By the way, Groebner bases were first used in coding theory by Cooper providing a decoder for cyclic codes. Then the application of Groebner basis computations to the study of linear codes became an active field of study.

Originally, the method of Groebner bases was introduced by Buchberger for the algorithmic solution of some of the fundamental problems in commutative algebra. Today, Groebner bases provide a uniform approach to solving a wide range of problems expressed in terms of sets of multivariate polynomials such as the solvability and solving algebraic systems of equations, ideal and radial membership decision, effective computation in residue class rings modulo polynomial ideals, linear diophantine equations with polynomial coefficients, algebraic relations among polynomials, implicitization, and inverse polynomial mappings.

AMS Subject Classification: 13P10, 94B05

Key Words: commutative polynomial rings - binomial ideals - Groebner bases - linear codes - encoding and decoding.

Literature:

• M. Saleemi, K.-H. Zimmermann: Groebner bases for a class of ideals in commutative polynomial rings. Int. J. Pure Appl. Math., vol. 58, no. 1, 1-9, 2010.
• M. Saleemi, K.-H. Zimmermann: Linear codes as binomial ideals. Int. J. Pure Appl. Math., vol. 61, no. 2, 2010.
• M. Saleemi, K.-H. Zimmermann: Groebner bases for linear codes. Int. J. Pure Appl. Math., vol. 62, no. 4, 481-491, 2010.
• M. Saleemi, K.-H. Zimmermann: Syzygies and free resolutions of linear codes. Int. Electr. J. Pure Appl. Math., to appear
• M. Saleemi, K.-H. Zimmermann: Primary decompositions of linear codes. Int. Electr. J. Pure Appl. Math., submitted.