Toward a New Method of Decoding Algebraic Codes Using Groebner Bases.

摘要

A binary BCH error control code is a vector subspace of binary N-tuples. Algebraically, the code is generated by a polynomial having binary coefficients and roots in GF(2m). It is decoded by computing a set of syndrome equations which are multivariate polynomials over GF(2m) and which exhibit a certain symmetry. If the number of transmission errors in a received word does not exceed a bound t for the code, the roots of the syndromes are the locations, in the received word, of those errors. These multivariate polynomials are taken as the basis for an ideal in the ring of polynomials in t variables over GF(2m). A celebrated algorithm by Buchberger produces a reduced Groebner basis of that ideal. It tums out that, since the common roots of all the polynomials in the ideal are a set of isolated points, this reduced Groebner basis is in triangular form, and the univariate polynomial in that basis is the well known BCH error locator polynomial, the roots of which specify the error locations. Decoding is algorithmically complete when this polynomial is known. Decoding, Algebraic functions, Polynomials.