, currently used in various applications such as CD technology,
the syndromes are
The application of algebraic geometry to coding theory started in the 80's with the work of Goppa (see Coding Theory and Algebraic Geometry : an Interplay in this series), with curves over finite fields proving to be a source of good codes. In decoding these codes, it gradually became clear that the approach needed was more in terms of (multivariate) polynomial ideals, than in terms of the vector spaces related to divisors from the algebraic geometry approach. Indeed, the main problem of finding error positions, was a question of finding the variety of points associated with an particular ideal, with the ideal produced by finding a minimal Gröbner basis relative to a particular TDEG (total degree) type ordering. This is recent and exciting research, with an obvious application.
The general decoding problem for any code, is to take a received word (that is, a corrupted code word) and produce (efficiently) the nearest code word to it (or equivalently the smallest error possible). For linear codes (subspaces), this is generally done by using functions of the received word which only depend on the error, not on the specific code word transmitted. Such functions are called syndromes.
For Reed-Solomon codes over , currently used in various applications such as CD technology,
the syndromes are
with 
the given received word, and 
a primitve element of 
.
One then uses a Berlekamp-Massey algorithm (or the extended Euclidean algorithm)
to produce an error-locator polynomial 
(or an error-evaluator polynomial).
Then one has a choice of producing all 
,
(by viewing 
as a recurrence relation and the given syndromes as initial conditions)
and using an inverse transform,
with 
the (most likely) error
or
factoring 
, producing 
,
and using Forney's formula:
Algebraic-geometric codes (the duals of those described in ``Coding Theory and Algebraic Geometry: An Interplay'') are generalizations of the Reed-Solomon codes above. As such, there should be an efficient decoding scheme that is modelled on the algorithm above. The first important algorithm in this process was the generalization of the Berlekamp-Massey algorithm to higher dimensions, published in the late 80's by Sakata. This lead to reasonably efficient vector-space based techniques, each with some flaws, either in the number of errors, number of points, or efficiency. The next important idea was published in 93 by Feng and Rao. This majority voting scheme allowed for production of more ``syndromes'' while row-reducing the syndrome matrix. Only recently has this been synthesized into a generalization of the above algorithm.
The syndromes are
for a vector space basis of parity-check functions f.
A version of Sakata's algorithm with efficient majority voting can be used to produce an ideal basis B for the error-locator ideal I whose variety is precisely the set of error positions. B is actually a minimal Gröbner basis relative to a specific TDEG type ordering on the variables.
As before there are two ways to proceed from this point.
The first is to use these basis elements as recurrence relations to produce all syndromes 
.
Then one can use a generalized inverse transform to produce both error positions and error-magnitudes.
The second is to change to a PLEX (pure lexicographic) type minimal Gröbner basis,
from which it is relatively easy to read off the variety of error-positions by finding roots of single variable polynomials.
Then one can use general Forney functions 
,(that is, functions which are zero at all error positions except P),
obtained as a by-product of the basis change,to produce the errors
as before.
There are still many open questions in this area. Those possibly dealing with Gröbner bases would be to show that the complexity of the change of basis approach is as good or better than the inverse transform approach, and that it can be applied to curves not necessarily in special position (as currently required by the Feng-Rao majority vote). It may also be that by viewing decoding in terms of ideals and Gröbner bases, it will be clear which codes will perform best relative to which point sets and designed distances. And this may provide even further feed-back into decoding of BCH codes beyond the BCH bound as well. There may even be an efficient way to produce optimal Forney functions.
Most of the literature in this area appears in the IEEE Transactions on Information Theory. The history of decoding research in this area is covered quite nicely in the introduction of a survey paper by Hø holdt and Pellikaan, which also has an extensive bibliography. A good synthesis with mention of ideals can be found in the IEEE paper by Saints and Heegard, though the general algorithm above is from the author's work to be published in said IEEE journal.
Thu Sep 28 09:58:04 CDT 1995