Home Online Manual
Top
Back: Cooper philosophy
Forward: Fitzgerald-Lax method
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.3 Generalized Newton identities

The error-locator polynomial is defined by

\begin{displaymath}
\sigma(Z)=\prod_{l=1}^{t}(Z-z_l).
\end{displaymath}

If this product is expanded,

\begin{displaymath}
\sigma(Z)=Z^t+\sigma_1Z^{t-1}+\dots+\sigma_{t-1}Z+\sigma_t,
\end{displaymath}

then the coefficients $\sigma_i$ are the elementary symmetric functions in the error locations $z_1,\dots,z_t$

\begin{displaymath}
\sigma_i=(-1)^i\sum_{1\le j_1<j_2<\dots<j_i\le t}z_{j_1}z_{j_2}\dots z_{j_i}, \ 1\le i\le t.
\end{displaymath}

Generalized Newton identities

The syndromes $s_i=r(a^i)=e(a^i)$ and the coefficients $\sigma_i$ satisfy the following generalized Newton identities:

\begin{displaymath}
s_i+\sum_{j=1}^{t}\sigma_js_{i-j}=0,\ \ \hbox{ for all } \ i\in Z\!\!\! Z_n.
\end{displaymath}

Decoding up to error-correcting capacity

We have $ s_{i+n}=s_i, \hbox{ for all } i\in Z\!\!\! Z_n$, since $s_{i+n}=r(a^{i+n})=r(a^i)$. Furthermore

\begin{displaymath}
s_i^q=(e(a^i))^q=e(a^{iq})=s_{qi}, \hbox{ for all } i \in Z_n,
\end{displaymath}

and $\sigma_i^{q^m}=\sigma_i, \hbox{ for all } 1\le i \le t$. Replace the syndromes by variables and obtain the following set of polynomials $Newton_t$ in the variables $S_1,\dots,S_n$ and $\sigma_1,\dots,\sigma_t$:

\begin{displaymath}
\sigma_i^{q^m}-\sigma_i, \ \ \forall \ 1\le i \le t,
\end{displaymath}


\begin{displaymath}
S_{i+n}-S_i, \ \ \forall \ i\in Z\!\!\! Z_n,
\end{displaymath}


\begin{displaymath}
S_i^q-S_{qi}, \ \ \forall \ i\in Z\!\!\! Z_n,
\end{displaymath}


\begin{displaymath}
S_i+\sum_{j=1}^{t}\sigma_jS_{i-j}, \ \ \forall \ i\in Z\!\!\! Z_n,
\end{displaymath}


\begin{displaymath}
S_i-s_i(r) \ \ \forall \ i\in S_C.
\end{displaymath}

For an example see sysNewton in decodegb_lib. More on this method and the method based on Waring function can be found in [ABF2002]. See also [ABF2008].