Hamming metric decoding of alternant codes over Galois rings

The standard decoding procedure for alternant codes over fields centers on solving a key equation which relates an error locator polynomial and an error evaluator polynomial by a syndrome sequence. We extend this technique to decode alternant codes over Galois rings. We consider the module M={(a, b): as≡b mod x^r} of all solutions to the key equation where s is the syndrome polynomial and r, is the number of rows in a parity-check matrix for the code. In decoding we seek a particular solution (Σ, Ω)∈M which we prove can be found in a Grobner basis for M. We present an iterative algorithm which generates a Grobner basis modulo x^k+1 from a given basis modulo x^k. At the rth step, a Grobner basis for M is found, and the required solution recovered