Decoding algebraic-geometric codes by solving a key equation

DOI10.1007/BFB0087989MaRDI QIDQ4027636zbMATH OpenFDO

Authors Dirk Ehrhard

Publication date 21 February 1993

Published in Lecture Notes in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0087989

zbMATH Keywords

algebraic-geometric codesBerlekamp's decoding algorithmkey equation

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Review text

[For the entire collection see Zbl 0745.00062.] This paper investigates a series of preprints by S. C. Porter, where Berlekamp's decoding algorithm is generalized to the case of a small class of Algebraic-Geometric Codes. The main step of this algorithm is to solve a so-called ``key-equation. Here, it is shown how to generalize this concept to all Algebraic- Geometric Codes and moreover, how to solve the key equation by simple linear algebra operations. Two observations on Porter's methods have motivated the paper: 1. The operations done by Porters algorithm at the so-called ``resultant-matrix, may be considered as a Gaussian algorithm, applied to the transposed matrix. 2. The key equation may be reviewed as linear. The result is a decoding algorithm of complexity order \(O(n^ 3)\), that corrects up to \(\left\lfloor{1\over 2}(d^*-1-g)\right\rfloor\) errors, exactly as the well-known algorithm does. (\(d^*\) is the designed minimum distance of the code, \(n\) its length, and \(g\) the genus of the underlying curve). Moreover, it is shown that both algorithms are equivalent is some reasonable manner.

Recommendations

• Decoding algebraic geometry codes by a key equation
• On the decoding of algebraic-geometric codes
• Decoding algebraic-geometric codes up to the designed minimum distance
• Decoding geometric Goppa codes up to designed minimum distance by solving a key equation in a ring
• Simplified understanding and efficient decoding of a class of algebraic-geometric codes

Cited in

(5)

• Solving a congruence on a graded algebra by a subresultant sequence and its application
• Decoding algebraic geometry codes by a key equation
• The key equation for one-point codes and efficient error evaluation
• scientific article; zbMATH DE number 1559532 (Why is no real title available?)
• Decoding geometric Goppa codes up to designed minimum distance by solving a key equation in a ring

This page was built for publication: Decoding algebraic-geometric codes by solving a key equation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027636)