# 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

# Descriptors:

# Subject Categories:

- Numerical Mathematics