Gröbner Bases over Galois Rings with an Application to Decoding Alternant Codes
✍ Scribed by Eimear Byrne; Patrick Fitzpatrick
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 346 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0747-7171
No coin nor oath required. For personal study only.
✦ Synopsis
We develop a theory of Gröbner bases over Galois rings, following the usual formulation for Gröbner bases over finite fields. Our treatment includes a division algorithm, a characterization of Gröbner bases, and an extension of Buchberger's algorithm. One application is towards the problem of decoding alternant codes over Galois rings. To this end we consider the module M = {(a, b) : aS ≡ b mod x r } of all solutions to the so-called key equation for alternant codes, where S is a syndrome polynomial. In decoding, a particular solution (Σ, Ω) ∈ M is sought satisfying certain conditions, and such a solution can be found in a Gröbner basis of M . Applying techniques introduced in the first part of this paper, we give an algorithm which returns the required solution.