List Decoding Algorithm based on Voting in Groebner Bases for General One-Point AG Codes

We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amor\'os and O'Sullivan (2012) 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 Andersen and Geil (2008) 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 empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010). It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010; Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs.


Introduction
We consider the list decoding of one-point algebraic geometry (AG) codes. Guruswami and Sudan (1999) 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 Beelen and Brander (2010, Figure 1).
By modifying the unique decoding algorithm (Lee et al., 2012) for primal onepoint AG codes, we propose another list decoding algorithm based on voting in Gröbner bases whose error correcting capability is higher than Guruswami and Sudan (1999) and whose computational complexity is empirically smaller than Beelen and Brander (2010); Guruswami and Sudan (1999) in many cases that are examined and reported in our computational experiments. It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010;Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs. A decoding algorithm for primal one-point AG codes was proposed in Matsumoto and Miura (2000c), which was a straightforward adaptation of the original Feng-Rao majority voting for the dual AG codes (Feng and Rao, 1993) to the primal ones. The Feng-Rao majority voting in Matsumoto and Miura (2000c) for one-point primal codes was generalized to multi-point primal codes in Beelen and Høholdt (2008, Section 2.5). The one-point primal codes can also be decoded as multi-point dual codes with majority voting (Beelen, 2007;Duursma et al., 2011;Duursma and Park, 2010), whose faster version was proposed in Sakata and Fujisawa (2011) for the multipoint Hermitian codes. Lee, Bras-Amorós and O'Sullivan (2012) 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 (Lee et al., 2012) is a curve theoretic generalization of one used for Reed-Solomon codes in Ali and Kuijper (2011) that is a special case of the module used in Lee and O'Sullivan (2008). An interesting feature in Lee et al. (2012) is that it did not use differentials and residues on curves for its majority voting, while they were used in Beelen and Høholdt (2008); Matsumoto and Miura (2000c). The above studies (Beelen and Høholdt, 2008;Lee et al., 2012;Matsumoto and Miura, 2000c) dealt with the primal codes. We recently proved in Geil et al. (2013) that the errorcorrecting capabilities of Lee et al. (2012); Matsumoto and Miura (2000c) are the same. The earlier papers (Duursma, 1994;Pellikaan, 1993) suggest that central observations in Andersen and Geil (2008); Geil et al. (2013); Matsumoto and Miura (2000c) were known to the Dutch group, which is actually the case (Duursma, 2012). Chen (1999), Elbrønd Jensen et al. (1999) and Bras-Amorós and O'Sullivan

Notation, Preliminaries and the Statement of Problem
Our study heavily relies on the standard form of algebraic curves introduced independently by Geil and Pellikaan (2002) and Miura (1998), which is an enhancement of earlier results (Miura, 1993;Saints and Heegard, 1995). Let F/F q be an algebraic function field of one variable over a finite field 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 where ev( f ) = ( f (P 1 ), . . . , f (P n )). The problem considered in this paper is as follows: We use a linear code C u (or its improved version C Γ defined in Eq. (4)). A codeword in C u (or C Γ ) is transmitted, and the receiver receives r ∈ F n q . A list-decoding algorithm with a decoding radius τ finds all the codewords in C u (or C Γ ) whose Hamming distances from r are within τ. Our aim is to propose another list-decoding algorithm based on Gröbner bases and demonstrate its computational complexity in a wide range of examples.
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 ) ∞ = a i Q 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 L(∞Q) = ∪ ∞ i=1 L(iQ) is equal to F q [x 1 , . . . , x t ] (Saints and Heegard, 1995). We express L(∞Q) as a residue class ring F q [X 1 , . . . , X t ]/I of the polynomial ring F q [X 1 , . . . , X t ], where X 1 , . . . , X t are transcendental over F q , and I is the kernel of the canonical homomorphism sending X i to x i . Geil and Pellikaan (2002); Miura (1998) identified the following convenient representation of L(∞Q) by using Gröbner basis theory (Buchberger, 1965) (See, for example, a textbook (Adams and Loustaunau, 1994)). The following review is borrowed from Matsumoto and Miura (2000b). Hereafter, we assume that the reader is familiar with the Gröbner basis theory in Adams and Loustaunau (1994).
Example 1 The Klein quartic over F 8 is given by the equation There exists a unique F 8 -rational place Q, namely (0 : 1 : 0), that is a unique pole of v. The numbers 3, 5 and 7 is the minimal generating set of the Weierstrass semigroup at Q. Define three functions Høholdt and Pellikaan (1995, Example 3.7). By Tang (1998, Theorem 4.1) we can see that the standard form of the Klein quartic is given by which is the reduced Gröbner basis with respect to the monomial order ≻. We can see that a 1 = 3, a 2 = 5, and a 3 = 7.
Example 2 Consider the function field This is the third function field in the asymptotically good tower introduced by Garcia and Stichtenoth (1995). Substituting v 2 with u 1 u 2 and v 3 with u 2 u 3 in Eq.
For i = 0, . . . , a 1 − 1, we define b i = min{m ∈ H(Q) | m ≡ i (mod a 1 )}, and L i to be the minimum element (m 1 , . . . , m t ) ∈ N t 0 with respect to ≺ such that a 1 m 1 + · · ·+a t m t = b i . Note that b i 's are the well-known Apéry set (Rosales and García-Sánchez, 2009, Lemmas 2.4 and 2.6) of the numerical semigroup H(Q). Then we have is not the leading monomial of any nonzero polynomial in I with respect to ≺}, and Then Ω 0 is a basis of L(∞Q) as an F q -linear space (Adams and Loustaunau, 1994), two distinct elements in Ω 0 have different pole orders at Q, and Equation (3) shows that L(∞Q) is a free F q [x 1 ]-module with a basis {y 0 , . . . , y a 1 −1 }. Note that the above structured shape of Ω 0 reflects the well-known property of every weighted reverse lexicographic monomial order, see the paragraph preceding to Eisenbud (1995, Proposition 15.12).
Remark 3 For a description of the proposed algorithm, only a 1 , b 1 , . . . , b a 1 −1 , y 1 , . . . , y a 1 −1 are absolutely necessary, and we can remove ϕ s , x 2 , . . . , x t , a 2 , . . . , a t , X 1 , . . . , X t , Y 1 , . . . , Y t from our presentation. However, we retain those notations for the following two reasons: Firstly, because s will be used as the iteration variable and our proposed algorithm will focus on the monomial in Ω 0 whose pole order at Q is s, the notation ϕ s clarifies the relation between s and the monomial in Ω 0 focused in the s-th iteration.
Secondly, the proposed algorithm needs to find the normal form of a function in L(∞Q) that is an F q -linear combination of monomials in Ω 0 . Functions in L(∞Q) are represented by multivariate polynomials over F q . The specific definition of X 1 , . . . , X t and the specific choice of the monomial order in F q [X 1 , . . . , X t ] enable us to compute the normal form just by the standard Gröbner basis division, and make implementation of our proposal easier in practice. Thirdly, Y 1 , . . . , Y t will be used to explain how we count the computational cost. They are necessary to allow readers to reproduce our experimental results presented later in this paper.
Let v Q be the unique valuation in F associated with the place Q. The semigroup (Rosales and García-Sánchez, 2009, Lemma 2.6). By Matsumoto and Miura (2000b, Proposition 3.18), for each nongap s ∈ H(Q) there is a unique monomial x i 1 y j ∈ Ω 0 with 0 ≤ j < a 1 such that −v Q (x i 1 y j ) = s, and let us denote this monomial by ϕ s . Let Γ ⊂ H(Q), and we may consider the one-point codes where · denotes the F q -linear space spanned by ·. Since considering linearly dependent rows in a generator matrix has no merit, we assume where H(Q) = {u ∈ H(Q) | C u C u−1 }. One motivation for considering these codes is that it was shown in Andersen and Geil (2008) how to increase the dimension of the one-point codes without decreasing the lower bound d AG for the minimum distance. The bound d AG (C Γ ) is defined for C Γ as follows (Andersen and Geil, 2008): For s ∈ Γ, let Then d AG (C Γ ) = min{λ(s) | s ∈ Γ}. It is proved in Geil et al. (2011) that d AG gives the same estimate for the minimum distance as the Feng-Rao bound (Feng and Rao, 1993) for one-point dual AG codes when both d 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 Geil et al. (2011) that d AG (C Γ ) can be obtained from the bounds in Beelen (2007); Duursma et al. (2011); Duursma and Park (2010), hence d AG can be understood as a particular case of these bounds (Beelen, 2007;Duursma et al., 2011;Duursma and Park, 2010).

Overall Structure
Suppose that we have a received word r ∈ F n q . We shall modify the unique decoding algorithm proposed by Lee et al. (2012) so that we can find all the codewords in C Γ in Eq. (4) within the Hamming distance τ from r. τ is a parameter independent of r, and τ is chosen before reception of r. The overall structure of the modified algorithm is as follows: 1. Precomputation before getting a received word r, 2. Initialization after getting a received word r, 3. Termination criteria of the iteration, and 4. Main part of the iteration.
Steps 2 and 4 are based on Lee et al. (2012). Steps 1 and 3 are not given in Lee et al. (2012). Each step is described in the following subsections in Section 3. We shall analyze time complexity except the precomputation part of the algorithm.

Modified Definitions for the Proposed Modification
We retain notations from Section 2. In this subsection, we modify notations and definitions in Lee et al. (2012) to describe the proposed modification to their algorithm. We also introduce several new notations. Define a set Our Ω 1 is Ω in Lee et al. (2012). Recall also that Since the F q [x 1 ]-module L(∞Q)z ⊕ L(∞Q) has a free basis {y j z, y j | 0 ≤ j < a 1 }, we can regard Ω 1 as the set of monomials in the Gröbner basis theory for modules. We introduce a monomial order on Ω 1 as follows. For given two monomials x i 1 1 y j z i t+1 and x i ′ 1 1 y j ′ z i ′ t+1 , first rewrite y j and y j ′ by x 2 , . . . , x t defined in Section 2 and get Observe that the restriction of < s to Ω 0 is equal to ≺ defined in Section 2. 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 ∈ L(∞Q)z ⊕ L(∞Q), γ( f ) denotes the number of nonzero terms in f when f is expressed as an F q -linear combination of monomials in Ω 1 . γ 1 ( f ) denotes the number of nonzero terms whose coefficients are not 1 ∈ F q .
For each (i, j), express y i y j as an F q -linear combination of monomials in Ω 0 . Such expressions will be used for computing products and quotients in L(∞Q) as explained in Section 3.4.1. From the above data, we can easily know lc(y i y j ), which will be used in Eqs. (14) and (22).
Find elements ϕ s ∈ Ω 0 with s ∈ H(Q). There are n such elements, which we denote by ψ 1 , .

Multiplication and Division in an Affine Coordinate Ring
In both of the original unique decoding algorithm (Lee et al., 2012) and our modified version, we need to quickly compute the product gh of two elements g, h in the affine coordinate ring L(∞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 3.6. Since the authors could not find quick computational procedures for those tasks in L(∞Q), we shall present such ones here.

Multiplication in an Affine Coordinate Ring
The normal form of g, for g ∈ L(∞Q), is the expression of g written as an F q -linear combination of monomials ϕ s ∈ Ω 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 , which is computed in Section 3.3. We denote by X 1 , Y 1 , . . . , Y a 1 −1 algebraically independent variables over 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 Therefore, the total number of multiplications in F q is at most Define Eq. (11) as multi(g, h). We emphasize that when the characteristic of F q is 2 and all the coefficients of defining equations belong to F 2 , which is almost always the case for those cases of interest for applications in coding theory, then γ 1 ( a 1 −1 k=0 y k f i, j,k (x 1 )) in Eq. (11) is zero. This means that L(∞Q) has little additional overhead over F q [X] for computing products of their elements in terms of the number of F q -multiplications and divisions.

Remark 5 Define
The right hand side of Eq. (9) can be written as By using Eq. (12) instead of Eq. (9), we have another upper bound on the number of multiplications as we have Eq. (13) ≤ Eq. (11). However, Eq. (13) is almost always the same as Eq.
(11) over the curve in Example 2, and Eq. (13) will not be used in our computer experiments in Section 5.

Computation of the Quotient
Assume h 0. The following procedure computes the quotient g/h ∈ L(∞Q) or declares that g does not belong to the principal ideal of L(∞Q) generated by h.
If not, declare that g does not belong to the principal ideal of L(∞Q) generated by h, and finish the procedure.
Computation of tϕ s needs one multiplication and one division in

Compute the normal form of tϕ s h, which requires at most multi(tϕ
5. Update σ ← σ + tϕ s and g ← g − tϕ s h. If the updated g is zero, then output the updated σ as the quotient and finish the procedure. Otherwise go to Step 2. This step has no multiplication nor division. Define quot(g, h) as ζ after finishing the above procedure. quot(g, h) is an upper bound on the number of multiplications and divisions in F q in the above procedure. The program variable ζ is just to define quot(g, h), and the decoding algorithm does not need to update ζ. Observe also that the above procedure is a straightforward generalization of the standard long division of two univariate polynomials (McKeague, 2012).

Initialization after Getting a Received Word r
Therefore, the total number of multiplications in the initialization is at most Let s = N and execute the following steps.

Three Termination Criteria of the Iteration
After finishing the initialization step in Section 3.5, we iteratively compute f (s) i and 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 (s) We describe the first part in Section 3.6. Let 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 Ali and Kuijper (2011, Theorem 12) from the case g = 0 to g > 0. Ali and Kuijper (2011, Theorem 12) proved that if the number δ of errors satisfies 2δ < d RS (C s ), where d 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 −α 0 /α 1 . To one-point primal AG codes, d RS (C s ) can be generalized as either d AG (C s ) or n − s − g. The former generalization d AG (C s ) corresponds to the first criterion in Section 3.6.1 and the latter n − s − g corresponds to the second in Section 3.6.2.
The third one is almost the same as the original procedure in Lee et al. (2012). The first one was proposed in Geil et al. (2012) while the second and the third ones are new in this paper. We shall compare the three criteria in Section 5.2. Throughout this paper, wt( x) denotes the Hamming weight of a vector x ∈ F n q . The proposed decoding algorithm can perform both unique decoding and list decoding depending on whether or not d AG (C Γ (≤s) ) > 2τ. To provide a unified presentation of both variants of our proposal, we will include the condition d AG (C Γ (≤s) ) > 2τ in the following. Observe that the condition d AG (C Γ (≤s) ) > 2τ can be checked when one implements our proposal by an electronic circuit or a computer software, before executing the proposed algorithm.

If
• s ∈ Γ, • d AG (C Γ (≤s) ) > 2τ, and then do the following: multiplications and divisions in F q .
2. If α 0 /α 1 ∈ L(∞Q) and α 0 /α 1 can be written as a linear combination of monomials in {ϕ s ′ ∈ s ′ ∈ Γ (≤s) }, then do the following: into the list of transmitted information vectors, and avoid proceeding with the rest of the decoding procedure. When Γ (>s) = ∅, the summation over Γ (>s) is regarded as zero.
then include the coefficients of −α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ into the list of transmitted information vectors, and avoid proceeding with s. Otherwise, continue the iterations unless s < n − g − 2τ.
. This needs at most multiplications and divisions in F q .
5. Finish the iteration no matter what happened in the above steps.

Third Criterion for Judging Termination
The third criterion terminates the algorithm when it finds f (s) i at s = −1 for i = 0, . . . , a 1 − 1 in the main iteration presented in Section 3.7. If 2τ < d AG (C Γ ) then declare the vector (w s : s ∈ Γ) as the only transmitted information and finish.
If 2τ ≥ d AG (C Γ ) then do the following: 1. If α 0 = 0 and −v Q (α 1 ) ≤ τ then include the vector (w s : s ∈ Γ) into the list of transmitted information vectors. Finish the iteration.
3. Otherwise compute ev( s∈Γ w s ϕ s ). This needs at most multiplications and divisions in F q .
then include the vector (w s : s ∈ Γ) into the list of transmitted information vectors. Finish the iteration.

Iteration of Pairing, Voting, and Rebasing
The iteration of the original algorithm (Lee et al., 2012) 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 and let ν (s) i = lc(d i,i ). We assume that lt( f (s) i ) = a i,i y i z and lt(g (s) i ) = d i,i y i . For 0 ≤ i < a 1 , as in Lee et al. (2012) there are unique integers 0 ≤ i ′ < a 1 and k i satisfying Note that by the definition above

Voting
For each i ∈ {0, . . . a 1 − 1}, we set where We remark that the leading coefficient µ i must be considered after expressing a i,i y i ϕ s by monomials in Ω 0 .
Observe that lc(y i ϕ s ) = lc(y i y s mod a 1 ) and that lc(y i y s mod a 1 ) is already precomputed as Section 3.3. By using that precomputed table, computation of µ i needs one multiplication. The total number of multiplications and divisions in Eq. (22) is 2a 1 excluding negation from the number of multiplication. Let We consider two different candidates depending on whether s ∈ Γ or not: • If s ∈ Γ, let w be one of the element(s) in F q with Let w s = w. If several w's satisfy the condition above, repeat the rest of the algorithm for each of them.

Rebasing
In all of the following cases, we need to compute the normal form of the product wϕ s × a 1 −1 j=0 a i, j y j , and the product wϕ s × a 1 −1 j=0 c i, j y j . For each i, the number of multiplications is ≤ multi(wϕ s , where multi(·, ·) is defined in Section 3.4.1.
• If w s,i = w, then let where the parentheses denote substitution of the variable z and let ν The number of multiplications in this case is bounded by Eq. (27).
• If w s,i w and c i > 0, then let Computation of needs one multiplication and one division. The product of and g (s) i ′ (z + wϕ s ) needs γ(g (s) i ′ (z + wϕ s )) multiplications, where γ is defined in Section 3.4.1. Thus, the number of multiplications and divisions is • If w s,i w and c i ≤ 0, then let needs one multiplication and one division. The product of where γ is defined in Section 3.4.1. Thus, the number of multiplications and divisions is ≤ Eq. (28).
After computing f (prec(s)) i and g (prec(s)) i as above, update the program variable s to prec(s) and return to the beginning of Section 3.6, that is, return to the step of the chosen termination criterion.

Difference to the Original Method
In this subsection, we review advantages of our modified algorithm over the original (Lee et al., 2012).
• Our version can handle any one-point primal AG codes, while the original can handle codes only coming from the C ab curves (Miura, 1993). This generalization is enabled only by replacing y j in Lee et al. (2012) by y j defined in Section 2.
• Our version can find all the codewords within Hamming distance τ from the received word 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 H(Q), while the original computes them for N ≥ s H(Q).
• The original algorithm assumed u < n, where u is as defined in Eq. (1).
This assumption is replaced by another less restrictive assumption (5) in our version.
• Our version supports the Feng-Rao improved code construction (Feng and Rao, 1995), while the original does not. This extension is made possible by the change at Eq. (25).
• The first and the second termination criteria come from Ali and Kuijper (2011, Theorem 12) and do not exist in the original (Lee et al., 2012).
• The third termination criterion is essentially the same as the original (Lee et al., 2012), but examination of the Hamming distance between the decoded codeword and r is added when 2τ ≥ d AG (C Γ ).
• The original (Lee et al., 2012) is suitable for parallel implementation on electric circuit similar to the Kötter architecture (Kötter, 1998). Our modified version retains this advantage.
We use C u with u = 4 for decoding. Then Γ = {0, 2, 3, 4} and d AG (C Γ ) = 4. We shall try to correct τ = 2 errors. Suppose that 0 was transmitted and r = (0, 0, 1, 1, 0, 0, 0, 0) was received. This received word r has four codewords within Hamming distance 2, and all of them are found by the proposed decoding algorithm. We shall show how one of the four codeword is found.
According to Section 3.5, we have h r = u 3 + u 2 + u, which implies N = −v Q (h r ) = 6. We start the iteration from s = 6(= N), and again according to Section 3.5 we have At the iteration for s = 6 none of the temination criteria is satisfied. Since 6 Γ, we do not need voting and set w 6 = 0, and we compute new polynomials as At the iteration for s = 5 none of the temination criteria is satisfied. Since 5 Γ, we do not need voting and set w 5 = 0, and we compute new polynomials as At the iteration for s = 4 none of the temination criteria is satisfied. We need voting at s = 4, and all the candidates 0, 1, β, β 2 in F 4 get zero vote. Therefore, the execution of the proposed algorithm splits to four branches at s = 4. Firstly we consider the choice w 4 = 1, which will result in an incorrect decoding.
The choice w 4 = 1 gives At the iteration for s = 3 only the first temination criterion is satisfied. We have α 0 = u 2 + u and α 1 = u, and the decoded codeword by the first criterion is (1, 1, 1, 1, 0, 0, 0, 0) which is at the Hamming distance 2 from r but not equal to the transmitted codeword.
The second or the third termination criterion is not satisfied. In the voting for s = 3, w 3 = 0 is chosen with two votes while other candidates get zero vote. The choice w 3 = 0 gives 1 .
At the iteration for s = 2 the second temination criterion is satisfied. The computation process and the decoded codeword by the second criterion at s = 2 are the same as those by first criterion at s = 3.
In the voting for s = 2, w 2 = 0 is chosen with two votes while other candidates get zero vote. The choice w 2 = 0 gives 1 .
In the voting for s = 1, w 1 = 1 is chosen with two votes while other candidates get zero vote. The choice w 1 = 0 gives In the voting for s = 0, w 0 = 1 is chosen with four votes while other candidates get zero vote. The choice w 0 = 1 gives At s = −1, we find α 0 = 0, α 1 = u and 2 = −v Q (α 1 ) ≤ τ = 2. Thus the algorithm outputs (w s ) s∈Γ as decoded information by the third termination criterion. The decoded codeword is again (1, 1, 1, 1, 0, 0, 0, 0). The three termination criterion give the same decoded codeword, but their numbers of iterations are different.
Recall that all of candidates w 4 = 0, 1, β, β 2 are chosen by voting at s = 4 because all the candidates have the same number of votes. Only w 4 = 0 gives the correct codeword, while w 4 = β and w 4 = β 2 give two other different incorrect codewords whose Hamming distances are both 2 from r. In this example, multiple candidates are chosen only at s = 4.

Theoretical Analysis of the Proposed Modification
In this section we prove that our modified algorithm can find all the codewords within Hamming distance τ from the received word r. We also give upper bounds on the number of iterations in Section 4.6.

Supporting Lemmas
In Section 4.1 we shall introduce several lemmas necessary in Sections 4.2-4.5. Recall that the execution of our modified algorithm can branch when there are multiple candidates satisfying the condition (26). For a fixed sequence of determined w s , define r (N) = r and recursively define r (prec(s)) = r (s) − ev(w s ϕ s ). By definition r (−1) = r − ev( s∈Γ w s ϕ s ).
The following lemma explains why the authors include "Gröbner bases" in the paper title. The module I r (N) where r (s) = (r (s) 1 , . . . , r (s) n ) . The following proposition shows that the original decoding algorithm Lee et al. (2012) can correct errors up to half the bound d AG (C Γ ), which was not claimed in Lee et al. (2012).

Proof. Let
where the third equality holds by Eq. (21). By the equalities above, we see which proves the equality ν(s) = λ(s). Lee et al. (2012) showed that their original decoding algorithm can correct up to ⌊(d LBAO (C u ) − 1)/2⌋ errors, where d LBAO (C u ) = min{ν(s) | s ∈ H(Q), s ≤ u}. Proposition 7 implies that d LBAO (C u ) is equivalent to d AG (C u ) for every one-point primal code C u , and therefore Andersen and Geil (2008, Theorem 8) implies Lee et al. (2012, Proposition 12). In another recent paper Geil et al. (2013) we proved that d AG and d LBAO are equal to the Feng-Rao bound as defined in Beelen and Høholdt (2008); Matsumoto and Miura (2000c) for C u .

Lower Bound for the Number of Votes
In Section 4.2 we discuss the number of votes (26) 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 Lee et al. (2012). Nevertheless, the original theorems in Lee et al. (2012) allow natural generalizations to the list decoding context.  Matsumoto and Miura (2000a)).
Let {ǫ 0 , . . . , ǫ a 1 −1 } be a Gröbner basis for J e as an F q [x 1 ]-module with respect to < s (for any integer s), such that lm(ǫ j ) = x k j 1 y j . Under the above notations, we have for i with w s,i ω s , and for i with w s,i = ω s .
Proof. The proof is the same as those of Lee et al. (2012, Propositions 7 and 8), with replacing y j in Lee et al. (2012) by y j , δ(·) in Lee et al. (2012) The following lemma is a modification to Lee et al. (2012, Proposition 9) for the list decoding.

Lemma 9
We retain notations from Lemma 8. We have

Now we have a chain of inequalities
where at Eq. (30) we used the equality shown in Lee et al. (2012, Lemma 2 and Eq. (1)). Finally note that by Lee et al. (2012, Eq. ( 3)).
The following lemma is a modification to Lee et al. (2012, Proposition 10) for list decoding, and provides a lower bound for the number of votes (26) received by any candidate ω s ∈ F q , as indicated in the section title.

Correctness of the Modified List Decoding Algorithm with the Third Iteration Termination Criterion
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 τ from the received word 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 ∈ Γ. If wt( r − ev( s∈Γ w s ϕ s )) ≤ τ then the sequence w s is found by the algorithm because of Proposition 10. When 2τ < d AG (C Γ ), by Proposition 7 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τ ≥ d AG (C Γ ), then the found sequence could correspond to a codeword more distant than Hamming distance τ, and the algorithm examines the Hamming distance between the found codeword and the received word r.
Since computing ev( f ) for f ∈ L(∞Q) needs many multiplications in F q , the algorithm checks some sufficient conditions to decide the Hamming distance between the found codeword and the received word r. Let r (−1) = (r (−1) 1 , . . . , r (−1) n ). When α 0 = 0 in Section 3.6.3, by Lemma 6, we have because Eq. (29) and α 0 = 0 implies that v P i (α 1 ) ≥ 1 for r (−1) i 0. By the above equation, −v Q (α 1 ) ≤ τ implies that the found codeword is within Hamming distance τ from r. This explains why the algorithm can avoid computation of the evaluation map ev in Step 1 in Section 3.6.3.
In order to explain Step 2 in Section 3.6.3, we shall show that the condition of Step 2 in Section 3.6.3 implies that wt( r − ev( s∈Γ w s ϕ s )) > τ. Suppose that wt( r − ev( s∈Γ w s ϕ s )) ≤ τ. Then there exists β 1 ∈ L(∞Q) such that v P i (β) ≥ 1 for r (−1) i 0, −v Q (β) ≤ τ + g, and β 1 z ∈ I r (−1) . Because the leading term of β 1 z must be divisible by lt( f (−1) i ) for some i by the property of Gröbner bases, we must have −v Q (α 1 ) ≤ −v Q (β 1 ). This explains why the algorithm can avoid computation of the evaluation map ev in Step 2 in Section 3.6.3.
Otherwise, the algorithm computes the Hamming distance between the found codeword and r in Steps 3 and 4 in Section 3.6.3.

Correctness of the Modified List Decoding Algorithm with the Second Iteration Termination Criterion
We shall explain why the second criterion in Section 3.6.2 correctly finds the required codewords. For explanation, we present slightly rephrased version of facts in Beelen and Høholdt (2008).
i , and assume that g has the minimum pole order at Q among such elements in L(∞Q). Then −v Q (g) ≤ τ + g. One has that gz − f g ∈ I r (s) and lt(gz − f g) = lt(gz) with respect to < s . By the property of Gröbner bases, lt(gz) is divisible by lt We explain how the procedure in Section 3.6.2 works as desired. When the condition in Step 1 in Section 3.6.2 is true, then there cannot be a codeword within Hamming distance τ from r (s) by the same reason as Section 4.3. So the algorithm stops processing with r (s) .
When 2τ ≥ d AG (C Γ ), then the algorithm examines the found codeword close enough to r in Steps 4a and 4b in Section 3.6.2. When −v Q (α 1 ) ≤ τ we can avoid computation of the evaluation map ev by the same reason as Section 4.3, which is checked at Step 4a. Otherwise we compute the codeword vector at Step 4b and examine its Hamming distance to r (s) .

Correctness of the Modified List Decoding Algorithm with the First Iteration Termination Criterion
We shall explain why the first criterion in Section 3.6.1 correctly finds the required codewords. The idea behind the first criterion is that there cannot be another codeword within Hamming distance τ from r (s) when the algorithm already found one. So the algorithm can stop iteration with smaller s once a codeword is found as ev(−α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ ). The algorithm does not examine conditions when −v Q (α 1 ) > τ + g by the same reason as Sections 4.3 and 4.4. When 2τ < d AG (C Γ ), then the algorithm declares −α 0 /α 1 + s ′ ∈Γ (>s) w s ′ ϕ s ′ as the unique codeword.
When 2τ ≥ d AG (C Γ ), then the algorithm examines the found codeword close enough to r in Steps 2a-2c in Section 3.6.1. When −v Q (α 1 ) ≤ τ we can avoid computation of the evaluation map ev by the same reason as Section 4.3, which is checked at Step 2a.

Upper Bound on the Number of Iterations and the Worst Case Complexity
Observe that for s > max Γ we set always w s to 0. For each s ∈ Γ satisfying ν(s) ≤ 2τ, the number of accepted candidates satisfying Eq. (26) can be at most q.
On the other hand, for s with ν(s) > 2τ, the number of candidates is either zero or one, because at most one w ∈ F q can satisfy Eq. (26). Therefore, we have upper bounds for the number of iterations, counting executions of Rebasing in Section 3.7.3, as for the third criterion for judging termination, where exp q (x) = q x , and for the first and the second criteria for judging termination. We will use max H(Q) in place of N in Eqs. (31) and (32) for computation in Tables 1-4, because N depents on r and N ≤ max H(Q). The proposed algorithm processes 2a 1 polynomials (elements in L(∞Q)) in each iteration and each polynomial has O(n) terms. For a precise closed-form evaluation of Eqs. (31) and (32), we need a closed-form upper bound of ♯{s ∈ Γ | ν(s) ≤ 2τ} in terms of τ, but the authors could not find such one. Clearly n is an upper bound on ♯{s ∈ Γ | ν(s) ≤ 2τ}, and the number of iterations is O(exp q (n)). Therefore the worst-case complexity is O(a 1 n exp q (n)). Nonetheless, we will see that the actual computational cost can be lower than the existing list decoding algorithms in some cases in Section 5. We remark that when τ < d AG (C Γ ) the number of iterations is ≤ n and the worst case complexity is O(a 1 n 2 ) because the number of chosen candidate is at most one by voting at each iteration, and that the complexity O(a 1 n 2 ) is the same as the BMS algorithm (Sakata et al., 1995a,b).
Observe that the list decoding can be implemented as exp q (♯{s ∈ Γ | ν(s) ≤ 2τ}) parallel execution of the unique decoding. Therefore, when one can afford exp q (♯{s ∈ Γ | ν(s) ≤ 2τ}) parallel implementation, which increases the circuit size, the decoding time of list decoding is the same as that of the unique decoding.

Simulation Condition and Results
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 F 8 with n = 23 by using Examples 1 and 4, the one-point Hermitian codes over F 16 with n = 64, and the one-point primal codes on the curve in Example 2 over F 9 with n = 77.
The program is implemented on the Singular computer algebra system (Decker et al., 2011). The program used for this simulation is available from http://arxiv.org/src/1203.6127v5/anc.
In  (27) and (28), and the number of codewords found. Note also that Eq. (11) instead of Eq. (13) is used.
The parameter τ 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 2 and 3 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 Γ . That of error vectors is uniform on the vectors of Hamming weight τ.
In the code construction, we always try to use the Feng-Rao improved construction. Specifically, for a given designed distance δ, we choose Γ = {s ∈ H(Q) | λ(s) = ν(s) ≥ δ}, and construct C Γ of Eq. (4). In the following, the designed distance is denoted by d AG (C Γ ). It can be seen from Tables 1-4 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 (Guruswami and Sudan, 1999).

Comparison among the Three Proposed Termination Criteria
In Section 3.6 we proposed three criteria for terminating iteration of the proposed algorithm. From Tables 1-4, 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 Geil et al. (2012) and we see that the new criteria are better than the old one. The reason is as follows: The computation of quotient α 0 /α 1 at Step 1 in Section 3.6.1 is costlier than updating f (s) i and g (s) i in Section 3.7.3 and the first criterion computes α 0 /α 1 many times, which cancels the effect of decrease in the number of iterations. On the other hand, the second criterion computes α 0 /α 1 only once, so it has the smaller number of multiplications and divisions than the first.
The second criterion is faster when 2τ < d AG (C Γ ), while the third tends to be faster when 2τ ≥ d AG (C Γ ). In addition to this, the ratio of the number of iterations in the second criterion to that of the third is smaller with 2τ < d AG (C Γ ) than with 2τ ≥ d AG (C Γ ). We speculate the reason behind them as follows: When 2τ ≥ d AG (C Γ ) and a wrong candidate is chosen at Eq. (26), after several iterations of Sections 3.6 and 3.7, we often observe in our simulation that no candidate satisfies Eq. (26) 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. (26), and there are many occasions at which a wrong candidate is chosen at Eq. (26) when 2τ ≥ d AG (C Γ ). On the other hand, when 2τ < d AG (C Γ ), the second criterion helps to determine the transmitted information earlier than the third.

Tightness of Upper Bounds (31) and (32)
In Table 4, we observe that the upper bounds (31) and (32) are much larger than the actual number of iterations for τ = 5. The disappearance of candidates satisfying Eq. (26) in the last paragraph may also explain the reason behind the large differences for τ = 5.

Klein
The code is C u with u = 20, dim C u = 18. There is no previously known algorithm that can handle this case. 5.6 Klein Quartic, (d AG (C Γ ), τ) = (10, 5) The code is C u with u = 13, dim C u = 11. According to Beelen and Brander (2010, Figure 1), we can use the original Guruswami-Sudan (Guruswami and Sudan, 1999) but it seems that its faster variants cannot be used. We need 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 F 8 . The proposed algorithm is much faster. 5.7 Klein Quartic, (d AG (C Γ ), τ) = (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. 5.8 Hermitian, (d AG (C Γ ), τ) = (6, 2) or (20,9) We can use the BMS algorithm (Sakata et al., 1995a,b) for this case. The complexity of Sakata et al. (1995a,b) is estimated as O(a 1 n 2 ) and a 1 n 2 = 24, 576. The complexity of the proposed algorithm seems comparable to Sakata et al. (1995a,b). However, we are not sure which one is faster.

5.9
Hermitian, (d AG (C Γ ), τ) = (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 (Andersen and Geil, 2008) 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.

5.10
Hermitian, (d AG (C Γ ), τ) = (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 Beelen and Brander (2010). Beelen and Brander (2010, Example 4) estimates the complexity of their algorithm as O(λ 5 n 2 (log λn) 2 log(log λn)), where λ 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 λ 5 n 2 = 2, 202, 927, 104. The proposed algorithm needs much fewer number of multiplications and divisions in F 16 .

5.12
Garcia-Stichtenoth (Example 2), (d AG (C Γ ), τ) = (6, 2), (10, 4), or (20,9) We can use Beelen (2007); Beelen and Høholdt (2008); Duursma et al. (2011); Duursma and Park (2010); Matsumoto and Miura (2000c) 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 Beelen (2007) 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 (Guruswami and Sudan, 1999) can correct no error in this set of parameters. There seems no previously known algorithm that can handle this case.
5.14 Garcia-Stichtenoth (Example 2), (d AG (C Γ ), τ) = (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 (Guruswami and Sudan, 1999) can correct 2 errors in this set of parameters. There seems no previously known algorithm that can handle this case.

Conclusion
In this paper, we modified the unique decoding algorithm for plane AG codes in Lee et al. (2012) 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 (Lee et al., 2012) and our modified algorithms are also expressed in terms of the minimum distance lower bound in Andersen and Geil (2008). 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 theoretically the same as the BMS algorithm (Sakata et al., 1995a,b) for one-point Hermitian codes. It is also much faster than the standard list decoding algorithms (Beelen and Brander, 2010;Guruswami and Sudan, 1999) for many cases that are examined and reported in our computational experiments in which examined error-correcting codes have midium sizes. It should be noted that as a list decoding algorithm the proposed method seems to have exponential worstcase computational complexity while the previous proposals (Beelen and Brander, 2010;Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposal for very large/special inputs.
The original decoding algorithm (Lee et al., 2012) allows parallel implementation on circuits like the Kötter architecture (Kötter, 1998). 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.
the Villum Foundation through their VELUX Visiting Professor Programme 2011-