论文标题
AG代码的快速解码
Fast Decoding of AG Codes
论文作者
论文摘要
我们提出了一个有效的列表，该列表以Guruswami-Sudan的样式解码算法，用于代数几何代码。 Our decoder can decode any such code using $\tilde{\mathcal O}(s\ell^ωμ^{ω-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 $μ$ is the smallest Weierstrass Semigroup的积极元素在某个选择的地方； “ soft-o”符号$ \ tilde {\ mathcal o}（\ cdot）$与“ big-o”符号$ {\ mathcal o}（\ cdot）$相似，但忽略了对数因素。对于构成方法的计算瓶颈的插值步骤，我们使用已知算法用于单变量多项式矩阵，而使用现有的单变量求解词根求解单变量的求解步骤。
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^ωμ^{ω-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 $μ$ 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.
