Home Online Manual
Top
Back: Codes and the decoding problem
Forward: Generalized Newton identities
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.2 Cooper philosophy

Computing syndromes in cyclic code case

Let $C$ be an $[n,k]$ cyclic code over $F_q$; $F$ is a splitting field with $a$ being a primitive n-th root of unity. Let $S_C=\{i_1,\dots,i_{n-k}\}$ be the complete defining set of $C$. Let ${\bf r}={\bf c}+{\bf e}$ be a received word with ${\bf c}\in C$ and ${\bf e}$ an error vector. Denote the corresponding polynomials in $F_q[x]/\langle x^n-1 \rangle$ by $r(x)$, $c(x)$ and $e(x)$, resp. Compute syndromes

\begin{displaymath} s_{i_m}=r(a^{i_m})=e(a^{i_m})= \sum_{l=1}^{t}e_{j_l}(a^{i_m})^{j_l}, \ \ 1\le m \le n-k, \end{displaymath}

where $t$ is the number of errors, $j_1,\dots,j_t$ are the error positions and $e_{j_1},\dots,e_{j_t}$ are the error values. Define $z_l=a^{j_l}$ and $y_l=e_{j_l}$. Then $z_1,\dots,z_t$ are the error locations and $y_1,\dots,y_t$ are the error values and the syndromes above become generalized power sum functions $s_{i_m}=\sum_{l=1}^{t}y_lz_l^{i_m}, \ \ 1\le m \le n-k. $

CRHT-ideal

Replace the concrete values above by variables and add some natural restrictions. Introduce
  • $f_u := \sum_{l=1}^e Y_lZ_l^{i_u}-X_u=0, 1\le u\le n-k$;
  • $\epsilon_j:=X_j^{q^m}-X_j=0, 1\le j\le n-k,$ since $s_j\in F$;
  • $\eta_i:= Z_i^{n+1}-Z_i=0, 1\le i\le e$, since $a^{j_i}$ are either $n$-th roots of unity or zero;
  • $\lambda_i:=Y_i^{q-1}-1=0, 1\le i\le e$, since $y_l\in F_q \setminus\{0\}$.

We obtain the following set of polynomials in the variables $X=(X_1,\dots,X_{n-k})$, $Z=(Z_1,\dots,Z_e)$ and $Y=(Y_1,\dots,Y_e)$:

\begin{displaymath}F_C=\{f_j,\epsilon_j,\eta_i,\lambda_i:1\le j\le n-k,1\le i\le e\}\subset F_q[X,Z,Y].\end{displaymath}

The zero-dimensional ideal $I_C$ generated by $F_C$ is the CRHT-syndrome ideal associated to the code $C$, and the variety $V(F_C)$ defined by $F_C$ is the CRHT-syndrome variety, after Chen, Reed, Helleseth and Truong.

General error-locator polynomial

Adding some more polynomials to $F_C$, thus obtaining some $F'_C$, it is possible to prove the following Theorem:

Every cyclic code $C$ possesses a general error-locator polynomial $L_C$ from $F_q[X_1,\ldots ,X_{n-k},Z]$ that satisfies the following two properties:

  • $L_C=Z^e+a_{t-1}Z^{e-1}+\dots +a_0$ with $a_j\in F_q[X_1,\dots ,X_{n-k}],\ 0\le j\le e-1$, where $e$ is the error-correcting capacity;
  • given a syndrome ${\bf s}=(s_{i_1},\dots,s_{i_{n-k}})\in F^{n-k}$ corresponding to an error of weight $t\le e$ and error locations $\{k_1,\dots,k_{t}\}$, if we evaluate the $X_u=s_{i_u}$ for all $1\le u \le n-k$, then the roots of $L_C({\bf s},Z)$ are exactly $a^{k_1},\dots,a^{k_t}$ and 0 of multiplicity $e-t$, in other words $L_C({\bf s},Z)=Z^{e-t}\prod_{i=1}^{t}(Z-a ^{k_i}).$

The general error-locator polynomial actually is an element of the reduced Gröbner basis of $\langle F'_C \rangle$. Having this polynomial, decoding of the cyclic code $C$ reduces to univariate factorization.

For an example see sysCRHT in decodegb_lib. More on Cooper's philosophy and the general error-locator polynomial can be found in [OS2005].

Finding the minimum distance

The method described above can be adapted to find the minimum distance of a code. More concretely, the following holds:

Let $C$ be the binary $[n,k,d]$ cyclic code with the defining set $S_C=\{i_1,\dots,i_v\}$. Let $1\le w\le n$ and let $J_C(w)$ denote the system:

\begin{displaymath} Z_1^{i_1}+\dots+Z_w^{i_1}=0, \end{displaymath}


\begin{displaymath} \vdots \end{displaymath}


\begin{displaymath} Z_1^{i_v}+\dots+Z_w^{i_v}=0, \end{displaymath}


\begin{displaymath} Z_1^n-1=0, \end{displaymath}


\begin{displaymath} \vdots \end{displaymath}


\begin{displaymath} Z_w^n-1=0, \end{displaymath}


\begin{displaymath} p(n,Z_i,Z_j)=0, 1\le i<j\le w. \end{displaymath}

Then the number of solutions of $J_C(w)$ is equal to $w!$ times the number of codewords of weight $w$. And for $1\le w\le d$, either $J_C(w)$ has no solutions, which is equivalent to $w<d$, or $J_C(w)$ has some solutions, which is equivalent to $w=d$.

For an example see sysCRHTMindist in decodegb_lib. More on finding the minimum distance with Groebner bases can be found in [S2007]. See [OS2005], for the definition of the polynomial $p$ above.