ISSN:
1432-0622
Keywords:
Keywords: Decoding
;
Cyclic codes
;
Gröbner basis
;
Zero-dimensional ideals.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract. In 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, 12, 7] Golay code, and a decoding algorithm.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002000050084
Permalink