---
abstract: |
    We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya $C_{ab}$ curves proposed by @lee11 to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by @andersen08 that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is as fast as the BMS algorithm for one-point Hermitian codes, and as a list decoding algorithm it is much faster than the algorithm by @beelen10.\
    **Keywords:** algebraic geometry code, Gröbner basis, list decoding\
    **MSC 2010:** Primary: 94B35; Secondary: 13P10, 94B27, 14G50
author:
- 'Ryutaroh Matsumoto[^1], Diego Ruano[^2],  and Olav Geil'
date: 'April 22, 2013'
title: 'List Decoding Algorithm based on Voting in Gröbner Bases for General One-Point AG Codes'
---

Introduction
============

We consider the list decoding of one-point algebraic geometry (AG) codes. @guruswami99 proposed the well-known list decoding algorithm for one-point AG codes, which consists of the interpolation step and the factorization step. The interpolation step has large computational complexity and many researchers have proposed faster interpolation steps, see [@beelen10 Figure 1].

By modifying the unique decoding algorithm [@lee11] for primal one-point AG codes, we propose another list decoding algorithm based on voting in Gröbner bases whose error correcting capability is higher than [@guruswami99] and whose computational complexity is smaller than [@beelen10; @guruswami99] in many cases. A decoding algorithm for primal one-point AG codes was proposed in [@ldecodepaper], which was a straightforward adaptation of the original Feng-Rao majority voting for the dual AG codes [@fengrao93] to the primal ones. The Feng-Rao majority voting in [@ldecodepaper] for one-point primal codes was generalized to multi-point primal codes in [@beelen08 Section 2.5]. The one-point primal codes can also be decoded as multi-point dual codes with majority voting [@beelen07; @duursma11; @duursma10], whose faster version was proposed in [@sakata11] for the multi-point Hermitian codes. @lee11 proposed another unique decoding (not list decoding) algorithm for primal codes based on the majority voting inside Gröbner bases. The module used by them [@lee11] is a curve theoretic generalization of one used for Reed-Solomon codes in [@kuijper11] that is a special case of the module used in [@lee08]. An interesting feature in [@lee11] is that it did not use differentials and residues on curves for its majority voting, while they were used in [@beelen08; @ldecodepaper]. The above studies [@beelen08; @lee11; @ldecodepaper] dealt with the primal codes. We recently proved in [@gmr13] that the error-correcting capabilities of [@lee11; @ldecodepaper] are the same. The earlier papers [@duursma94; @pellikaan93] suggest that central observations in [@andersen08; @gmr13; @ldecodepaper] were known to the Dutch group, which is actually the case [@duursma12pcomm]. @chen99, @elbrondjensen99 and @amoros06 studied the error-correcting capability of the Feng-Rao [@fengrao93] or the BMS algorithm [@sakata95b; @sakata95a] with majority voting beyond half the designed distance that are applicable to the dual one-point codes.

There was room for improvements in the original result [@lee11], namely, (a) they have not clarified the relation between its error-correcting capability and existing minimum distance lower bounds except for the one-point Hermitian codes, (b) they have not analyzed the computational complexity, (c) they assumed that the maximum pole order used for code construction is less than the code length, and (d) they have not shown how to use the method with the Feng-Rao improved code construction [@feng95]. We shall (1) prove that the error-correcting capability of the original proposal is always equal to half of the bound in [@andersen08] for the minimum distance of one-point primal codes (Proposition \[prop:AG\]), (2) generalize their algorithm to work with any one-point AG codes, (3) modify their algorithm to a list decoding algorithm, (4) remove the assumptions (c) and (d) above, (5) remove unnecessary computational steps from the original proposal, (6) analyze the computational complexity in terms of the number of multiplications and divisions in the finite field. The proposed algorithm is implemented on the Singular computer algebra system [@singular313], and we verified that the proposed algorithm can correct more errors than [@beelen10; @guruswami99] with manageable computational complexity.

This paper is organized as follows: Section \[sec2\] introduces notations and relevant facts. Section \[sec3\] improves [@lee11] in various ways, and the differences to the original [@lee11] are summarized in Section \[sec:diff\]. Section \[sec4\] shows that the proposed modification to [@lee11] works as claimed. Section \[sec:experiment\] compares its computational complexity with the conventional methods. Section \[sec6\] concludes the paper. Part of this paper was presented at 2012 IEEE International Symposium on Information Theory, Cambridge, MA, USA, July 2012 [@gmr12isit].

Notation and Preliminary {#sec2}
========================

Our study heavily relies on the standard form of algebraic curves introduced independently by @geilpellikaan00 and @miura98, which is an enhancement of earlier results [@miura92; @saints95]. Let $F/\mathbf{F}_q$ be an algebraic function field of one variable over a finite field $\mathbf{F}_q$ with $q$ elements. Let $g$ be the genus of $F$. Fix $n+1$ distinct places $Q$, $P_1$, …, $P_n$ of degree one in $F$ and a nonnegative integer $u$. We consider the following one-point algebraic geometry (AG) code $$C_u = \{ {\mathrm{ev}}(f) \mid f \in \mathcal{L}(uQ)\}
\label{eq:cu}$$ where ${\mathrm{ev}}(f) = (f(P_1)$, …, $f(P_n))$. Suppose that the Weierstrass semigroup $H(Q)$ at $Q$ is generated by $a_1$, …, $a_t$, and choose $t$ elements $x_1$, …, $x_t$ in $F$ whose pole divisors are $(x_i)_\infty = a_iQ$ for $i=1$, …, $t$. We do *not* assume that $a_1$ is the smallest among $a_1$, …, $a_t$. Without loss of generality we may assume the availability of such $x_1$, …, $x_t$, because otherwise we cannot find a basis of $C_u$ for every $u$. Then we have that $\mathcal{L}(\infty Q) = \cup_{i=1}^\infty\mathcal{L}(iQ)$ is equal to $\mathbf{F}_q[x_1$, …, $x_t]$ [@saints95]. We express $\mathcal{L}(\infty Q)$ as a residue class ring $\mathbf{F}_q[X_1$, …, $X_t]/I$ of the polynomial ring $\mathbf{F}_q[X_1$, …, $X_t]$, where $X_1$, …, $X_t$ are transcendental over $\mathbf{F}_q$, and $I$ is the kernel of the canonical homomorphism sending $X_i$ to $x_i$. @geilpellikaan00 [@miura98] identified the following convenient representation of $\mathcal{L}(\infty Q)$ by using Gröbner basis theory [@adams94]. The following review is borrowed from [@miuraform]. Hereafter, we assume that the reader is familiar with the Gröbner basis theory in [@adams94].

Let $\mathbf{N}_0$ be the set of nonnegative integers. For $(m_1$, …, $m_t)$, $(n_1$, …, $n_t) \in
\mathbf{N}_0^t$, we define the weighted reverse lexicographic monomial order $\succ$ such that $(m_1$, …, $m_t)$ $\succ$ $(n_1$, …, $n_t)$ if $a_1 m_1 + \cdots + a_t m_t > a_1 n_1 + \cdots + a_t n_t$, or $a_1 m_1 + \cdots + a_t m_t = a_1 n_1 + \cdots + a_t n_t$, and $m_1 = n_1$, $m_2 = n_2$, …, $m_{i-1} = n_{i-1}$, $m_i<n_i$, for some $1 \leq i \leq t$. Note that a Gröbner basis of $I$ with respect to $\succ$ can be computed by [@saints95 Theorem 15], [@schicho98], [@tang98 Theorem 4.1] or [@bn:vasconcelos Proposition 2.17], starting from any affine defining equations of $F/\mathbf{F}_q$.

\[ex1\] According to @hoholdt95 [Example 3.7], $$u^3 v + v^3 + u = 0$$ is an affine defining equation for the Klein quartic over $\mathbf{F}_8$. There exists a unique $\mathbf{F}_8$-rational place $Q$ such that $(v)_\infty= 3Q$, $(uv)_\infty = 5Q$, and $(u^2v)_\infty
= 7Q$. The numbers $3$, $5$ and $7$ is the minimal generating set of the Weierstrass semigroup at $Q$. Choosing $v$ as $x_1$, $uv$ as $x_2$ and $u^2v$ as $x_3$, by [@tang98 Theorem 4.1] we can see that the standard form of the Klein quartic is given by $$X_2^2+X_3X_1, X_3X_2+X_1^4+X_2, X_3^2+X_2X_1^3+X_3,$$ which is the reduced Gröbner basis with respect to the monomial order $\succ$. We can see that $a_1=3$, $a_2=5$, and $a_3=7$.

\[ex:gs1\] Consider the function field $\mathbf{F}_9(u_1,v_2,v_3)$ with relations $$v_2^3+v_2 = u_1^4, \quad v_3^3 + v_3 = (v_2/u_1)^4. \label{eq:gs1}$$ This is the third function field in the asymptotically good tower introduced by @garcia95. Substituting $v_2$ with $u_1u_2$ and $v_3$ with $u_2 u_3$ in Eq. (\[eq:gs1\]) we have affine defining equations $$u_1^2u_2^3+u_2-u_1^3=0, \quad u_2^2u_3^3+u_3-u_2^3=0.$$ The function $u_1$ has a unique pole $Q$ in $\mathbf{F}_9(u_1,u_2,u_3)
=\mathbf{F}_9(u_1,v_2,v_3)$. The minimal generating set of the Weiestrass semigroup $H(Q)$ at $Q$ is $9$, $12$, $22$, $28$, $32$ and $35$ [@voss97 Example 4.11]. It has genus $22$ and $77$ $\mathbf{F}_9$-rational points different from $Q$ [@garcia95].

Define six functions $x_1 = u_1$, $x_2 = u_1 u_2$, $x_3 = u_1^2u_2u_3$, $x_4 = u_1^3u_2^2u_3^2$, $x_5 = ((u_1u_2)^2+1)u_2u_3$ and $x_6 = ((u_1u_2)^2+1)u_2^2u_3^2$. We have $(x_1)_\infty = 9Q$, $(x_2)_\infty = 12Q$, $(x_3)_\infty = 22Q$, $(x_4)_\infty = 35Q$, $(x_5)_\infty = 28Q$ and $(x_6)_\infty = 32Q$ [@umehara98]. From this information and [@tang98 Theorem 4.1] we can compute the $15$ polynomials in the reduced Gröbner basis of the ideal $I \subset \mathbf{F}_9[X_1$, …, $X_6]$ defining $\mathcal{L}(\infty Q)$ as $\{X_2^3-X_1^4+X_2$, $X_5X_2-X_3X_1^2$, $X_6X_2-X_4X_1$, $X_3^2-X_4X_1$, $X_3X_2^2-X_5X_1^2+X_3$, $X_5X_3-X_6X_1^2$, $X_6X_3-X_1^6+X_5X_1^2+X_2X_1^2$, $X_5^2-X_4X_2X_1-X_6$, $X_4X_3-X_2X_1^5+X_3X_1^3+X_2^2X_1$, $X_4X_2^2-X_6X_1^3+X_4$, $X_6X_5-X_2^2X_1^4+X_3X_2X_1^2+X_5$, $X_5X_4-X_1^7+X_5X_1^3+X_2X_1^3$, $X_6^2-X_5X_1^4+X_4X_2X_1+X_3X_1^2+X_6$, $X_6X_4-X_3X_1^5+X_6X_1^3+X_3X_2X_1$, $X_4^2-X_3X_2X_1^4+X_4X_1^3+X_5X_1^2-X_3\}$. Note that polynomials in the above Gröbner basis are in the ascending order with respect to the monomial order $\prec$ while terms in each polynomial are in the descending order with respect to $\prec$.

For $i=0$, …, $a_1-1$, we define $b_i = \min\{ m \in H(Q) \mid m \equiv i \pmod{a_1}\}$, and $L_i$ to be the minimum element $(m_1$, …, $m_t) \in \mathbf{N}_0^t$ with respect to $\prec$ such that $a_1 m_1 + \cdots +
a_t m_t = b_i$. Note that $b_i$’s are the well-known Apéry set [@MR2549780 Lemmas 2.4 and 2.6] of the numerical semigroup $H(Q)$. Then we have $\ell_1 = 0$ if we write $L_i$ as $(\ell_1$, …, $\ell_t)$. For each $L_i = (0$, $\ell_{i2}$, …, $\ell_{it})$, define $y_i = x_2^{\ell_{i2}} \cdots x_t^{\ell_{it}} \in \mathcal{L}(\infty Q)$.

The footprint of $I$, denoted by $\Delta(I)$, is $\{ (m_1$, …, $m_t) \in \mathbf{N}_0^t \mid X_1^{m_1} \cdots
X_t^{m_t}$ is not the leading monomial of any nonzero polynomial in $I$ with respect to $\prec\}$, and define $\Omega_0 = \{x_1^{m_1} \cdots x_t^{m_t} \mid 
(m_1$, …, $m_t) \in \Delta(I)\}$. Then $\Omega_0$ is a basis of $\mathcal{L}(\infty Q)$ as an $\mathbf{F}_q$-linear space [@adams94], two distinct elements in $\Omega_0$ have different pole orders at $Q$, and $$\begin{aligned}
\Omega_0 &=& \{ x_1^m x_2^{\ell_2} \cdots, x_t^{\ell_t} \mid m \in \mathbf{N}_0,
(0, \ell_2, \ldots, \ell_t) \in \{L_0, \ldots, L_{a_1-1}\}\}\nonumber\\
&=& \{ x_1^m y_i \mid m \in \mathbf{N}_0, i=0, \ldots, a_1-1\}.
\label{eq:footprintform}\end{aligned}$$ Equation (\[eq:footprintform\]) shows that $\mathcal{L}(\infty Q)$ is a free $\mathbf{F}_q[x_1]$-module with a basis $\{y_0$, …, $y_{a_1-1}\}$. Note that the above structured shape of $\Omega_0$ reflects the well-known property of every weighted reverse lexicographic monomial order, see the paragraph preceding to [@bn:eisenbud Proposition 15.12].

\[ex2\] For the curve in Example \[ex1\], we have $y_0 = 1$, $y_1=x_3$, $y_2=x_2$.

Let $v_Q$ be the unique valuation in $F$ associated with the place $Q$. The semigroup $H(Q)$ is equal to $\{i a_1 - v_Q (y_j) \mid 0\le i,0\le j<a_1\}$ [@MR2549780 Lemma 2.6]. By [@miuraform Proposition 3.18], for each nongap $s\in H(Q)$ there is a unique monomial $x_1^i y_j \in \Omega_0$ with $0\le j<a_1$ such that $-v_Q (x_1^i  y_j )=s$, and let us denote this monomial by $\varphi_s$. Let $\Gamma \subset H(Q)$, and we may consider the one-point codes $$C_\Gamma = \langle \{{\mathrm{ev}}(\varphi_s) \mid s \in \Gamma \}\rangle,\label{eq:cgamma}$$ where $\langle \cdot \rangle$ denotes the $\mathbf{F}_q$-linear space spanned by $\cdot$. Since considering linearly dependent rows in a generator matrix has no merit, we assume $$\Gamma \subseteq \widehat{H}(Q), \label{eq:gammaassume}$$ where $\widehat{H}(Q) = \{ u \in H(Q) \mid
C_u \neq C_{u-1} \}$. One motivation for considering these codes is that it was shown in [@andersen08] how to increase the dimension of the one-point codes without decreasing the lower bound $d_{\mathrm{AG}}$ for the minimum distance. The bound $d_{\mathrm{AG}}(C_\Gamma)$ is defined for $C_\Gamma$ as follows [@andersen08]: For $s \in \Gamma$, let $$\lambda(s) = \sharp \{ j \in H(Q) \mid j+s \in
\widehat{H}(Q) \}. \label{eq:lambda}$$ Then $d_{\mathrm{AG}}(C_\Gamma) = \min\{ \lambda(s) \mid s\in \Gamma \}$. It is proved in [@geil11] that $d_{\mathrm{AG}}$ gives the same estimate for the minimum distance as the Feng-Rao bound [@fengrao93] for one-point dual AG codes when both $d_{\mathrm{AG}}$ and the Feng-Rao bound can be applied, that is, when the dual of a one-point code is isometric to a one-point code. Furthermore, it is also proved in [@geil11] that $d_{\mathrm{AG}}(C_\Gamma)$ can be obtained from the bounds in [@beelen07; @duursma11; @duursma10], hence $d_{\mathrm{AG}}$ can be understood as a particular case of these bounds [@beelen07; @duursma11; @duursma10].

Procedure of New List Decoding based on Voting in Gröbner Bases {#sec3}
===============================================================

Overall Structure
-----------------

Suppose that we have a received word $\vec{r} \in \mathbf{F}_q^n$. We shall modify the unique decoding algorithm proposed by @lee11 so that we can find all the codewords in $C_\Gamma$ in Eq. (\[eq:cgamma\]) within the Hamming distance $\tau$ from $\vec{r}$. The overall structure of the modified algorithm is as follows:

1.  \[l1\] Precomputation before getting a received word $\vec{r}$,

2.  \[l2\] Initialization after getting a received word $\vec{r}$,

3.  \[l3\] Termination criteria of the iteration, and

4.  \[l4\] Main part of the iteration.

Steps \[l2\] and \[l4\] are based on [@lee11]. Steps \[l1\] and \[l3\] are not given in [@lee11]. Each step is described in the following subsections in Section \[sec3\]. We shall analyze time complexity except the precomputation part of the algorithm.

Modified Definitions for the Proposed Modification
--------------------------------------------------

We retain notations from Section \[sec2\]. In this subsection, we modify notations and definitions in [@lee11] to describe the proposed modification to their algorithm. We also introduce several new notations. Define a set $\Omega_1 = \{ x_1^i y_jz^k \mid 0 \leq i$, $0 \leq j < a_1$, $k=0,1\}$. Our $\Omega_1$ is $\Omega$ in [@lee11]. Recall also that $\Omega_0 = \{ \varphi_s \mid s \in H(Q)\}$.

Since the $\mathbf{F}_q[x_1]$-module ${\mathcal{L}(\infty Q)}z \oplus {\mathcal{L}(\infty Q)}$ has a free basis $\{ y_j z, y_j \mid
0 \leq j < a_1\}$, we can regard $\Omega_1$ as the set of monomials in the Gröbner basis theory for modules. We introduce a monomial order on $\Omega_1$ as follows. For given two monomials $x_1^{i_1} y_j z^{i_{t+1}}$ and $x_1^{i'_1} y_{j'} z^{i'_{t+1}}$, first rewrite $y_j$ and $y_{j'}$ by $x_2$, …, $x_t$ defined in Section \[sec2\] and get $x_1^{i_1} y_j z^{i_{t+1}} = x_1^{i_1} x_2^{i_2} \cdots x_t^{i_t} z^{i_{t+1}}$ and $x_1^{i'_1} y_{j'} z^{i'_{t+1}} = x_1^{i'_1} x_2^{i'_2} \cdots x_t^{i'_t} z^{i'_{t+1}}$. For a nongap $s \in H(Q)$, we define the monomial order $x_1^{i_1} x_2^{i_2} \cdots x_t^{i_t} z^{i_{t+1}}<_s
x_1^{i'_1} x_2^{i'_2} \cdots x_t^{i'_t} z^{i'_{t+1}}$ parametrized by $s$ if $i_{t+1}s - v_Q(x_1^{i_1} x_2^{i_2} \cdots x_t^{i_t}) <
i'_{t+1}s - v_Q(x_1^{i'_1} x_2^{i'_2} \cdots x_t^{i'_t})$ or $i_{t+1}s - v_Q(x_1^{i_1} x_2^{i_2} \cdots x_t^{i_t}) =
i'_{t+1}s - v_Q(x_1^{i'_1} x_2^{i'_2} \cdots x_t^{i'_t})$ and $i_1 = i'_1$, $i_2 = i'_2$, …, $i_{\ell-1}=i'_{\ell-1}$ and $i_\ell > i'_\ell$ for some $1 \leq \ell \leq t+1$. Observe that the restriction of $<_s$ to $\Omega_0$ is equal to $\prec$ defined in Section \[sec2\]. In what follows, every Gröbner basis, leading term, and leading coefficient is obtained by considering the Gröbner basis theory for modules, not for ideals.

For $f \in {\mathcal{L}(\infty Q)}z \oplus {\mathcal{L}(\infty Q)}$, $\gamma(f)$ denotes the number of nonzero terms in $f$ when $f$ is expressed as an $\mathbf{F}_q$-linear combination of monomials in $\Omega_1$. $\gamma_{\neq 1}(f)$ denotes the number of nonzero terms whose coefficients are not $1 \in \mathbf{F}_q$.

For the code $C_\Gamma$ in Eq. (\[eq:cgamma\]), define the divisor $D=P_1+ \cdots + P_n$. Define $\mathcal{L}(-G+\infty Q) = \bigcup_{i=1}^\infty
\mathcal{L}(-G+iQ)$ for a positive divisor $G$ of $F/\mathbf{F}_q$. Then $\mathcal{L}(-D+\infty Q)$ is an ideal of ${\mathcal{L}(\infty Q)}$ [@matsumoto99ldpaper]. Let $\eta_i$ be any element in $\mathcal{L}(-D+\infty Q)$ such that $\textsc{lm}(\eta_i) = x_1^j y_i$ with $j$ being the minimal given $i$. Then by [@lee11 Proposition 1], $\{\eta_0$, …, $\eta_{a_1-1}\}$ is a Gröbner basis for $\mathcal{L}(-D+\infty Q)$ with respect to $<_s$ as an $\mathbf{F}_q[x_1]$-module. For a nonnegative integer $s$, define $\Gamma^{(\leq s)} = \{
s' \in \Gamma \mid s' \leq s \}$, $\Gamma^{(> s)} = \{
s' \in \Gamma \mid s' > s \}$, and $\mathrm{prec}(s)= \max\{s' \in H(Q) \mid s'<s \}$. We define $\mathrm{prec}(0) = -1$.

Precompuation before Getting a Received Word {#sec:precomput}
--------------------------------------------

Before getting $\vec{r}$, we need to compute the Pellikaan-Miura standard form of the algebraic curve, $y_0(=1)$, $y_1$, …, $y_{a_1-1}$, and $\varphi_s$ for $s \in H(Q)$ as defined in Section \[sec2\]. Also compute $\eta_0$, …, $\eta_{a_1-1}$, which can be done by [@matsumoto99ldpaper].

For each $(i,j)$, express $y_i y_j$ as an $\mathbf{F}_q$-linear combination of monomials in $\Omega_0$. Such expressions will be used for computing products and quotients in ${\mathcal{L}(\infty Q)}$ as explained in Section \[sec:product\]. [From]{} the above data, we can easily know $\textsc{lc}(y_i y_j)$, which will be used in Eqs. (\[eq:quotientpre\]) and (\[eq:mui\]).

Find elements $\varphi_s \in \Omega_0$ with $s \in \widehat{H}(Q)$. There are $n$ such elements, which we denote by $\psi_1$, …$\psi_n$ such that $-v_Q(\psi_i) < -v_Q(\psi_{i+1})$. Compute the $n \times n$ matrix $$M=\left(
\begin{array}{ccc}
\psi_1(P_1)&\cdots&\psi_1(P_n)\\
\vdots&\vdots& \vdots\\
\psi_n(P_1)&\cdots&\psi_n(P_n)
\end{array}\right)^{-1}.\label{eq:invgenmatrix}$$

Multiplication and Division in an Affine Coordinate Ring
--------------------------------------------------------

In both original unique decoding algorithm [@lee11] and our modified version, we need to quickly compute the product $gh$ of two elements $g,h$ in the affine coordinate ring ${\mathcal{L}(\infty Q)}$. In our modified version, we also need to compute the quotient $g/h$ depending on the choice of iteration termination criterion described in Section \[sec:termination\]. Since the authors could not find quick computational procedures for those tasks in ${\mathcal{L}(\infty Q)}$, we shall present such ones here.

### Multiplication in an Affine Coordinate Ring {#sec:product}

The normal form of $g$, for $g \in {\mathcal{L}(\infty Q)}$, is the expression of $g$ written as an $\mathbf{F}_q$-linear combination of monomials $\varphi_s \in \Omega_0$. $g,h$ are assumed to be in the normal form. We propose the following procedure to compute the normal form of $gh$. Let the normal form of $y_i y_j$ be $$\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1).$$ with $f_{i,j,k}(x_1) \in \mathbf{F}_q[x_1]$, which is computed in Section \[sec:precomput\].

We denote by $X_1$, $Y_1$, …, $Y_{a_1-1}$ algebraically independent variables over $\mathbf{F}_q$.

1.  Assume that $g$ and $h$ are in their normal forms. Change $y_i$ to $Y_i$ and $x_1$ to $X_1$ in $g,h$ for $i=1$, …, $a_1-1$. Recall that $y_0=1$. Denote the results by $G,H$.

2.  Compute $GH$. This step needs $$\gamma(g)\times \gamma(h)\label{eq:NFmulti1}$$ multiplications in $\mathbf{F}_q$.

3.  Let $GH = \sum_{0\leq i,j <a_1} Y_i Y_j F_{G,H,i,j}(X_1)$. Then we have $$gh =  \sum_{0\leq i,j<a_1} F_{G,H,i,j}(x_1) \sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1).
    \label{eq:gh}$$ Computation of $F_{G,H,i,j}(X_1)\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1)$ needs at most $\gamma_{\neq 1}(\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1)) \allowbreak
    \gamma( F_{G,H,i,j}(x_1))$ multiplications in $\mathbf{F}_q$. Therefore, the total number of multiplications in $\mathbf{F}_q$ in this step is at most $$\sum_{0 \leq i,j < a_1} \gamma( F_{G,H,i,j}(x_1))
    \gamma_{\neq 1}(\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1)).\label{eq:NFmulti2}$$

Therefore, the total number of multiplications in $\mathbf{F}_q$ is at most $$\gamma(g)\times \gamma(h) + \sum_{0 \leq i,j < a_1} \gamma( F_{G,H,i,j}(x_1))
\gamma_{\neq 1}(\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1))
. \label{eq:NFmulti3}$$ Define Eq. (\[eq:NFmulti3\]) as $\mathrm{multi}(g,h)$.

We emphasize that when the characteristic of $\mathbf{F}_q$ is 2 and all the coefficients of defining equations belong to $\mathbf{F}_2$, which is almost always the case for those cases of interest for applications in coding theory, then $\gamma_{\neq 1}(\sum_{k=0}^{a_1-1} y_k f_{i,j,k}(x_1))$ in Eq. (\[eq:NFmulti3\]) is zero. This means that $\mathcal{L}(\infty Q)$ has little additional overhead over $\mathbf{F}_q[X]$ for computing products of their elements in terms of the number of $\mathbf{F}_q$-multiplications and divisions.

Define $(i,j)$ to be equivalent to $(i',j')$ if $y_i y_j = y_{i'}y_{j'} \in \mathcal{L}(\infty Q)$. Denote by $[i,j]$ the equivalence class represented by $(i,j)$. For $(i,j), (i',j') \in [i,j]$ we have $f_{i,j,k}(x_1) = f_{i',j',k}(x_1)$, which is denoted by $f_{[i,j],k}(x_1)$. The right hand side of Eq. (\[eq:gh\]) can be written as $$\sum_{[i,j]}\left(\sum_{(i',j')\in[i,j]} F_{G,H,i',j'}(x_1)\right) \sum_{k=0}^{a_1-1} y_k f_{[i,j],k}(x_1). \label{eq:gh2}$$ By using Eq. (\[eq:gh2\]) instead of Eq. (\[eq:gh\]), we have another upper bound on the number of multiplications as $$\gamma(g)\times \gamma(h) + \sum_{[i,j]} \gamma\left( \sum_{(i',j')\in[i,j]} F_{G,H,i',j'}(x_1)\right)
\gamma_{\neq 1}(\sum_{k=0}^{a_1-1} y_k f_{[i,j],k}(x_1))
. \label{eq:NFmulti4}$$ Since $$\gamma\left( \sum_{(i',j')\in[i,j]} F_{G,H,i',j'}(x_1)\right)
\leq 
\sum_{(i',j')\in[i,j]} \gamma( F_{G,H,i',j'}(x_1)),$$ we have Eq. (\[eq:NFmulti4\]) $\leq$ Eq. (\[eq:NFmulti3\]). However, Eq. (\[eq:NFmulti4\]) is almost always the same as Eq. (\[eq:NFmulti3\]) over the curve in Example \[ex:gs1\], and Eq. (\[eq:NFmulti4\]) will not be used in our computer experiments in Section \[sec:experiment\].

### Computation of the Quotient

Assume $h\neq 0$. The following procedure computes the quotient $g/h \in \mathcal{L}(\infty Q)$ or declares that $g$ does not belong to the principal ideal of ${\mathcal{L}(\infty Q)}$ generated by $h$.

1.  Initialize $\sigma=0$. Also initialize $\zeta=0$.

2.  \[lab\] Check if $-v_Q(g) \in -v_Q(h) + H(Q)$. If not, declare that $g$ does not belong to the principal ideal of ${\mathcal{L}(\infty Q)}$ generated by $h$, and finish the procedure.

3.  Let $\varphi_s \in \Omega_0$ such that $-v_Q(g) = -v_Q(\varphi_sh)$. Observe that $\textsc{lc}(\varphi_s\textsc{lm}(h)) = 
    \textsc{lc}(y_{s \bmod a_1} y_{-v_Q(h) \bmod a_1})$ and that $\textsc{lc}(y_{s \bmod a_1} y_{-v_Q(h) \bmod a_1})$ is precomputed as Section \[sec:precomput\]. Let $$\mathbf{F}_q \ni t =  \textsc{lc}(g)/(\textsc{lc}(h) \times \underbrace{\textsc{lc}(\varphi_s\textsc{lm}(h))}_{\textrm{Precomputed in Section \ref{sec:precomput}}}).
    \label{eq:quotientpre}$$ Computation of $t\varphi_s$ needs one multiplication and one division in $\mathbf{F}_q$. Observe that $-v_Q(g - t\varphi_sh) < -v_Q(g)$.

4.  Compute the normal form of $t \varphi_s h$, which requires at most $\mathrm{multi}(t\varphi_s, h)$ multiplications in $\mathbf{F}_q$. Increment $\zeta$ by $2+\mathrm{multi}(t\varphi_s, h)$.

5.  Update $\sigma \leftarrow \sigma + t \varphi_s$ and $g \leftarrow g - t\varphi_sh$. If the updated $g$ is zero, then output the updated $\sigma$ as the quotient and finish the procedure. Otherwise go to Step \[lab\]. This step has no multiplication nor division.

Define $\mathrm{quot}(g,h)$ as $\zeta$ after finishing the above procedure. $\mathrm{quot}(g,h)$ is an upper bound on the number of multiplications and divisions in $\mathbf{F}_q$ in the above procedure. The program variable $\zeta$ is just to define $\mathrm{quot}(g,h)$, and the decoding algorithm does not need to update $\zeta$. Observe also that the above procedure is a straightforward generalization of the standard long division of two univariate polynomials [@mckeague11].

Initialization after Getting a Received Word $\vec{r}$ {#sec:initialization}
------------------------------------------------------

Let $(i_1$, …, $i_n)^T = M\vec{r}$, where $M$ is defined in Eq. (\[eq:invgenmatrix\]). Define $h_{\vec{r}} = \sum_{j=1}^n i_j \psi_j$. Then we have ${\mathrm{ev}}(h_{\vec{r}}) = \vec{r}$. The computation of $h_{\vec{r}}$ from $\vec{r}$ needs at most $n^2$ multiplications in $\mathbf{F}_q$.

Let $N=-v_Q(h_{\vec{r}})$. For $i=0$, …, $a_1-1$, compute $g_i^{(N)} = \eta_i \in {\mathcal{L}(\infty Q)}$ and $f_i^{(N)} =
y_i(z-h_{\vec{r}}) \in {\mathcal{L}(\infty Q)}z \oplus {\mathcal{L}(\infty Q)}$. The computation of $f_i^{(N)}$ needs at most $\mathrm{multi}(y_i, h_{\vec{r}})$ multiplications in $\mathbf{F}_q$. Therefore, the total number of multiplications in the initialization is at most $$n^2 + \sum_{i=0}^{a_1-1} \mathrm{multi}(y_i, h_{\vec{r}}). \label{eq:compl:ini}$$ Let $s=N$ and execute the following steps.

Three Termination Criteria of the Iteration {#sec:termination}
-------------------------------------------

After finishing the initialization step in Section \[sec:initialization\], we iteratively compute $f_i^{(s)}$ and $g_i^{(s)}$ with $N \geq s \in H(Q) \cup
\{-1\}$ and $w_s$ with $N \geq s \in H(Q)$ from larger $s$ to smaller $s$. The single iteration consists of two parts: The first part is to check if an iteration termination criterion is satisfied. The second part is computation of $f_i^{(s)}$ and $g_i^{(s)}$ for $N \geq s \in H(Q) \cup \{-1\}$. We describe the first part in Section \[sec:termination\].

Let $f_{\mathrm{min}} = \alpha_0 + z \alpha_1$ having the smallest $-v_Q(\alpha_1)$ among $f^{(s)}_0$, …, $f^{(s)}_{a_1-1}$. In the following subsections, we shall propose three different procedures to judge whether or not iterations in the proposed algorithm can be terminated. In an actual implementation of the proposed algorithm, one criterion is chosen and the chosen one is consistently used throughout the iterations. The first one and the second one are different generalizations of [@kuijper11 Theorem 12] for the case $g=0$ to $g > 0$. @kuijper11 [Theorem 12] proved that if the number $\delta$ of errors satisfies $2 \delta < d_{\mathrm{RS}}(C_s)$, where $d_{\mathrm{RS}}(C_s)$ is the minimum distance $n-s$ of the $[n,s+1]$ Reed-Solomon code $C_s$, then the transmitted information word is obtained by Ali-Kuijper’s algorithm as $-\alpha_0/\alpha_1$. To one-point primal AG codes, $d_{\mathrm{RS}}(C_s)$ can be generalized as either $d_{\mathrm{AG}}(C_s)$ or $n-s-g$. The former generalization $d_{\mathrm{AG}}(C_s)$ corresponds to the first criterion in Section \[sec:first\] and the latter $n-s-g$ corresponds to the second in Section \[sec:second\].

The third one is almost the same as the original procedure in [@lee11]. The first one was proposed in [@gmr12isit] while the second and the third ones are new in this paper. We shall compare the three criteria in Section \[sec:comparethree\]. Throughout this paper, ${\mathrm{wt}}(\vec{x})$ denotes the Hamming weight of a vector $\vec{x}\in \mathbf{F}_q^n$.

### First Criterion for Judging Termination {#sec:first}

If

-   $s \in \Gamma$,

-   $d_{\mathrm{AG}}(C_{\Gamma^{(\leq s)}}) > 2 \tau$, and

-   $-v_Q(\alpha_1) \leq \tau + g$

then do the following:

1.  \[first1\] Compute $\alpha_0/\alpha_1 \in F$. This needs at most $$\mathrm{quot}(\alpha_0, \alpha_1)\label{eq:compl3}$$ multiplications and divisions in $\mathbf{F}_q$.

2.  If $\alpha_0/\alpha_1 \in {\mathcal{L}(\infty Q)}$ and $\alpha_0/\alpha_1$ can be written as a linear combination of monomials in $\{\varphi_{s'}\in s'\in \Gamma^{(\leq s)}\}$, then do the following:

    1.  \[first11\] If $d_{\mathrm{AG}}(C_{\Gamma}) > 2 \tau$ or $-v_Q(\alpha_1) \leq \tau$ then include the coefficients of $-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ into the list of transmitted information vectors, and avoid proceeding with the rest of the decoding procedure.

    2.  \[first12\] Otherwise compute ${\mathrm{ev}}(-\alpha_0/\alpha_1 +\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})$. This needs at most $$n \gamma(-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}) \label{eq:compl4}$$ multiplications and divisions in $\mathbf{F}_q$.

    3.  \[first13\] If $${\mathrm{wt}}\left({\mathrm{ev}}(-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})- \vec{r}\right) \leq  \tau,$$ then include the coefficients of $-\alpha_0/\alpha_1$ $+$ $\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ into the list of transmitted information vectors, and avoid proceeding with $s$. Otherwise, continue the iterations unless $s < n - g - 2\tau$.

### Second Criterion for Judging Termination {#sec:second}

If $s = \max\{ s' \in \Gamma 
\mid s' < n-2 \tau - g\}$, then do the following:

1.  \[second1\] If $-v_Q(\alpha_1) > \tau + g$ then stop proceeding with iteration.

2.  Otherwise compute $\alpha_0/\alpha_1 \in F$. This needs at most $$\mathrm{quot}(\alpha_0, \alpha_1) \label{eq:compl5}$$ multiplications and divisions in $\mathbf{F}_q$.

3.  If $2 \tau < d_{\mathrm{AG}} (C_\Gamma )$, $\alpha_0/\alpha_1 \in {\mathcal{L}(\infty Q)}$, and $\alpha_0/\alpha_1$ can be written as a linear combination of monomials in $\{\varphi_{s'}\in s'\in \Gamma^{(\leq s)}\}$ then declare the coefficients of $-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ as the only transmitted information and finish. Otherwise declare “decoding failure” and finish.

4.  If $2 \tau \geq d_{\mathrm{AG}} (C_\Gamma )$, $\alpha_0/\alpha_1 \in {\mathcal{L}(\infty Q)}$ and $\alpha_0/\alpha_1$ can be written as a linear combination of monomials in $\{\varphi_{s'}\in s'\in \Gamma^{(\leq s)}\}$, then do the following:

    1.  \[second11\] If $-v_Q(\alpha_1) \leq \tau$ then include the coefficients of $-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ into the list of transmitted information vectors, and avoid proceeding with $s$.

    2.  \[second12\] Otherwise compute ${\mathrm{ev}}(-\alpha_0/\alpha_1 +\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})$. This needs at most $$n \gamma(-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})\label{eq:compl6}$$ multiplications and divisions in $\mathbf{F}_q$.

    3.  If $${\mathrm{wt}}\left({\mathrm{ev}}(-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})- \vec{r}\right) \leq  \tau,$$ then include the coefficients of $-\alpha_0/\alpha_1$ $+$ $\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ into the list of transmitted information vectors.

5.  Finish the iteration no matter what happened in the above steps.

### Third Criterion for Judging Termination {#sec:3rd}

Just repeat the iteration until finding $f_i^{(s)}$ at $s=-1$ for $i=0$, …, $a_1-1$. If $2 \tau < d_{\mathrm{AG}} (C_\Gamma )$ then declare the vector $(w_s : s \in \Gamma)$ as the only transmitted information and finish.

If $2 \tau \geq d_{\mathrm{AG}} (C_\Gamma )$ then do the following:

1.  \[third1\] If $\alpha_0=0$ and $-v_Q(\alpha_1) \leq \tau$ then include the vector $(w_s : s \in \Gamma)$ into the list of transmitted information vectors. Finish the iteration.

2.  \[third2\] If $-v_Q(\alpha_1) > \tau+g$ then finish the iteration.

3.  \[third3\] Otherwise compute ${\mathrm{ev}}(\sum_{s \in \Gamma} w_{s} \varphi_{s})$. This needs at most $$n \gamma(\sum_{s \in \Gamma} w_{s} \varphi_{s})\label{eq:compl7}$$ multiplications and divisions in $\mathbf{F}_q$.

4.  \[third4\] If $${\mathrm{wt}}\left({\mathrm{ev}}(\sum_{s \in \Gamma} w_{s} \varphi_{s})- \vec{r}\right) \leq  \tau,$$ then include the vector $(w_s : s \in \Gamma)$ into the list of transmitted information vectors. Finish the iteration.

Iteration of Pairing, Voting, and Rebasing {#sec:mainiteration}
------------------------------------------

The iteration of the original algorithm [@lee11] consists of three steps, called pairing, voting, and rebasing. We will make a small change to the original. Our modified version is described below.

### Pairing

Let $$g_i^{(s)} = \sum_{0\le j<a_1}c_{i,j}  y_j  z+ \sum_{0\le j<a_1} d_{i,j}    y_j, \mathrm{~with~} c_{i,j}, d_{i,j} \in\mathbf{F}_q[x_1],$$ $$f_i^{(s)}   =   \sum_{0\le j<a_1}a_{i,j}   y_j  z+ \sum_{0\le j<a_1}b_{i,j}   y_j, \mathrm{~with~} a_{i,j}, b_{i,j} \in\mathbf{F}_q[x_1],$$ and let $\nu_i^{(s)}=\textsc{lc} (d_{i,i})$. We assume that $\textsc{lt}(f_i^{(s)}) = a_{i,i}   y_i  z$ and $\textsc{lt}(g_i^{(s)}) = d_{i,i}   y_i$. For $0 \le i <a_1$, as in [@lee11] there are unique integers $0\le i'<  a_1$ and $k_i$ satisfying $$-v_Q(a_{i,i} y_i) + s = a_1 k_i -v_Q(y_{i'}).$$ Note that by the definition above $$\label{eq:iprime}i' = i + s \bmod  a_1,$$ and the integer $-v_Q (a_{i,i} y_i )+s$ is a nongap if and only if $k_i\ge 0$. Now let $c_i=\deg_{x_1}(d_{i',i'})-k_i$. Note that the map $i\mapsto i'$ is a permutation of $\{0,1,\dots,a-1\}$ and that the integer $c_i$ is defined such that $a_1 c_i= -v_Q (d_{i',i'}  y_{i'} )+v_Q (a_{i,i}  y_i )-s$.

### Voting

For each $i \in  \{0, \ldots a_1 -1\}$, we set $$\mu_i= \textsc{lc}( a_{i,i} y_i \varphi_s), ~ w_{s,i}=-\frac{b_{i,i'}[x_1^{k_i}]}{\mu_i}, ~  \bar{c}_i=\max\{c_i,0\},
\label{eq:mui}$$ where $b_{i,i'}[x_1^{k_i}]$ denotes the coefficient of $x_{k_i}$ of the univariate polynomial $b_{i,i'} \in \mathbf{F}_q[x_1]$. We remark that the leading coefficient $\mu_i$ must be considered after expressing $a_{i,i} y_i \varphi_s$ by monomials in $\Omega_0$.

Observe that $\textsc{lc}(y_i \varphi_s) = \textsc{lc}(y_i y_{s \bmod a_1})$ and that $\textsc{lc}(y_i y_{s \bmod a_1})$ is already precomputed as Section \[sec:precomput\]. By using that precomputed table, computation of $\mu_i$ needs one multiplication. The total number of multiplications and divisions in Eq. (\[eq:mui\]) is $$2 a_1 \label{eq:compl1}$$ excluding negation from the number of multiplication.

Let $$\nu(s)=\frac{1}{a_1}\sum_{0\le i<a_1}
\max\{-v_Q(\eta_{i'})+v_Q(  y_i )-s,0\}.\label{eq:nu}$$ We consider two different candidates depending on whether $s \in \Gamma$ or not:

-   If $s \in H(Q) \setminus \Gamma$, set $$w=0. \label{eq:w0}$$

-   If $s \in \Gamma$, let $w$ be one of the element(s) in $\mathbf{F}_q$ with $$\label{eq:acceptedvote}
        \sum_{w=w_{s,i}}\bar{c}_i \geq \sum_{w\neq w_{s,i}}\bar{c}_i - 2\tau+\nu(s).$$

Let $w_s=w$. If several $w$’s satisfy the condition above, repeat the rest of the algorithm for each of them.

### Rebasing {#sec:rebasing}

In all of the following cases, we need to compute the normal form of the product $w\varphi_s \times \sum_{j=0}^{a_1-1} a_{i,j}   y_j$, and the product $w\varphi_s \times \sum_{j=0}^{a_1-1} c_{i,j}   y_j$. For each $i$, the number of multiplications is $$\leq \mathrm{multi}(w\varphi_s, \sum_{j=0}^{a_1-1} a_{i,j}   y_j)
+ \mathrm{multi}(w\varphi_s, \sum_{j=0}^{a_1-1} c_{i,j}   y_j), \label{eq:multirebasing}$$ where $\mathrm{multi}(\cdot, \cdot)$ is defined in Section \[sec:product\].

-   If $w_{s,i}=w$, then let $$\begin{aligned}
    \label{fkfmvd}
        &&g_{i'}^{( \mathrm{prec}(s))}=g_{i'}^{(s)}(z+w\varphi_s),\\
        &&f_i^{( \mathrm{prec}(s))}=f_i^{(s)}(z+w\varphi_s)\end{aligned}$$where the parentheses denote substitution of the variable $z$ and let $\nu_{i'}^{(  \mathrm{prec}(s))}=\nu_{i'}^{(s)}$. The number of multiplications in this case is bounded by Eq. (\[eq:multirebasing\]).

-   If $w_{s,i}\neq w$ and $c_i>0$, then let $$\begin{aligned}
    &&    g_{i'}^{( \mathrm{prec}(s))}=f_i^{(s)}(z+w\varphi_s),  \\
    &&   f_i^{( \mathrm{prec}(s))}=x_1^{c_i}f_i^{(s)}(z+w\varphi_s)-\frac{\mu_i(w-w_{s,i}) }{\nu_{i'}^{(s)}}g_{i'}^{(s)}(z+w\varphi_s)\end{aligned}$$ and let $\nu_{i'}^{( \mathrm{prec}(s))}=\mu_i(w-w_{s,i})$.

    Computation of $\frac{\mu_i(w-w_{s,i}) }{\nu_{i'}^{(s)}}$ needs one multiplication and one division. The product of $\frac{\mu_i(w-w_{s,i}) }{\nu_{i'}^{(s)}}$ and $g_{i'}^{(s)}(z+w\varphi_s)$ needs $\gamma(g_{i'}^{(s)}(z+w\varphi_s))$ multiplications, where $\gamma$ is defined in Section \[sec:product\]. Thus, the number of multiplications and divisions is $$\leq 2 + \gamma(g_{i'}^{(s)}(z+w\varphi_s)) + \mbox{Eq.\ (\ref{eq:multirebasing})}. \label{eq:compl2}$$

-   If $w_{s,i}\neq w$ and $c_i\le 0$, then let $$\begin{aligned}
    &&   g_{i'}^{({ \mathrm{prec}(s)})}=g_{i'}^{(s)}(z+w\varphi_s),\\
    && f_i^{({ \mathrm{prec}(s)})}=f_i^{(s)}(z+w\varphi_s)-\frac{\mu_i(w-w_{s,i})}{\nu_{i'}^{(s)}}x_1^{-c_i}g_{i'}^{(s)}(z+w\varphi_s)\end{aligned}$$ and let $\nu_{i'}^{( \mathrm{prec}(s))}=\nu_{i'}^{(s)}$.

    Computation of $\frac{\mu_i(w-w_{s,i}) }{\nu_{i'}^{(s)}}$ needs one multiplication and one division. The product of $\frac{\mu_i(w-w_{s,i}) }{\nu_{i'}^{(s)}}$ and $g_{i'}^{(s)}(z+w\varphi_s)$ needs $\gamma(g_{i'}^{(s)}(z+w\varphi_s))$ multiplications, where $\gamma$ is defined in Section \[sec:product\]. Thus, the number of multiplications and divisions is $\leq $ Eq. (\[eq:compl2\]).

After computing $f_i^{(\mathrm{prec}(s))}$ and $g_i^{(\mathrm{prec}(s))}$ as above, update the program variable $s$ to $\mathrm{prec}(s)$ and go to the beginning of Section \[sec:termination\].

Difference to the Original Method {#sec:diff}
---------------------------------

In this subsection, we review advantages of our modified algorithm over the original [@lee11].

-   Our version can handle any one-point primal AG codes, while the original can handle codes only coming from the $C_{ab}$ curves [@miura92]. This generalization is enabled only by replacing $y^j$ in [@lee11] by $y_j$ defined in Section \[sec2\].

-   Our version can find all the codeword within Hamming distance $\tau$ from the received word $\vec{r}$, while the original is a unique decoding algorithm.

-   Our version does not compute $f^{(s)}_i$, $g^{(s)}_i$ for a Weiestrass gap $s \notin H(Q)$, while the original computes them for $N\geq s\notin H(Q)$.

-   The original algorithm assumed $u<n$, where $u$ is as defined in Eq. (\[eq:cu\]). This assumption is replaced by another less restrictive assumption (\[eq:gammaassume\]) in our version.

-   Our version supports the Feng-Rao improved code construction [@feng95], while the original does not. This extension is made possible by the change at Eq. (\[eq:w0\]).

-   The first and the second termination criteria come from [@kuijper11 Theorem 12] and do not exist in the original [@lee11].

-   The third termination criterion is essentially the same as the original [@lee11], but examination of the Hamming distance between the decoded codeword and $\vec{r}$ is added when $2 \tau \geq d_{\mathrm{AG}}(C_\Gamma)$.

-   The original [@lee11] is suitable for parallel implementation on electric circuit similar to the Kötter architecture [@koetter98]. Our modified version retains this advantage.

Theoretical Analysis of the Proposed Modification {#sec4}
=================================================

In this section we prove that our modified algorithm can find all the codewords within Hamming distance $\tau$ from the received word $\vec{r}$. We also give upper bounds on the number of iterations in Section \[sec:nriteration\].

Supporting Lemmas {#sec:sl}
-----------------

In Section \[sec:sl\] we shall introduce several lemmas necessary in Sections \[sec:nrvotes\]–\[sec:firstwhy\]. Recall that the execution of our modified algorithm can branch when there are multiple candidates satisfying the condition (\[eq:acceptedvote\]). For a fixed sequence of determined $w_s$, define $\vec{r}^{(N)} = \vec{r}$ and recursively define $\vec{r}^{(\mathrm{prec}(s))} =
\vec{r}^{(s)} - {\mathrm{ev}}(w_s \varphi_s)$. By definition $\vec{r}^{(-1)} = \vec{r}-{\mathrm{ev}}(\sum_{s\in \Gamma} w_s \varphi_s)$.

The following lemma explains why the authors include “Gröbner bases” in the paper title. The module $I_{\vec{r}^{(N)}}$ was used in [@beelen10; @fujisawa06; @lax12; @lee09; @mrg13jsc; @sakata01; @sakata03] but the use of $I_{\vec{r}^{(s)}}$ with $s < N$ was new in [@lee11].

\[lem:ir\] Fix $s \in H(Q) \cup \{-1\}$. Let $\vec{r}^{(s)}$ correspond to $w_s$ ($s \in \Gamma$) chosen by the decoding algorithm. Define the $\mathbf{F}_q[x_1]$-submodule $I_{\vec{r}^{(s)}}$ of ${\mathcal{L}(\infty Q)}z \oplus {\mathcal{L}(\infty Q)}$ by $$I_{\vec{r}^{(s)}}=\{ \alpha_0 + \alpha_1 z \mid \alpha_0, \alpha_1 \in {\mathcal{L}(\infty Q)},
v_{P_i}(\alpha_0+r_i^{(s)}\alpha_1) \geq 1, 1 \leq i \leq n \},\label{eq:ir}$$ where $\vec{r}^{(s)} = (r_1^{(s)}$, …, $r_n^{(s)})$. Then $\{ f_i^{(s)}$, $g_i^{(s)} \mid i=0$, …, $a_1-1\}$ is a Gröbner basis of $I_{\vec{r}^{(s)}}$ with respect to $<_s$ as an $\mathbf{F}_q[x_1]$-module.

[**Proof. **]{}This lemma is a generalization of [@lee11 Proposition 11]. We can prove this lemma in exactly the same way as the proof of [@lee11 Proposition 11] with replacing $y^j$ in [@lee11] with $y_j$ and $s-1$ in [@lee11] by $\mathrm{prec}(s)$. [ ]{}

The following proposition shows that the original decoding algorithm [@lee11] can correct errors up to half the bound $d_{\mathrm{AG}}(C_\Gamma)$, which was not claimed in [@lee11].

\[prop:AG\] Fix $s \in \Gamma$. Let $\lambda(s)$ as defined in Eq. (\[eq:lambda\]) and $\nu(s)$ as defined in Eq. (\[eq:nu\]). Then $\nu(s) = \lambda(s)$.

[**Proof. **]{}Let $T_i = \{ j \in H(Q) \mid j \equiv i \pmod{a_1}, j+s \in \widehat{H}(Q)\}$, then we have $\lambda(s) = \sharp T_0 + \cdots + \sharp T_{a_1-1}$. Moreover, observe that $$H(Q) \setminus \widehat{H}(Q) =
\{ -v_Q (\eta_i x_1^k) \mid
i=0, \ldots, a_1-1, k=0,1,\ldots \}.$$ Therefore, for $s \in \Gamma$ we have $$\begin{aligned}
T_i &=& \{ j \in H(Q) \mid j \equiv i \pmod{a_1},
j+s \in \widehat{H}(Q) \} \\
&=& \{ j \in H(Q) \mid j \equiv i \pmod{a_1},
j+s \notin H(Q) \setminus \widehat{H}(Q) \}\\
&=& \{ j \in H(Q) \mid j \equiv i \pmod{a_1},
j+s \notin \{ -v_Q(\eta_{i'} x_1^k) \mid
 k \ge 0 \} \}\\
&=& \{ -v_Q(y_i x_1^m) \mid s  -v_Q(y_i x_1^m) \notin \{ -v_Q(\eta_{i'} x_1^k) \mid  k \ge 0 \} \},\end{aligned}$$ where the third equality holds by Eq. (\[eq:iprime\]). By the equalities above, we see $$\sharp T_i = \max\left\{0, \frac{-v_Q(\eta_{i'}) + v_Q (y_i)-s}{-v_Q(x_1)}\right\},$$ which proves the equality $\nu(s)=\lambda(s)$. [ ]{}

@lee11 showed that their original decoding algorithm can correct up to $\lfloor (d_{\mathrm{LBAO}}(C_u)-1)/2 \rfloor$ errors, where $d_{\mathrm{LBAO}}(C_u)
=\min\{\nu(s)\mid s\in
H(Q)$, $s\le u\}$. Proposition \[prop:AG\] implies that $d_{\mathrm{LBAO}}(C_u)$ is equivalent to $d_{\mathrm{AG}} (C_u)$ for every one-point primal code $C_u$, and therefore [@andersen08 Theorem 8] implies [@lee11 Proposition 12]. In another recent paper [@gmr13] we proved that $d_{\mathrm{AG}}$ and $d_{\mathrm{LBAO}}$ are equal to the Feng-Rao bound as defined in [@beelen08; @ldecodepaper] for $C_u$.

Lower Bound for the Number of Votes {#sec:nrvotes}
-----------------------------------

In Section \[sec:nrvotes\] we discuss the number of votes (\[eq:acceptedvote\]) which a candidate $w_{s,i}$ receives. Since we study list decoding, we cannot assume the original transmitted codeword nor the error vector as in [@lee11]. Nevertheless, the original theorems in [@lee11] allow natural generalizations to the list decoding context.

\[lem:nrvotes\] Fix $s \in \Gamma$. For $s' \in \Gamma^{(> s)}$, fix a sequence of $w_{s'}$ chosen by the decoding algorithm, and define $\vec{r}^{(s)}$ corresponding to the chosen sequence of $w_{s'}$. Fix $\omega_s \in \mathbf{F}_q$. Let $\vec{e} = (e_1$, …, $e_n)^T$ be a nonzero vector with the minimum Hamming weight in the coset $\vec{r}^{(s)} -{\mathrm{ev}}(\omega_s\varphi_s)+ C_{s-1}$, where $C_{s-1}$ is as defined in Eq. (\[eq:cu\]). Define $$\begin{aligned}
J_{\vec{e}} &=& \bigcap_{e_i\neq 0} \mathcal{L}(-P_i+\infty Q)\\
&=& \mathcal{L}\left(\infty Q - \sum_{e_i\neq 0} P_i\right) \mbox{ (by \citep{matsumoto99ldpaper})}.\end{aligned}$$ Let $\{\epsilon_0$, …, $\epsilon_{a_1-1}\}$ be a Gröbner basis for $J_{\vec{e}}$ as an $\mathbf{F}_q[x_1]$-module with respect to $<_s$ (for any integer $s$), such that $\textsc{lm}(\epsilon_j) = x_1^{k_j} y_j$.

Under the above notations, we have $$\begin{aligned}
-v_Q(\epsilon_i)+v_Q(a_{i,i} y_i )&\geq&a_1\bar{c}_i,\\
\min{\{ -v_Q(\epsilon_i)+s,-v_Q(\eta_{i'}) \}}&\geq&-v_Q(d_{i',i'} y_{i'}),\end{aligned}$$ for $i$ with $w_{s,i}\neq \omega_s$, and $$\min\{-v_Q(\epsilon_i)+s, -v_Q(\eta_{i'})\} \geq
-v_Q(d_{i',i'}y_{i'})-a_1 \bar{c}_i,$$ for $i$ with $w_{s,i}= \omega_s$.

[**Proof. **]{}The proof is the same as those of [@lee11 Propositions 7 and 8], with replacing $y^j$ in [@lee11] by $y_j$, $\delta(\cdot)$ in [@lee11] by $-v_Q(\cdot)$. [ ]{}

The following lemma is a modification to [@lee11 Proposition 9] for the list decoding.

We retain notations from Lemma \[lem:nrvotes\]. We have $$\begin{aligned}
\lefteqn{a_1 \sum_{w_{s,i}=\omega_s}\bar{c}_i\geq  a_1 \sum_{w_{s,i}\neq\omega_s}\bar{c}_i
- 2a_1{\mathrm{wt}}(\vec{e})} \\
&& \mbox{ } + \sum_{0\le i<a_1}\max{\{ -v_Q(\eta_{i'})+v_Q( y_i)-s,-v_Q(\epsilon_i)+v_Q( y_i ) \}}.\end{aligned}$$

[**Proof. **]{}Lemma \[lem:nrvotes\] implies $$\begin{aligned}
    \sum_{w_{s,i}=\omega_s}a_1\bar{c}_i
    &\geq&\sum_{w_{s,i}=\omega_s}-v_Q(d_{i',i'} y_{i'} )-\min{\{ -v_Q(\epsilon_i)+s,-v_Q(\eta_{i'}) \}}\\
    &\geq&\sum_{0\le i<a_1}-v_Q(d_{i',i'} y_{i'} )-\min{\{ -v_Q(\epsilon_i)+s,-v_Q(\eta_{i'}) \}}\end{aligned}$$ and $$\begin{aligned}
\sum_{w_{s,i}\neq\omega_s}a_1\bar{c}_i&\le&\sum_{w_{s,i}\neq\omega_s}-v_Q(\epsilon_i)+v_Q(a_{i,i} y_i )\\
    &\le&\sum_{0\le i<a_1}-v_Q(\epsilon_i)+v_Q(a_{i,i} y_i ).\end{aligned}$$ Now we have a chain of inequalities $$\begin{aligned}
&& \sum_{w_{s,i}=\omega_s}a_1\bar{c}_i - \sum_{w_{s,i}\neq\omega_s}a_1\bar{c}_i\nonumber\\
& \geq & 
\sum_{0\le i<a_1}-v_Q(d_{i',i'} y_{i'})-\min{\{ -v_Q(\epsilon_i)+s,-v_Q(\eta_{i'}) \}}\nonumber\\
    &&- \sum_{0\le i<a_1}-v_Q(\epsilon_i)+v_Q(a_{i,i} y_i )\nonumber\\
&=& \sum_{0\le i<a_1}-v_Q(d_{i',i'} y_{i'} ) -v_Q(a_{i,i} y_i)\nonumber
\\&&\mbox{ }-\min{\{ -v_Q(\epsilon_i)+s,-v_Q(\eta_{i'}) \}}+v_Q(\epsilon_i)\nonumber\\
&=  & \sum_{0\le i<a_1}-v_Q(\eta_{i'})-v_Q( y_i )\label{eq:this}\\
&&\mbox{ }+\max{\{ +v_Q(\epsilon_i)-s,+v_Q(\eta_{i'}) \}}+v_Q(\epsilon_i)\nonumber\\
&=  & \sum_{0\le i<a_1}\max{\{ -v_Q(\eta_{i'})+v_Q( y_i )-s,-v_Q(\epsilon_i)+v_Q( y_i ) \}}\nonumber\\
&&  -\sum_{0\le i<a_1}2(-v_Q(\epsilon_i)+v_Q( y_i ))\nonumber\end{aligned}$$ where at Eq. (\[eq:this\]) we used the equality $$\begin{aligned}
&&  \sum_{0\le i<a_1}-v_Q(d_{i',i'} y_{i'} )+\sum_{0\le i<a_1}-v_Q(a_{i,i} y_i)\\
&=&\sum_{0\le i<a_1}-v_Q(d_{i,i} y_i )+\sum_{0\le i<a_1}-v_Q(a_{i,i} y_i )\\
&=&\sum_{0\le i<a_1}(-v_Q(d_{i,i})-v_Q(a_{i,i}))+\sum_{0\le i<a_1}-2v_Q( y_i)\\
    &=&a_1n+\sum_{0\le i<a_1}-2v_Q( y_i )\\
&=&\sum_{0\le i<a_1}(-v_Q(\eta_{i})+v_Q(y_i))+\sum_{0\le i<a_1}-2v_Q(y_i)\\
&=&\sum_{0\le i<a_1}-v_Q(\eta_{i'})+\sum_{0\le i<a_1}-v_Q(y_i)\end{aligned}$$ shown in [@lee11 Lemma 2 and Eq. (1)]. Finally note that $$\begin{aligned}
&&\sum_{0\le i<a_1}2(-v_Q(\epsilon_i)+v_Q(y_i))\\
&=&\sum_{0\le i<a_1}2a_1\deg_{x_1}(\epsilon_i)=2a_1{\mathrm{wt}}(\vec{e})\end{aligned}$$ by [@lee11 Eq. (3)]. [ ]{}

The following lemma is a modification to [@lee11 Proposition 10] for list decoding, and provides a lower bound for the number of votes (\[eq:acceptedvote\]) received by any candidate $\omega_s \in \mathbf{F}_q$, as indicated in the section title.

\[prop:nrvotes\] We retain notations from Lemma \[lem:nrvotes\]. Let $\nu(s)$ be as defined in Eq. (\[eq:nu\]). We have $$\sum_{w_{s,i}=\omega_s}\bar{c}_i\geq \sum_{w_{s,i}\neq\omega_s}\bar{c}_i - 2{\mathrm{wt}}(\vec{e})+\nu(s).$$

[**Proof. **]{}We have $$\begin{aligned}
&&\sum_{0\le i<a_1}\max{\{ -v_Q(\eta_{i'})+v_Q(y_i)-s,-v_Q(\epsilon_i)+v_Q(y_i) \}}\\
&\ge&\sum_{0\le i<a_1}\max{\{ -v_Q(\eta_{i'})+v_Q(y_i)-s,0 \}}\end{aligned}$$ as $-v_Q(\epsilon_i)+v_Q(y_i)\ge 0$ for $0\le i<a_1$. [ ]{}

Correctness of the Modified List Decoding Algorithm with the Third Iteration Termination Criterion {#sec:thirdwhy}
--------------------------------------------------------------------------------------------------

In this subsection and the following sections, we shall prove that the proposed list decoding algorithm will find all the codewords within the Hamming distance $\tau$ from the received word $\vec{r}$. Since the third iteration termination criterion is the easiest to analyze, we start with the third one.

Fix a sequence $w_s$ for $s\in \Gamma$. If ${\mathrm{wt}}(\vec{r} - {\mathrm{ev}}(\sum_{s\in \Gamma} w_s \varphi_s))\leq \tau$ then the sequence $w_s$ is found by the algorithm because of Proposition \[prop:nrvotes\]. When $2 \tau < d_{\mathrm{AG}} (C_\Gamma )$, by Proposition \[prop:AG\] the decoding is not list decoding, and the algorithm just declares the sequence $w_s$ as the transmitted information.

On the other hand, if $2 \tau \geq d_{\mathrm{AG}} (C_\Gamma )$, then the found sequence could correspond to a codeword more distant than Hamming distance $\tau$, and the algorithm examines the Hamming distance between the found codeword and the received word $\vec{r}$.

Since computing ${\mathrm{ev}}(f)$ for $f\in {\mathcal{L}(\infty Q)}$ needs many multiplications in $\mathbf{F}_q$, the algorithm checks some sufficient conditions to decide the Hamming distance between the found codeword and the received word $\vec{r}$. Let $\vec{r}^{(-1)} = (r^{(-1)}_1$, …, $r^{(-1)}_n)$. When $\alpha_0=0$ in Section \[sec:3rd\], by Lemma \[lem:ir\], we have $$\begin{aligned}
{\mathrm{wt}}(\vec{r} - {\mathrm{ev}}(\sum_{s\in \Gamma} w_s \varphi_s))&=& {\mathrm{wt}}(\vec{r}^{(-1)})\\
&\leq& \sum_{r^{(-1)}_i \neq 0} v_{P_i}(\alpha_1)\\
&\leq&-v_Q(\alpha_1),\end{aligned}$$ because Eq. (\[eq:ir\]) and $\alpha_0=0$ implies that $v_{P_i}(\alpha_1) \geq 1$ for $r^{(-1)}_i \neq 0$. By the above equation, $-v_Q(\alpha_1) \leq \tau$ implies that the found codeword is within Hamming distance $\tau$ from $\vec{r}$. This explains why the algorithm can avoid computation of the evaluation map ${\mathrm{ev}}$ in Step \[third1\] in Section \[sec:3rd\].

In order to explain Step \[third2\] in Section \[sec:3rd\], we shall show that the condition of Step \[third2\] in Section \[sec:3rd\] implies that ${\mathrm{wt}}(\vec{r} - {\mathrm{ev}}(\sum_{s\in \Gamma} w_s \varphi_s))> \tau$. Suppose that ${\mathrm{wt}}(\vec{r} - {\mathrm{ev}}(\sum_{s\in \Gamma} w_s \varphi_s)) \leq \tau$. Then there exists $\beta_1 \in {\mathcal{L}(\infty Q)}$ such that $v_{P_i}(\beta) \geq 1$ for $r^{(-1)}_i \neq 0$, $-v_Q(\beta) \leq \tau + g$, and $\beta_1 z \in I_{\vec{r}^{(-1)}}$. Because the leading term of $\beta_1 z$ must be divisible by $\textsc{lt}(f_i^{(-1)})$ for some $i$ by the property of Gröbner bases, we must have $-v_Q(\alpha_1) \leq -v_Q(\beta_1)$. This explains why the algorithm can avoid computation of the evaluation map ${\mathrm{ev}}$ in Step \[third2\] in Section \[sec:3rd\].

Otherwise, the algorithm computes the Hamming distance between the found codeword and $\vec{r}$ in Steps \[third3\] and \[third4\] in Section \[sec:3rd\].

Correctness of the Modified List Decoding Algorithm with the Second Iteration Termination Criterion {#sec:secondwhy}
---------------------------------------------------------------------------------------------------

We shall explain why the second criterion in Section \[sec:second\] correctly finds the required codewords. For explanation, we present slightly rephrased version of facts in [@beelen08].

\[lem:23\][@beelen08 Lemma 2.3] Let $\beta_1 z + \beta_0 \in I_{\vec{r}^{(s)}}$ with $\textsc{lt}(\beta_1 z + \beta_0)
= \textsc{lt}(\beta_1 z)$ with respect to $<_s$ and $-v_Q(\beta_1) < n-\tau-s$. If there exists $f \in \mathcal{L}(sQ)$ such that ${\mathrm{wt}}({\mathrm{ev}}(f)-\vec{r}^{(s)}) \leq \tau$, then we have $f = - \beta_0/\beta_1$.

[**Proof. **]{}Observe that $\textsc{lt}(\beta_1 z + \beta_0)
= \textsc{lt}(\beta_1 z)$ implies that $-v_Q(\beta_0) \leq -v_Q(\beta_1)+s
< n-\tau$. The claim of Lemma \[lem:23\] is equivalent to [@beelen08 Lemma 2.3] with $A = (n-\tau-1)Q$ and $G = sQ$. Note that the assumption $\deg A > (n+\deg G)/2+g-1$ was not used in [@beelen08 Lemma 2.3] but only in [@beelen08 Lemma 2.4]. [ ]{}Note that the following proposition was essentially proved in [@beelen08 Proposition 2.10], [@justesen04 Section 14.2], and [@shokrollahi99 Theorem 2.1] with $b=1$.

\[prop:candivide\] Let $\alpha_0$ and $\alpha_1$ be as in Section \[sec:second\]. If $s < n -g -2\tau$ and there exists $f \in \mathcal{L}(sQ)$ such that ${\mathrm{wt}}({\mathrm{ev}}(f)-\vec{r}^{(s)}) \leq \tau$, then we have $f = -\alpha_0/\alpha_1$.

[**Proof. **]{}Let $g \in {\mathcal{L}(\infty Q)}$ such that $g(P_i) = 0$ if $f(P_i) \neq r_i^{(s)}$, and assume that $g$ has the minimum pole order at $Q$ among such elements in ${\mathcal{L}(\infty Q)}$. Then $-v_Q(g) \leq \tau + g$. One has that $gz - fg \in I_{\vec{r}^{(s)}}$ and $\textsc{lt}(gz - fg) = \textsc{lt}(gz)$ with respect to $<_s$. By the property of Gröbner bases, $\textsc{lt}(gz)$ is divisible by $\textsc{lt}(f^{(s)}_i)$ for some $i$, which implies $-v_Q(\alpha_1) \leq 
-v_Q(g) \leq \tau + g$. By Lemma \[lem:23\] we have $f = -\alpha_0/\alpha_1$. [ ]{}

We explain how the procedure in Section \[sec:second\] works as desired. When the condition in Step \[second1\] in Section \[sec:second\] is true, then there cannot be a codeword within Hamming distance $\tau$ from $\vec{r}^{(s)}$ by the same reason as Section \[sec:thirdwhy\]. So the algorithm stops processing with $\vec{r}^{(s)}$.

When $2 \tau < d_{\mathrm{AG}} (C_\Gamma )$, then the algorithm declares $-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ as the unique codeword.

When $2 \tau \geq d_{\mathrm{AG}} (C_\Gamma )$, then the algorithm examines the found codeword close enough to $\vec{r}$ in Steps \[second11\] and \[second12\] in Section \[sec:second\]. When $-v_Q(\alpha_1) \leq \tau$ we can avoid computation of the evaluation map ${\mathrm{ev}}$ by the same reason as Section \[sec:thirdwhy\], which is checked at Step \[second11\]. Otherwise we compute the codeword vector at Step \[second12\] and examine its Hamming distance to $\vec{r}^{(s)}$.

By Proposition \[prop:candivide\], the codeword must be found at $s= \max\{ s' \in \Gamma 
\mid s' < n-2 \tau + g\}$. Therefore, we do not execute the iteration at $s< \max\{ s' \in \Gamma 
\mid s'< n-2 \tau + g \}$.

Correctness of the Modified List Decoding Algorithm with the First Iteration Termination Criterion {#sec:firstwhy}
--------------------------------------------------------------------------------------------------

We shall explain why the first criterion in Section \[sec:first\] correctly finds the required codewords. The idea behind the first criterion is that there cannot be another codeword within Hamming distance $\tau$ from $\vec{r}^{(s)}$ when the algorithm already found one. So the algorithm can stop iteration with smaller $s$ once a codeword is found as ${\mathrm{ev}}(-\alpha_0/\alpha_1 +\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'})$.

The algorithm does not examine conditions when $-v_Q(\alpha_1) > \tau + g$ by the same reason as Sections \[sec:thirdwhy\] and \[sec:secondwhy\]. When $2 \tau < d_{\mathrm{AG}} (C_\Gamma )$, then the algorithm declares $-\alpha_0/\alpha_1+\sum_{s' \in \Gamma^{(> s)}} w_{s'} \varphi_{s'}$ as the unique codeword.

When $2 \tau \geq d_{\mathrm{AG}} (C_\Gamma )$, then the algorithm examines the found codeword close enough to $\vec{r}$ in Steps \[first11\]–\[first13\] in Section \[sec:first\]. When $-v_Q(\alpha_1) \leq \tau$ we can avoid computation of the evaluation map ${\mathrm{ev}}$ by the same reason as Section \[sec:thirdwhy\], which is checked at Step \[first11\].

By Proposition \[prop:candivide\], the codeword must be found at some $s\geq \max\{ s' \in \Gamma 
\mid s' < n-2 \tau + g\}$. Therefore, we do not execute the iteration at $s< \max\{ s' \in \Gamma 
\mid s' < n-2 \tau + g\}$.

Upper Bound on the Number of Iterations {#sec:nriteration}
---------------------------------------

Observe that for $s > \max \Gamma$ we set always $w_s$ to $0$. For each $s \in \Gamma$ satisfying $\nu(s) \leq 2 \tau$, the number of accepted candidates satisfying Eq. (\[eq:acceptedvote\]) can be at most $q$. On the other hand, for $s$ with $\nu(s) > 2\tau$, the number of candidates is either zero or one, because at most one $w \in \mathbf{F}_q$ can satisfy Eq.  (\[eq:acceptedvote\]). Therefore, we have upper bounds for the number of iterations, counting executions of Rebasing in Section \[sec:rebasing\], as $$\begin{aligned}
&&\sharp \{s\in H(Q) \mid \max \Gamma \leq s < N\}
+ \exp_q (\sharp \{s \in \Gamma \mid \nu(s) \leq 2 \tau\})\nonumber\\
&&\times \sharp \{s \in H(Q)\cup\{-1\} \mid
s < \max \Gamma \}\label{iteration-ub1}\end{aligned}$$ for the third criterion for judging termination, where $\exp_q(x) = q^x$, and $$\begin{aligned}
&\sharp \{s\in H(Q) \mid \max \Gamma \leq s < N)\}
+ \exp_q (\sharp \{s \in \Gamma \mid \nu(s) \leq 2 \tau\})\nonumber\\
&\times \sharp \{s \in H(Q) \mid
\max\{ s' \in \Gamma 
\mid  s' < n-2 \tau - g\} \leq s < \max \Gamma \}\label{iteration-ub2}\end{aligned}$$ for the first and the second criteria for judging termination. We will use $\max \widehat{H}(Q)$ in place of $N$ in Eqs. (\[iteration-ub1\]) and (\[iteration-ub2\]) for computation in Tables \[tab1\]–\[tab3\], because $N$ depents on $\vec{r}$ and $N \leq \max \widehat{H}(Q)$.

Observe that the list decoding can be implemented as $\exp_q (\sharp \{s \in \Gamma \mid \nu(s) \leq 2 \tau\})$ parallel execution of the unique decoding. Therefore, when one can afford $\exp_q (\sharp \{s \in \Gamma \mid \nu(s) \leq 2 \tau\})$ parallel implementation, which increases the circuit size, the decoding time of list decoding is the same as that of the unique decoding.

Comparison to Conventional Methods {#sec:experiment}
==================================

Simulation Condition and Results {#sec51}
--------------------------------

We have provided an upper bound on the number of multiplications and divisions at each step of the proposed algorithm. We simulated $1,000$ transmissions of codewords with the one-point primal codes on Klein quartic over $\mathbf{F}_8$ with $n=23$ by using Examples \[ex1\] and \[ex2\], the one-point Hermitian codes over $\mathbf{F}_{16}$ with $n=64$, and the one-point primal codes on the curve in Example \[ex:gs1\] over $\mathbf{F}_9$ with $n=77$.

The program is implemented on the Singular computer algebra system [@singular313]. The program used for this simulation is available from <http://arxiv.org/src/1203.6127/anc>.

In the execution, we counted the number of iterations, (executions of Rebasing in Section \[sec:rebasing\]), the sum of upper bounds on the number of multiplications and divisions given in Eqs. (\[eq:compl:ini\]), (\[eq:compl3\]), (\[eq:compl4\]), (\[eq:compl5\]), (\[eq:compl6\]), (\[eq:compl7\]), (\[eq:compl1\]), (\[eq:multirebasing\]) and (\[eq:compl2\]), and the number of codewords found. Note also that Eq. (\[eq:NFmulti3\]) instead of Eq. (\[eq:NFmulti4\]) is used.

The parameter $\tau$ is set to the same as the number of generated errors in each simulation condition. $N$ or $R$ in the number of errors in Tables \[tab2\] and \[tab22\] indicates that the error vector is generated toward another codeword nearest from the transmitted codeword or completely randomly, respectively. The distribution of codewords is uniform on $C_\Gamma$. That of error vectors is uniform on the vectors of Hamming weight $\tau$.

In the code construction, we always try to use the Feng-Rao improved construction. Specifically, for a given designed distance $\delta$, we choose $\Gamma = \{ s \in \widehat{H}(Q) \mid
\lambda(s)=\nu(s) \geq \delta \}$, and construct $C_\Gamma$ of Eq. (\[eq:cgamma\]). In the following, the designed distance is denoted by $d_{\mathrm{AG}}(C_\Gamma)$. It can be seen from Tables \[tab1\]–\[tab3\] and the following subsections that the computational complexity of the proposed algorithm tends to explode when the number of errors exceeds the error-correcting capability of the Guruswami-Sudan algorithm [@guruswami99].

Comparison among the Three Proposed Termination Criteria {#sec:comparethree}
--------------------------------------------------------

In Section \[sec:termination\] we proposed three criteria for terminating iteration of the proposed algorithm. From Tables \[tab1\]–\[tab3\], one can see the following. The first criterion has the smallest number of iterations, and the second is the second smallest. On the other hand, the first criterion has the largest number of multiplications and divisions. The second and the third have the similar numbers. Only the first criterion was proposed in [@gmr12isit] and we see that the new criteria are better than the old one.

The reason is as follows: The computation of quotient $\alpha_0/\alpha_1$ at Step \[first1\] in Section \[sec:first\] is costlier than updating $f_i^{(s)}$ and $g_i^{(s)}$ in Section \[sec:rebasing\] and the first criterion computes $\alpha_0/\alpha_1$ many times, which cancels the effect of decrease in the number of iterations. On the other hand, the second criterion computes $\alpha_0/\alpha_1$ only once, so it has the smaller number of multiplications and divisions than the first.

The second criterion is faster when $2 \tau < d_{\mathrm{AG}}(C_\Gamma)$, while the third tends to be faster when $2 \tau \geq d_{\mathrm{AG}}(C_\Gamma)$. In addition to this, the ratio of the number of iterations in the second criterion to that of the third is smaller with $2 \tau < d_{\mathrm{AG}}(C_\Gamma)$ than with $2 \tau \geq d_{\mathrm{AG}}(C_\Gamma)$. We speculate the reason behind them as follows: When $2 \tau \geq d_{\mathrm{AG}}(C_\Gamma)$ and a wrong candidate is chosen at Eq. (\[eq:acceptedvote\]), after several iterations of Sections \[sec:termination\] and \[sec:mainiteration\], we often observe in our simulation that no candidate satisfies Eq. (\[eq:acceptedvote\]) and the iteration stops automatically. Under such situation, the second criterion does not help much to decrease the number of iterations nor the computational complexity when a wrong candidate is chosen at Eq. (\[eq:acceptedvote\]), and there are many occasions at which a wrong candidate is chosen at Eq. (\[eq:acceptedvote\]) when $2 \tau \geq d_{\mathrm{AG}}(C_\Gamma)$. On the other hand, when $2 \tau < d_{\mathrm{AG}}(C_\Gamma)$, the second criterion helps to determine the transmitted information earlier than the third.

Tightness of Upper Bounds (\[iteration-ub1\]) and (\[iteration-ub2\])
---------------------------------------------------------------------

In Table \[tab3\], we observe that the upper bounds (\[iteration-ub1\]) and (\[iteration-ub2\]) are much larger than the actual number of iterations for $\tau=5$. The disappearance of candidates satisfying Eq. (\[eq:acceptedvote\]) in the last paragraph may also explain the reason behind the large differences for $\tau=5$.

On the other hand, we observe that the upper bound (\[iteration-ub2\]) is quite tight for $\tau=5$ in Table \[tab1\] and $\tau=10$N in Table \[tab22\]. This suggests that improvement of Eq. (\[iteration-ub2\]) may need some additional assumption.

Klein Quartic, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(4,1)$ or $(10,4)$
-------------------------------------------------------------------

We can use [@beelen07; @beelen08; @duursma11; @duursma10; @ldecodepaper] to decode this set of parameters. It is essentially the forward elimination in the Gaussian elimination, and it takes roughly $n^3/3$ multiplications. In this case $n^3/3= 4,055$. The proposed algorithm has the lower complexity than [@beelen07; @beelen08; @duursma11; @duursma10; @ldecodepaper].

Klein Quartic, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(4,2)$ or $(4,3)$
------------------------------------------------------------------

The code is $C_u$ with $u=20$, $\dim C_u = 18$. There is no previously known algorithm that can handle this case.

Klein Quartic, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(10,5)$
--------------------------------------------------------

The code is $C_u$ with $u=13$, $\dim C_u = 11$. According to @beelen10 [Figure 1], we can use the original Guruswami-Sudan [@guruswami99] but it seems that its faster variants cannot be used. We need the multiplicity $7$ to correct $5$ errors. We have to solve a system of $23(7+1)7/2 = 644$ linear equations. It takes $644^3/3 =89,029,994$ multiplications in $\mathbf{F}_8$. The proposed algorithm is much faster.

Klein Quartic, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(10,6)$
--------------------------------------------------------

The code is $C_u$ with $u=13$, $\dim C_u = 11$. There is no previously known algorithm that can handle this case.

Hermitian, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(6,2)$ or $(20,9)$
---------------------------------------------------------------

We can use the BMS algorithm [@sakata95b; @sakata95a] for this case. The complexity of [@sakata95b; @sakata95a] is estimated as $O(a_1 n^2)$ and $a_1 n^2 = 24,576$. The complexity of the proposed algorithm seems comparable to [@sakata95b; @sakata95a]. However, we are not sure which one is faster.

Hermitian, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(6,3)$ or $(6,4)$
--------------------------------------------------------------

The code becomes the Feng-Rao improved code with designed distance $6$. Its dimension is $55$. In order to have the same dimension by $C_u$ we have to set $u=60$, whose AG bound [@andersen08] is $4$ and the Guruwsami-Sudan can correct up to 2 errors. The proposed algorithm finds all codewords in the improved code with $3$ and $4$ errors.

Hermitian, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(20,10)$
-----------------------------------------------------

The code is $C_u$ with $u=44$. The required multiplicity is $11$, and the required designed list size is $14$. The fastest algorithm for the interpolation step seems [@beelen10]. @beelen10 [Example 4] estimates the complexity of their algorithm as $O(\lambda^5 n^2 (\log \lambda n)^2 \log(\log \lambda n))$, where $\lambda$ is the designed list size. Ignoring the log factor and assuming the scaling factor one in the big-$O$ notation, the number of multiplications and divisions is $\lambda^5 n^2 = 2,202,927,104$. The proposed algorithm needs much fewer number of multiplications and divisions in $\mathbf{F}_{16}$.

Hermitian, $(d_{\mathrm{AG}}(C_\Gamma),\tau)=(20,11)$
-----------------------------------------------------

The Guruwsami-Sudan algorithm [@guruswami99] can correct up to $10$ errors and there seems no previously known algorithm that can handle this case.

Garcia-Stichtenoth (Example \[ex:gs1\]), $(d_{\mathrm{AG}}(C_\Gamma),\tau) = (6,2)$, $(10,4)$, or $(20,9)$
----------------------------------------------------------------------------------------------------------

We can use [@beelen07; @beelen08; @duursma11; @duursma10; @ldecodepaper] to decode this set of parameters. It is essentially the forward elimination in the Gaussian elimination, and it takes roughly $n^3/3$ multiplications. In this case $n^3/3= 152,177$. The proposed algorithm has the lower complexity than [@beelen07; @beelen08; @duursma11; @duursma10; @ldecodepaper].

Garcia-Stichtenoth (Example \[ex:gs1\]), $(d_{\mathrm{AG}}(C_\Gamma),\tau) = (6,3)$
-----------------------------------------------------------------------------------

This is a Feng-Rao improved code with dimension $58$. In order to realize a code with the same dimension, we have to set $u=79$ in $C_u$. The Guruswami-Sudan algorithm [@guruswami99] can correct no error in this set of parameters. There seems no previously known algorithm that can handle this case.

Garcia-Stichtenoth (Example \[ex:gs1\]), $(d_{\mathrm{AG}}(C_\Gamma),\tau) = (10,5)$
------------------------------------------------------------------------------------

This is a Feng-Rao improved code with dimension $52$. In order to realize a code with the same dimension, we have to set $u=73$ in $C_u$. The Guruswami-Sudan algorithm [@guruswami99] can correct $2$ errors in this set of parameters. There seems no previously known algorithm that can handle this case.

Garcia-Stichtenoth (Example \[ex:gs1\]), $(d_{\mathrm{AG}}(C_\Gamma),\tau) = (20,10)$
-------------------------------------------------------------------------------------

This is an ordinary one-point AG code $C_u$ with $u=58$ and dimension $37$. The Guruswami-Sudan algorithm [@guruswami99] can correct $10$ errors with the multiplicity $154$ and the designed list size $178$. We have to solve a system of $77 \times (154+1)154/2 = 918,995$ linear equations. It takes $918,995^3/3 =258,712,963,551,308,291$ multiplications in $\mathbf{F}_9$. The proposed algorithm is much faster.

Garcia-Stichtenoth (Example \[ex:gs1\]), $(d_{\mathrm{AG}}(C_\Gamma),\tau) = (20,11)$
-------------------------------------------------------------------------------------

The Guruswami-Sudan algorithm [@guruswami99] can correct up to $10$ errors and there seems no previously known algorithm that can handle this case.

Conclusion {#sec6}
==========

In this paper, we modified the unique decoding algorithm for plane AG codes in [@lee11] so that it can support one-point AG codes on *any* curve, and so that it can do the list decoding. The error correction capability of the original [@lee11] and our modified algorithms are also expressed in terms of the minimum distance lower bound in [@andersen08].

We also proposed procedures to compute products and quotients in coordinate ring of affine algebraic curves, and by using those procedures we demonstrated that the modified decoding algorithm can be executed quickly. Specifically, its computational complexity is comparable to the BMS algorithm [@sakata95b; @sakata95a] for one-point Hermitian codes, and much faster than the standard list decoding algorithms [@beelen10; @guruswami99] for several cases.

The original decoding algorithm [@lee11] allows parallel implementation on circuits like the Kötter architecture [@koetter98]. Our modified algorithm retains this advantage. Moreover, if one can afford large circuit size, the proposed list decoding algorithm can be executed as quickly as the unique decoding algorithm by parallel implementation on a circuit.

Acknowledgment {#acknowledgment .unnumbered}
==============

The authors thank an anonymous reviewer for his/her careful reading that improved the presentation. This research was partially supported by the MEXT Grant-in-Aid for Scientific Research (A) No. 23246071, the Villum Foundation through their VELUX Visiting Professor Programme 2011–2012, the Danish National Research Foundation and the National Science Foundation of China (Grant No. 11061130539) for the Danish-Chinese Center for Applications of Algebraic Geometry in Coding Theory and Cryptography, the Spanish grant MTM2007-64704, and the Spanish MINECO grant No. MTM2012-36917-C03-03. The computer experiments in this research was conducted on Singular 3.1.3 [@singular313].

[52]{} \[1\][\#1]{} \[1\][`#1`]{} \[1\][doi:[](http://dx.doi.org/#1)]{} urlstyle \[1\][doi: \#1]{}

W. W. Adams and P. Loustaunau. *An Introduction to Gröbner Bases*, volume 3 of *Graduate Studies in Mathematics*. American Mathematical Society, Providence, RI, 1994.

M. Ali and M. Kuijper. A parametric approach to list decoding of Reed-Solomon codes using interpolation. *IEEE Trans. Inform. Theory*, 57(10):6718–6728, Oct. 2011. [doi: ]{}[10.1109/TIT.2011.2165803]{}. arXiv:1011.1040.

H. E. Andersen and O. Geil. Evaluation codes from order domain theory. *Finite Fields Appl.*, 14(1):92–123, Jan. 2008. [doi: ]{}[10.1016/j.ffa.2006.12.004]{}.

P. Beelen. The order bound for general algebraic geometric codes. *Finite Fields Appl.*, 13(3):665–680, July 2007. [doi: ]{}[10.1016/j.ffa.2006.09.006]{}.

P. Beelen and K. Brander. Efficient list decoding of a class of algebraic-geometry codes. *Adv. Math. Commun.*, 4(4):485–518, 2010. [doi: ]{}[10.3934/amc.2010.4.485]{}.

P. Beelen and T. Høholdt. The decoding of algebraic geometry codes. In E. Martínez-Moro, C. Munuera, and D. Ruano, editors, *Advances in Algebraic Geometry Codes*, volume 5 of *Coding Theory and Cryptology*, pages 49–98. World Scientific, 2008. [doi: ]{}[10.1142/9789812794017\_0002]{}.

M. Bras-Amorós and M. E. O’Sullivan. The correction capability of the Berlekamp-Massey-Sakata algorithm with majority voting. *Applicable Algebra in Engineering, Communication and Computing*, 17(5):315–335, Oct. 2006. [doi: ]{}[10.1007/s00200-006-0015-8]{}.

H. Chen. On the number of correctable errors of the Feng-Rao decoding algorithm for AG codes. *IEEE Trans. Inform. Theory*, 45(5):1709–1712, July 1999. [doi: ]{}[10.1109/18.771252]{}.

W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. [Singular]{} [3-1-3]{} — A computer algebra system for polynomial computations, 2011. URL <http://www.singular.uni-kl.de>.

I. M. Duursma. On erasure decoding of [AG]{}-codes. In *Proc. 1994 IEEE Information Theory Workshop*, Moscow, Russia, July 1994. URL <http://www.math.uiuc.edu/~duursma/pub/Erasure94.pdf>.

I. M. Duursma. Coset bound / shift bound. private communication, Nov. 2012.

I. M. Duursma and S. Park. Coset bounds for algebraic geometric codes. *Finite Fields Appl.*, 16(1):36–55, Jan. 2010. [doi: ]{}[10.1016/j.ffa.2009.11.006]{}.

I. M. Duursma, R. Kirov, and S. Park. Distance bounds for algebraic geometric codes. *J. Pure Appl. Algebra*, 215(8):1863–1878, Aug. 2011. [doi: ]{}[10.1016/j.jpaa.2010.10.018]{}. arXiv:1001.1374.

D. Eisenbud. *Commutative Algebra with a View Toward Algebraic Geometry*, volume 150 of *Graduate Texts in Mathematics*. Springer-Verlag, Berlin, 1995.

H. Elbrønd Jensen, R. R. Nielsen, and T. Høholdt. Performance analysis of a decoding algorithm for algebraic-geometry codes. *IEEE Trans. Inform. Theory*, 45(5):1712–1717, July 1999. [doi: ]{}[10.1109/18.771253]{}.

G. L. Feng and T. R. N. Rao. Decoding algebraic geometric codes up to the designed minimum distance. *IEEE Trans. Inform. Theory*, 39(1):36–47, Jan. 1993. [doi: ]{}[10.1109/18.179340]{}.

G. L. Feng and T. R. N. Rao. Improved geometric Goppa codes part [I]{}, basic theory. *IEEE Trans. Inform. Theory*, 41(6):1678–1693, Nov. 1995. [doi: ]{}[10.1109/18.476241]{}.

M. Fujisawa, H. Matsui, M. Kurihara, and S. Sakata. With a higher probability one can correct errors up to half the designed distance for primal codes from curves. In *Proc. SITA2006*, pages 101–104, Hakodate, Hokkaido, Japan, Nov. 2006.

A. Garcia and H. Stichtenoth. A tower of Artin-Schreier extensions of function fields, attaining the [D]{}rinfeld-[V]{}ladut bound. *Invent. Math.*, 121(1):211–222, July 1995. [doi: ]{}[10.1007/BF01884295]{}.

O. Geil and R. Pellikaan. On the structure of order domains. *Finite Fields Appl.*, 8(3):369–396, July 2002. [doi: ]{}[10.1006/ffta.2001.0347]{}.

O. Geil, C. Munuera, D. Ruano, and F. Torres. On the order bounds for one-point AG codes. *Adv. Math. Commun.*, 5(3):489–504, 2011. [doi: ]{}[10.3934/amc.2011.5.489]{}. arXiv:1002.4759.

O. Geil, R. Matsumoto, and D. Ruano. List decoding algorithms based on Gröbner bases for general one-point AG codes. In *Proc. ISIT 2012*, pages 86–90, Cambridge, MA, USA, July 2012. [doi: ]{}[10.1109/ISIT.2012.6284685]{}. arXiv:1201.6248.

O. Geil, R. Matsumoto, and D. Ruano. [Feng-Rao]{} decoding of primary codes. *Finite Fields Appl.*, 23:35–52, Sept. 2013. [doi: ]{}[10.1016/j.ffa.2013.03.005]{}. arXiv:1210.6722.

V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometry codes. *IEEE Trans. Inform. Theory*, 45(4):1757–1767, Sept. 1999. [doi: ]{}[10.1109/18.782097]{}.

T. Høholdt and R. Pellikaan. On the decoding of algebraic-geometric codes. *IEEE Trans. Inform. Theory*, 41(6):1589–1614, Nov. 1995. [doi: ]{}[10.1109/18.476214]{}.

J. Justesen and T. Høholdt. *A Course in Error-Correcting Codes*. EMS Textbooks in Mathematics. European Mathematical Society Publishing House, Zürich, Switzerland, 2004.

R. Kötter. A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-goemetric codes. *IEEE Trans. Inform. Theory*, 44(4):1353–1368, July 1998. [doi: ]{}[10.1109/18.681314]{}.

R. F. Lax. Generic interpolation polynomial for list decoding. *Finite Fields Appl.*, 18(1):167–178, Jan. 2012. [doi: ]{}[10.1016/j.ffa.2011.07.007]{}.

K. Lee and M. E. O’Sullivan. List decoding of [Reed-Solomon]{} codes from a Gröbner basis perspective. *J. Symbolic Comput.*, 43(9):645–658, Sept. 2008. [doi: ]{}[10.1016/j.jsc.2008.01.002]{}.

K. Lee and M. E. O’Sullivan. List decoding of Hermitian codes using Gröbner bases. *J. Symbolic Comput.*, 44(12):1662–1675, Dec. 2009. [doi: ]{}[10.1016/j.jsc.2007.12.004]{}. arXiv:cs/0610132.

K. Lee, M. Bras-Amorós, and M. E. O’Sullivan. Unique decoding of plane AG codes via interpolation. *IEEE Trans. Inform. Theory*, 58(6):3941–3950, June 2012. [doi: ]{}[10.1109/TIT.2012.2182757]{}. arXiv:1110.6251.

R. Matsumoto and S. Miura. On the Feng-Rao bound for the $\mathcal{L}$-construction of algebraic geometry codes. *IEICE Trans. Fundamentals*, E83-A(5):926–930, May 2000. URL <http://www.rmatsumoto.org/repository/e83-a_5_923.pdf>.

R. Matsumoto and S. Miura. Finding a basis of a linear system with pairwise distinct discrete valuations on an algebraic curve. *J. Symbolic Comput.*, 30(3):309–323, Sept. 2000. [doi: ]{}[10.1006/jsco.2000.0372]{}.

R. Matsumoto and S. Miura. On construction and generalization of algebraic geometry codes. In T. Katsura et al., editors, *Proc. Algebraic Geometry, Number Theory, Coding Theory, and Cryptography*, pages 3–15, Univ. Tokyo, Japan, Jan. 2000. URL <http://www.rmatsumoto.org/repository/weight-construct.pdf>.

R. Matsumoto, D. Ruano, and O. Geil. Generalization of the Lee-O’Sullivan list decoding for one-point AG code. *J. Symbolic Comput.*, 55:1–9, Aug. 2013. [doi: ]{}[10.1016/j.jsc.2013.03.001]{}. arXiv:1203.6129.

C. P. McKeague. *Elementary Algebra*. Brooks Cole, Florence, KY 41022-6904, USA, 9th edition, 2012. ISBN 0840064217.

S. Miura. Algebraic geometric codes on certain plane curves. *Electronics and Communications in Japan (Part III: Fundamental Electronic Science)*, 76(12):1–13, Dec. 1993. [doi: ]{}[10.1002/ecjc.4430761201]{}. (original Japanese version published as Trans. IEICE, vol. J75-A, no. 11, pp. 1735–1745, Nov. 1992).

S. Miura. Linear codes on affine algebraic curves. *Trans. IEICE*, J81-A(10):1398–1421, Oct. 1998.

R. Pellikaan. On the efficient decoding of algebraic-geometric codes. In P. Camion, P. Charpin, and S. Harari, editors, *Eurocode ’92 International Symposium on Coding Theory and Applications*, number 339 in CISM Courses and Lectures, pages 231–253. CISM International Centre for Mechanical Sciences, Springer, 1993. URL <http://www.win.tue.nl/~ruudp/paper/17.pdf>.

J. C. Rosales and P. A. García-Sánchez. *Numerical Semigroups*, volume 20 of *Developments in Mathematics*. Springer, New York, 2009. ISBN 978-1-4419-0159-0.

K. Saints and C. Heegard. Algebraic-geometric codes and multidimensional cyclic codes: A unified theory and algorithms for decoding using Gröbner bases. *IEEE Trans. Inform. Theory*, 41(6):1733–1751, Nov. 1995. [doi: ]{}[10.1109/18.476246]{}.

S. Sakata. On fast interpolation method for Guruswami-Sudan list decoding of one-point algebraic-geometry codes. In S. Boztaş and I. E. Shparlinski, editors, *Proc. AAECC-14*, volume 2227 of *Lecture Notes in Computer Science*, pages 172–181, Melbourne, Australia, Nov. 2001. Springer-Verlag. [doi: ]{}[10.1007/3-540-45624-4\_18]{}.

S. Sakata. Multivariate interpolation and list decoding. In K. Kobayashi and H. Morita, editors, *Proc. 3rd Asian-European Workshop on Information Theory*, pages 28–31, Kamogawa, Chiba, Japan, June 2003. Society of Information Theory and its Applications. ISBN 4-902087-04-9.

S. Sakata and M. Fujisawa. Fast decoding of multipoint codes from algebraic curves up to the order bound. In *Proc. SITA2011*, pages 417–422, Iwate, Japan, Nov. 2011.

S. Sakata, H. Elbrønd Jensen, and T. Høholdt. Generalized Berlekamp-Massey decoding of algebraic-geometric codes up to half the Feng-Rao bound. *IEEE Trans. Inform. Theory*, 41(5):1762–11768, Sept. 1995. [doi: ]{}[10.1109/18.476248]{}.

S. Sakata, J. Justesen, Y. Madelung, H. Elbrønd Jensen, and T. Høholdt. Fast decoding of algebraic geometric codes up to the designed minimum distance. *IEEE Trans. Inform. Theory*, 41(5):1672–1677, Sept. 1995. [doi: ]{}[10.1109/18.476240]{}.

J. Schicho. Inversion of birational maps with Gröbner bases. In B. Buchberger and F. Winkler, editors, *Gröbner Bases and Applications*, volume 251 of *London Mathematical Society Lecture Note Series*, pages 495–503. Cambridge University Press, 1998. ISBN 9780521632980. [doi: ]{}[10.1017/CBO9780511565847.031]{}.

M. A. Shokrollahi and H. Wasserman. List decoding of algebraic-geometric codes. *IEEE Trans. Inform. Theory*, 45(2):432–437, Mar. 1999. [doi: ]{}[10.1109/18.748993]{}.

L.-Z. Tang. A Gröbner basis criterion for birational equivalence of affine varieties. *J. Pure Appl. Algebra*, 123(1-3):275–283, Jan. 1998. [doi: ]{}[10.1016/S0022-4049(97)00139-4]{}.

D. Umehara and T. Uyematsu. One-point algebraic geometric codes from Artin-Schreier extensions of Hermitian function fields. *IEICE Trans. Fundamentals*, E81-A(10):2025–2031, Oct. 1998.

W. V. Vasconcelos. *Computational Methods in Commutative Algebra and Algebraic Geometry*, volume 2 of *Algorithms and Computation in Mathematics*. Springer-Verlag, Berlin, 1998.

C. Voss and T. Høholdt. An explicit construction of a sequence of codes attaining the Tsfasman-Vlăduţ-Zink bound. *IEEE Trans. Inform. Theory*, 43(1):128–135, Jan. 1997. [doi: ]{}[10.1109/18.567659]{}.

[^1]: Department of Communications and Computer Enginnering, Tokyo Instiutte of Technology, 152-8550 Japan.

[^2]: Department of Mathematical Sciences, Aalborg University, Denmark.
