Accession Number:

ADA273089

Title:

Toward a New Method of Decoding Algebraic Codes Using Groebner Bases

Descriptive Note:

Final rept. Oct 1991-Sep 1992

Corporate Author:

ARMY RESEARCH LAB ABERDEEN PROVING GROUND MD

Personal Author(s):

Report Date:

1993-10-01

Pagination or Media Count:

28.0

Abstract:

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 GF2m. It is decoded by computing a set of syndrome equations which are multivariate polynomials over GF2m 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 GF2m. 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

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE