Decoding affine variety codes using Gröbner bases (Q1378880): Difference between revisions

For an ideal \(I\) of the polynomial ring \(F=F_q[x_1,\dots, x_s]\) over the finite field \(F_q\) with \(q\) elements, let \(I_q\) denote the ideal generated by \(I\) and the polynomials \(x_i^q-x_i\) for all \(i\), and let \(V(I_q) \subseteq F_q^s\) be the affine variety corresponding to \(I_q\). There is defined a canonical mapping \(\phi\) on the factor ring \(R=F/I_q\) to \(F_q^{V(I_q)}\), essentially defined by evaluating a polynomial at the points of the variety. For an \(F_q\)-subspace \(L\) of \(R\), the image \(\phi(L)\) is called the affine variety code corresponding to \(I\) and \(L\). The authors demonstrate that, at least theoretically, one can use the theory of Gröbner bases and elimination theory for decoding affine variety codes up to half the true minimum distance: information on error locators and error values are obtained by inspecting the reduced Gröbner basis of a certain ideal corresponding to \(I_q\) and \(L\) with respect to some lexicographic term order. The authors mention that, due to massive computations, in practice, their (very general) approach might only work for codes over small fields with restricted length. As an example, a Hermitian code with minimum distance \(5\) is considered.