# Singular

### C.8.5 Decoding method based on quadratic equations

#### Preliminary definitions

Let be a basis of and let be the matrix with as rows. The unknown syndrome of a word w.r.t is the column vector with entries for .

For two vectors define . Then is a linear combination of , so there are constants such that The elements are the structure constants of the basis .

Let be the matrix with as rows (). Then is an ordered MDS basis and an MDS matrix if all the submatrices of have rank for all .

#### Expressing known syndromes

Let be an -linear code with parameters . W.l.o.g . is a check matrix of . Let be the rows of . One can express with some . In other words where is the matrix with entries .

Let be a received word with and an error vector. The syndromes of and w.r.t are equal and known:

They can be expressed in the unknown syndromes of w.r.t :

since and .

#### Contructing the system

Let be an MDS matrix with structure constants . Define in the variables by

The ideal in is generated by

The ideal in is generated by

Let be the ideal in generated by and .

#### Main theorem

Let be an MDS matrix with structure constants . Let be a check matrix of the code such that as above. Let be a received word with the codeword sent and the error vector. Suppose that and . Let be the smallest positive integer such that has a solution over the algebraic closure of . Then

• and the solution is unique and of multiplicity one satisfying .
• the reduced Gröbner basis for the ideal w.r.t any monomial ordering is

where is the unique solution.

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