Search

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using $\tilde{\mathcal {O}} (s\ell ^{\omega }\mu ^{\omega -1}(n+g))$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell $ is the designed list size and $\mu $ is the smallest positive element in the Weierstrass semigroup at some chosen place; the “soft-O” notation $\tilde{\mathcal {O}} (\cdot)$ is similar to the “big-O” notation $\mathcal {O}(\cdot)$ , but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series. [ABSTRACT FROM AUTHOR]

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called $C_{ab}$ curves, as well as algorithms for inverting the encoding map, which we call “unencoding”. Some $C_{ab}$ curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity $ \tilde { \mathcal {O}}(\text {n}^{3/2})$ resp. $ \tilde { \mathcal {O}}({\it\text { qn}})$ for AG codes over any $C_{ab}$ curve satisfying very mild assumptions, where n is the code length and q the base field size, and $ \tilde { \mathcal {O}}$ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, for example the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity $ \tilde { \mathcal {O}}(\text {n})$ for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse-Weil bound, our encoding and unencoding algorithms have complexities $ \tilde { \mathcal {O}}(\text {n}^{5/4})$ and $ \tilde { \mathcal {O}}(\text {n}^{3/2})$ respectively. [ABSTRACT FROM AUTHOR]

We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami–Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities. [ABSTRACT FROM AUTHOR]

We derive the Wu list-decoding algorithm for generalized Reed–Solomon (GRS) codes by using Gröbner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp–Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami–Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes. [ABSTRACT FROM PUBLISHER]

Abstract: A Reed–Solomon code of length can be list decoded using the well-known Guruswami–Sudan algorithm. By a result of the interpolation part in this algorithm can be done in complexity , where denotes the designed list size and the multiplicity parameter. The parameters and are sometimes considered to be constants in the complexity analysis, but for high rate Reed–Solomon codes, their values can be very large. In this paper we will combine ideas from and the concept of key equations to get an algorithm that has complexity . This compares favorably to the complexities of other known interpolation algorithms. [Copyright &y& Elsevier]