Top
Back: Generalized Newton identities
Forward: Decoding method based on quadratic equations
FastBack: Non-commutative algebra
FastForward: References
Up: Decoding codes with Groebner bases
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

C.8.4 Fitzgerald-Lax method

Affine codes

Let $I=\langle g_1,\dots,g_m \rangle \subseteq F_q[X_1,\dots,X_s]$ be an ideal. Define

\begin{displaymath}
I_q:=I+\langle X_1^q-X_1,\dots,X_s^q-X_s\rangle .
\end{displaymath}

So $I_q$ is a zero-dimensional ideal. Define also $V(I_q)=:\{P_1,\dots,P_n\}$. Every $q$-ary linear code $C$ with parameters $[n,k]$ can be seen as an affine variety code $C(I,L)$, that is, the image of a vector space $L$ of the evaluation map

\begin{displaymath}
\phi :R\to F_q ^n
\end{displaymath}


\begin{displaymath}
\bar{f}\mapsto(f(P_1),\dots,f(P_n)),
\end{displaymath}

where $R:=F_q[U_1,\dots,U_s]/I_q$, $L$ is a vector subspace of $R$ and $\bar{f}$ the coset of $f$ in $F_q[U_1,\dots,U_s]$ modulo $I_q$.

Decoding affine variety codes

Given a $q$-ary $[n,k]$ code $C$ with a generator matrix $G=(g_{ij})$:

  1. choose $s$, such that $q^s\ge n$, and construct $s$ distinct points $P_1,\dots,P_s$ in $F_q^s$.
  2. Construct a Gröbner basis $\{g_1,\dots,g_m\}$ for an ideal $I$ of polynomials from $F_q[X_1,\dots,X_s]$ that vanish at the points $P_1,\dots,P_s$. Define $\xi_i\in F_q[X_1,\dots,X_s]$ such that $\xi_i(P_i)=1,\xi_i(P_j)=0,i\ne j$.
  3. Then $f_i=\sum_{i=1}^ng_{ij}\xi_j$ span the space $L$, so that $g_{ij}=f_i(P_j)$.

In this way we obtain that the code $C$ is the image of the evaluation above, thus $C=C(I,L)$. 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 $(g_l(X_{k1},\dots,X_{ks}))_{l=1,\dots,m; k=1,\dots,t}$ for every error position. We also assume that field equations on $X_{ij}$'s are included among the polynomials above. Let $C$ be a $q$-ary $[n,k]$ linear code such that its dual is written as an affine variety code of the form $C^{\bot}=C(I,L)$. Let ${\bf r}={\bf c}+{\bf e}$ as usual and $t\le e$. Then the syndromes are computed by $s_i=\sum_{j=1}^nr_jf_i(P_j)=\sum_{j=1}^ne_jf_i(P_j)
\hbox{ for } i=1,\dots,n-k$.

Consider the ring $F_q[X_{11},\dots,X_{1s},\ldots,X_{t1},\dots,X_{ts},E_1,\dots,E_t]$, where $(X_{i1},\dots,X_{is})$ correspond to the $i$-th error position and $E_i$ to the $i$-th error value. Consider the ideal $Id_C$ generated by

\begin{displaymath}
\sum_{j=1}^tE_jf_i(X_{j1},\dots,X_{js})-s_i, 1\le i\le n-k,
\end{displaymath}


\begin{displaymath}
g_l(X_{j1},\dots,X_{js}), 1\le l\le m,
\end{displaymath}


\begin{displaymath}
E_k^{q-1}-1.
\end{displaymath}

Theorem:
Let $G$ be the reduced Gröbner basis for $Id_C$ with respect to an elimination order $X_{11}<\dots<X_{1s}<E_1$. Then we may solve for the error locations and values by applying elimination theory to the polynomials in $G$.

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


Top Back: Generalized Newton identities Forward: Decoding method based on quadratic equations FastBack: Non-commutative algebra FastForward: References Up: Decoding codes with Groebner bases Top: Singular Manual Contents: Table of Contents Index: Index About: About this document
            User manual for Singular version 4-0-3, 2016, generated by texi2html.