Details:
Title  The ChenReedHellesethTruong Decoding Algorithm and the
GianniKalkbrenner Shape Theorem  Author(s)  Massimo Caboara, Ferdinando Mora  Type  Article in Journal  Abstract  In a paper from Chen, Reed, Helleseth and Truong, (cf.
also Lousteanaou and York ) Gr\"obner bases are applied as a
preprocessing tool in order to devise an algorithm for decoding a
cyclic code over $GF(q)$ of length $n$. The \Gr\ basis
computation of a suitable ideal allows us to produce two finite
ordered lists of polynomials over $GF(q)$,
$$
\{\Gamma_i(X_1,\ldots,X_s)\}\text{\ and\ }\{G_i(X_1,\ldots,X_s, Z)\};
$$
upon the receipt of a codeword, one needs to compute the syndromes
$\{{\sf s}_1,\ldots,{\sf s}_s\}$ and then to compute the maximal
value of the index $i$ s.t. $\Gamma_i({\sf s}_1,\ldots,{\sf s}_s) = 0$;
the error locator polynomial is then
$$
\gcd(G_i({\sf s}_1,\ldots,{\sf s}_s, Z), Z^n1).
$$
The algorithm proposed in Chen, Reed Helleseth and Truong needs the assumption that
the computed Gr\"obner basis associated to a cyclic code has a particular structure; this
assumption is not satisfied by every cyclic code.
However the structure of the
Gr\"obner basis of a $0$dimensional ideal has been deeply
analyzed by Gianni and Kalkbrenner. Using these
results we were able to generalize the idea of Chen, Reed,
Helleseth and Truong to all cyclic codes.
 Length  22 
File 
 Language  English  Journal  Applicable Algebra in Engineering, Communications and Computing  Volume  13  Number  3  Pages  209232  Publisher  Springer  Year  2002  Edition  0  Translation 
No  Refereed 
Yes 
