1. Fast Decoding of AG Codes.
- Author
-
Beelen, Peter, Rosenkilde, Johan, and Solomatov, Grigory
- Subjects
- *
ALGEBRAIC geometry , *FINITE fields , *DECODING algorithms , *DECODERS & decoding , *POWER series , *MULTIPLICITY (Mathematics) , *ALGEBRAIC codes , *ALGORITHMS , *INTERPOLATION - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF