Singular

C.8.4 Fitzgerald-Lax method

Affine codes

Let be an ideal. Define

So is a zero-dimensional ideal. Define also . Every -ary linear code with parameters can be seen as an affine variety code , that is, the image of a vector space of the evaluation map

where , is a vector subspace of and the coset of in modulo .

Decoding affine variety codes

Given a -ary code with a generator matrix :

1. choose , such that , and construct distinct points in .
2. Construct a Gröbner basis for an ideal of polynomials from that vanish at the points . Define such that .
3. Then span the space , so that .

In this way we obtain that the code is the image of the evaluation above, thus . In the same way by considering a parity check matrix instead of a generator matrix we have that the dual code is also an affine variety code.

The method of decoding is a generalization of CRHT. One needs to add polynomials for every error position. We also assume that field equations on 's are included among the polynomials above. Let be a -ary linear code such that its dual is written as an affine variety code of the form . Let as usual and . Then the syndromes are computed by .

Consider the ring , where correspond to the -th error position and to the -th error value. Consider the ideal generated by

Theorem:
Let be the reduced Gröbner basis for with respect to an elimination order . Then we may solve for the error locations and values by applying elimination theory to the polynomials in .

For an example see sysFL in decodegb_lib. More on this method can be found in [FL1998].