Seminar: Constructive Algebraic Geometry

Topics:

• Evaluation codes.
• Reed-Muller codes and Reed-Solomon codes as evaluation codes.
• Hermitian codes.
• A result of van Lint on evaluation codes.

Seminar: Constructive Algebraic Geometry

Topics:

• projective n-space
• homogeneous ideals
• projective algebraic sets
• Zariski topology
• irreducibility and dimension

Computational Biology - Lecture 12

Yesterday, we resumed with the introduction into algebraic geometry:

• ideal-variety correspondence,
• elimination theorem,
• extension theorem.

Computational Biology - Lecture 10

Today, we will finish the topic on Groebner bases:

• Minimal Groebner bases,
• Reduced Groebner bases,
• Buchberger's S-criterion,
• Buchberger's algorithm.

Reed-Muller Codes - Revisited

Recently, we published the article:

• From Ideals in Polynomial Rings to Linear Codes Using Groebner Bases, Int. J. Pure Applied Math., vol. 65, no. 1, pp. 41-53, 2010.

This paper studies linear codes as ideals in the group algebra over an elementary abelian p-group. These codes are described in terms of Groebner bases and corresponding encoding and decoding procedures are given. It is shown that the class of codes studied contains an interesting family of linear codes. These codes have a designed Hamming distance and turn out to be superior to the primitive Reed-Muller codes in the non-binary case.

Computational Biology - Lecture 9

Today, the basics of Groebner bases were presented including test of ideal membership, uniqueness of division, existence of Groebner bases, and Hilbert's basis theorem.

Reed-Muller Codes Revisited

Recently, we studied linear codes as ideals in the group algebra over an elementary abelian p-group. These codes can be described in terms of Groebner bases which in turn provide encoding and decoding procedures. In particular, we investigated generalizations of primitive Reed-Muller codes and constructed corresponding Groebner bases. We also showed that the class of codes studied contains an interesting family of linear codes. These codes have a designed Hamming distance and turn out to be superior to the primitive Reed-Muller codes in the non-binary case.

AMS Subject Classification: 13P10, 94B05

Keywords: Commutative polynomial rings, ideals, Groebner bases, Reed-Muller codes, decoding.

M. Saleemi, K.-H. Zimmermann: From Ideals in Polynomial Rings to Linear Codes using Groebner Bases. Int. J. Pure Appl. Math., to appear.

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.