Singular Manual: Cooper philosophy

C.8.2 Cooper philosophy

Computing syndromes in cyclic code case

Let

be an

cyclic code over

;

is a splitting field with

being a primitive n-th root of unity. Let $S_C=\{i_1,\dots,i_{n-k}\}$ be the complete defining set of

. 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

and

, 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

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 -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

generated by

is the CRHT-syndrome ideal associated to the code

, and the variety

defined by

is the CRHT-syndrome variety, after Chen, Reed, Helleseth and Truong.

General error-locator polynomial

Adding some more polynomials to

, thus obtaining some

, it is possible to prove the following Theorem:

Every cyclic code possesses a general error-locator polynomial 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 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 , 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 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 be the binary cyclic code with the defining set $S_C=\{i_1,\dots,i_v\}$ . Let $1\le w\le n$ and let 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

is equal to

times the number of codewords of weight

. And for $1\le w\le d$ , either

has no solutions, which is equivalent to

, or

has some solutions, which is equivalent to

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 above.

User manual for Singular version 4-0-3, 2016, generated by texi2html.