Home Online Manual
Top
Back: Fitzgerald-Lax method
Forward: References for decoding with Groebner bases
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.5 Decoding method based on quadratic equations

Preliminary definitions

Let ${\bf b}_1,\dots,{\bf b}_n$ be a basis of $F_q^n$ and let $B$ 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 $B$ 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 $B_s$ be the $s \times n$ matrix with ${\bf b}_1,\dots,{\bf b}_s$ as rows ($B=B_n$). Then ${\bf b}_1,\dots,{\bf b}_n$ is an ordered MDS basis and $B$ an MDS matrix if all the $s\times s$ submatrices of $B_s$ have rank $s$ for all $s=1 ,\dots ,n$.

Expressing known syndromes

Let $C$ be an $F_q$-linear code with parameters $[n,k,d]$. W.l.o.g $n\le q$. $H$ is a check matrix of $C$. Let ${\bf h}_1,\dots,{\bf h}_{n-k}$ be the rows of $H$. 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 $H=AB$ where $A$ 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 $H$ 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 $B$:

\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 $B$ 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 $I(t,U,V)$ 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 $I(t,U,V)$.

Main theorem

Let $B$ be an MDS matrix with structure constants $\mu^{ij}_l$. Let $H$ be a check matrix of the code $C$ such that $H=AB$ 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 $t$ be the smallest positive integer such that $J(t,{\bf r})$ has a solution $({\bf u,v})$ over the algebraic closure of $F_q$. 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 $G$ 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].