Details:
Title | The Chen-Reed-Helleseth-Truong Decoding Algorithm and the
Gianni-Kalkbrenner 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^n-1).
$$
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 | 209-232 | Publisher | Springer | Year | 2002 | Edition | 0 | Translation |
No | Refereed |
Yes |
|