
C.8.5 Decoding method based on quadratic equationsPreliminary definitionsLet 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 syndromesLet 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 theoremLet 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
For an example see 