The Chen-Reed-Helleseth-Truong Decoding Algorithm and the Gianni-Kalkbrenner Shape Theorem

In a paper from Chen, Reed, Helleseth and Truong, [4] (cf. also Loustaunau andYork [10]) Grobner 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 Grobner basis computation of a suitable ideal allows us to produce two finite ordered lists of polynomials over GF(q), {Gamma(i)(X-1,..., X-s)} and {G(i)(X-1,..., X-s, Z)}; upon the receipt of a codeword, one needs to compute the syndromes {s(1),..., s(s)} and then to compute the maximal value of the index i s.t. Gamma(i)(s(1),..., s(s)) = 0; the error locator polynomial is then gcd(G(i)(s(1),..., s(s), Z), Z(n) - 1). The algorithm proposed in [4] needs the assumption that the computed Grobner basis associated to a cyclic code has a particular structure; this assumption is not satisfied by every cyclic code. However the structure of the Grobner basis of a 0-dimensional ideal has been deeply analyzed by Gianni [7] and Kalkbrenner [8]. Using these results we were able to generalize the idea of Chen, Reed, Helleseth and Truong to all cyclic codes.