Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOn the Decoding of Cyclic Codes Using Gröbner Bases
Author(s) Philippe Loustaunau, Eric V. York
TypeArticle in Journal
AbstractIn this paper we revisit an algorithm presented by Chen, Reed, Helleseth, and Troung in [5] for decoding cyclic codes up to their true minimum distance using Gröbner basis techniques. We give a geometric characterization of the number of errors, and we analyze the corresponding algebraic characterization. We give a characterization for the error locator polynomial as well. We make these ideas effective using the theory of Gröbner bases. We then present an algorithm for computing the reduced Gröbner basis over ¶2 for the syndrome ideal of cyclic codes, with respect to a lexicographic term ordering. This algorithm does not use Buchberger's algorithm or the multivariable polynomial division algorithm, but instead uses the form of the generators of the syndrome ideal and an adaptation of the algorithm introduced in [11]. As an application of this algorithm, we present the reduced Gröbner basis for the syndrome ideal of the [23,r12,r7] Golay code, and a decoding algorithm.
Keywordsdecoding, cyclic codes, Gröbner basis, zero-dimensional ideals
URL dx.doi.org/10.1007/s002000050084
JournalApplicable Algebra in Engineering, Communication and Computing
PublisherSpringer-Verlag GmbH
Translation No
Refereed No