Singular Manual: Decoding method based on quadratic equations

Forward: References for decoding with Groebner bases

C.8.5 Decoding method based on quadratic equations

Preliminary definitions

Let ${\bf b}_1,\dots,{\bf b}_n$ be a basis of and let be the $n\times n$ matrix with ${\bf b}_1,\dots,{\bf b}_n$ as rows. The unknown syndrome ${\bf u}(B,{\bf e})$ of a word ${\bf e}$ w.r.t is the column vector ${\bf u}(B,{\bf e})=B{\bf e}^T$ with entries $u_i(B,{\bf e})={\bf b}_i\cdot {\bf e}$ for $i=1,\dots,n$ .

For two vectors ${\bf x,y} \in F_q^n$ define ${\bf x*y}=(x_1y_1,\dots,x_ny_n)$ . Then ${\bf b}_i*{\bf b_j}$ is a linear combination of ${\bf b}_1,\dots,{\bf b}_n$ , so there are constants $\mu^{ij}_l\in F_q$ such that ${\bf b}_i*{\bf b}_j = \sum_{l=1}^n \mu^{ij}_l{\bf b}_l.$ The elements $\mu^{ij}_l\in F_q$ are the structure constants of the basis ${\bf b}_1,\dots,{\bf b}_n$ .

Let be the $s \times n$ matrix with ${\bf b}_1,\dots,{\bf b}_s$ as rows (). Then ${\bf b}_1,\dots,{\bf b}_n$ is an ordered MDS basis and an MDS matrix if all the $s\times s$ submatrices of have rank for all $s=1 ,\dots ,n$ .

Expressing known syndromes

Let

be an

-linear code with parameters

. W.l.o.g $n\le q$ .

is a check matrix of

. Let ${\bf h}_1,\dots,{\bf h}_{n-k}$ be the rows of

. One can express ${\bf h}_i = \sum _{j=1}^n a_{ij}{\bf b}_j$ with some $a_{ij}\in F_q$ . In other words

where

is the $(n-k) \times n$ matrix with entries $a_{ij}$ .

Let ${\bf r}={\bf c}+{\bf e}$ be a received word with ${\bf c}\in C$ and ${\bf e}$ an error vector. The syndromes of ${\bf r}$ and ${\bf e}$ w.r.t are equal and known:

$\begin{displaymath} s_i({\bf r}):={\bf h}_i \cdot {\bf r}={\bf h}_i\cdot {\bf e}=s_i({\bf e}). \end{displaymath}$

They can be expressed in the unknown syndromes of ${\bf e}$ w.r.t

$\begin{displaymath} s_i({\bf r})=s_i({\bf e}) =\sum _{j=1}^n a_{ij}u_j({\bf e}) \end{displaymath}$

since ${\bf h}_i = \sum _{j=1}^n a_{ij}{\bf b}_j$ and ${\bf b}_j \cdot {\bf e}=u_j({\bf e})$ .

Contructing the system

Let be an MDS matrix with structure constants $\mu^{ij}_l$ . Define $U_{ij}$ in the variables $U_1, \dots ,U_n$ by

$\begin{displaymath} U_{ij}=\sum _{l=1}^n \mu^{ij}_lU_l. \end{displaymath}$

The ideal $J({\bf r})$ in $F_q[U_1,\dots,U_n]$ is generated by

$\begin{displaymath} \sum_{l=1}^n a_{jl}U_l-s_j({\bf r}) \hbox{ for } j=1,\dots,n-k. \end{displaymath}$

The ideal

in $F_q[U_1,\dots,U_n,V_1,\dots,V_t]$ is generated by

$\begin{displaymath} \sum_{j=1}^t U_{ij}V_j-U_{i,t+1} \hbox{ for } i=1,\dots,n \end{displaymath}$

Let $J(t,{\bf r})$ be the ideal in $F_q[U_1,\dots,U_n,V_1,\dots,V_t]$ generated by $J({\bf r})$ and

Main theorem

Let be an MDS matrix with structure constants $\mu^{ij}_l$ . Let be a check matrix of the code such that as above. Let ${\bf r}={\bf c}+{\bf e}$ be a received word with ${\bf c}\in C$ the codeword sent and ${\bf e}$ the error vector. Suppose that $wt({\bf e})\ne 0$ and $wt({\bf e})\le\lfloor (d(C)-1)/2\rfloor$ . Let be the smallest positive integer such that $J(t,{\bf r})$ has a solution $({\bf u,v})$ over the algebraic closure of . Then

$wt({\bf e})=t$ and the solution is unique and of multiplicity one satisfying ${\bf u}={\bf u}({\bf e})$ .
the reduced Gröbner basis for the ideal $J(t,{\bf r})$ w.r.t any monomial ordering is

$\begin{displaymath} U_i-u_i({\bf e}), i=1,\dots,n, \end{displaymath}$

$\begin{displaymath} V_j-v_j, j=1,\dots,t, \end{displaymath}$

where $({\bf u}({\bf e}),{\bf v})$ is the unique solution.

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

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