Fast Decoding of AG Codes
Peter Beelen, Johan Rosenkilde, Grigory Solomatov · IEEE Transactions on Information Theory · 2022
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.