Search

This thesis introduces and discusses a new algorithm for solving the key equation for Hermitian codes, that belong to the class of algebraic-geometric (AG) codes. First, the most important concepts of channel coding are recalled and the popular Reed-Solomon (RS) codes are used to illustrate them. The decoding of RS codes with the extended Euclidean algorithm is used to illustrate the basic idea of algebraic decoding and motivate the new decoding algorithm. After that, some elementary results from algebraic geometry, that are (directly or indirectly) used in the definition of AG codes, are introduced. From the definition of general AG codes, RS codes and Hermitian codes are derived as special cases. An alternative definition of Hermitian codes that uses almost no algebraic geometry is also given. After that, the key equation for Hermitian codes is presented. For a limited error weight, it has a unique solution of minimal degree, and the error pattern can be reconstructed from this solution. An algorithm that finds this solution of minimal degree is given. But this algorithm is not capable of decoding all error patterns with weight up to half the minimum distance - a bound up to which unique decoding is guaranteed by the properties of general linear codes. An extension that achieves this decoding radius is discussed afterwards, and the complexity of both the algorithm and its extension are estimated. A modification of the algorithm that returns a basis for decoding beyond half the minimum distance is given in the last chapter. However, decoding up to this increased radius without (significantly) increasing the complexity is not always possible. A bound on the error weight that allows such decoding for interleaved Hermitian codes with high probability is derived, as well as the probability that decoding fails. Finally, the idea of virtual extension to an interleaved code is described. This principle works only for codes with low rates, and the rate bound is given.

International audience; In this paper we investigate two new decoding schemes for Reed-Solomon codes, which allow to decode beyond half the minimum distance. One is Sudan's list-decoding principle, based on interpolation with a degree-restricted bivariate polynomial. We show a syndrome-based approach of it. We compare Sudan's procedure with a scheme that is based on an extension to Interleaved Reed-Solomon codes. We present theoretical parallels and outline both algorithms in a unique comparable way. Furthermore, we show the connection of both schemes to the classical Linear Feedback Shift Register analysis. Afterwards, we compare the performance of the considered schemes.