arXiv:1203.6127v5 [cs.IT] 22 Apr 2013

List Decoding Algorithm based on Voting in
Gröbner Bases for General One-Point AG
Codes
Ryutaroh Matsumoto∗, Diego Ruano†, and Olav Geil†
April 22, 2013
Abstract
We generalize the unique decoding algorithm for one-point AG codes
over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amorós, andO’Sullivan [31] 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, proveequality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil [3] that has not been done in theoriginal 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 ismuch faster than the algorithm by Beelen and Brander [5].
Keywords: algebraic geometry code, Gröbner basis, list decoding
MSC 2010: Primary: 94B35; Secondary: 13P10, 94B27, 14G50

1 Introduction
We consider the list decoding of one-point algebraic geometry (AG) codes. Guruswami and Sudan [24] proposed the well-known list decoding algorithm for∗

Department of Communications and Computer Enginnering, Tokyo Instiutte of Technology,
152-8550 Japan.
†
Department of Mathematical Sciences, Aalborg University, Denmark.

1

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 [5, Figure 1].
By modifying the unique decoding algorithm [31] 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 [24] and whose computational complexity is smaller than [5, 24] in many cases. A decoding algorithm
for primal one-point AG codes was proposed in [32], which was a straightforward
adaptation of the original Feng-Rao majority voting for the dual AG codes [16] tothe primal ones. The Feng-Rao majority voting in [32] for one-point primal codes
was generalized to multi-point primal codes in [6, Section 2.5]. The one-point
primal codes can also be decoded as multi-point dual codes with majority voting[4, 12, 13], whose faster version was proposed in [44] for the multi-point Hermitian codes. Lee, Bras-Amorós, and O’Sullivan [31] proposed another uniquedecoding (not list decoding) algorithm for primal codes based on the majority
voting inside Gröbner bases. The module used by them [31] is a curve theoretic
generalization of one used for Reed-Solomon codes in [2] that is a special caseof the module used in [29]. An interesting feature in [31] is that it did not use
differentials and residues on curves for its majority voting, while they were usedin [6, 32]. The above studies [6, 31, 32] dealt with the primal codes. We recently
proved in [23] that the error-correcting capabilities of [31, 32] are the same. The
earlier papers [10, 39] suggest that central observations in [3, 23, 32] were known
to the Dutch group, which is actually the case [11]. Chen [8], Elbrønd Jensen et al.
[15] and Bras-Amorós and O’Sullivan [7] studied the error-correcting capabilityof the Feng-Rao [16] or the BMS algorithm [45, 46] 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 [31], 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 [17]. We shall (1) prove that the error-correcting capability of theoriginal proposal is always equal to half of the bound in [3] for the minimum distance of one-point primal codes (Proposition 6), (2) generalize their algorithm towork 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
2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 [9], and we verified that the proposed algorithm can correct more errors
than [5, 24] with manageable computational complexity.
This paper is organized as follows: Section 2 introduces notations and relevantfacts. Section 3 improves [31] in various ways, and the differences to the original[31] are summarized in Section 3.8. Section 4 shows that the proposed modification to [31] works as claimed. Section 5 compares its computational complexity
with the conventional methods. Section 6 concludes the paper. Part of this paper was presented at 2012 IEEE International Symposium on Information Theory,
Cambridge, MA, USA, July 2012 [22].

2 Notation and Preliminary
Our study heavily relies on the standard form of algebraic curves introduced independently by Geil and Pellikaan [20] and Miura [38], which is an enhancementof earlier results [37, 41]. Let F/Fq be an algebraic function field of one variable
over a finite field Fq with q elements. Let g be the genus of F. Fix n + 1 distinct
places Q, P1 , . . . , Pn of degree one in F and a nonnegative integer u. We consider
the following one-point algebraic geometry (AG) code
Cu = {ev( f ) | f ∈ L(uQ)}(1)

where ev( f ) = ( f (P1 ), . . . , f (Pn )). Suppose that the Weierstrass semigroup H(Q)at Q is generated by a1 , . . . , at , and choose t elements x1 , . . . , xt in F whose poledivisors are (xi )∞ = ai Q for i = 1, . . . , t. We do not assume that a1 is the smallest
among a1 , . . . , at . Without loss of generality we may assume the availability ofsuch x1 , . . . , xt , because otherwise we cannot find a basis of Cu for every u. Then
we have that L(∞Q) = ∪∞i=1 L(iQ) is equal to Fq [x1 , . . . , xt ] [41]. We express
L(∞Q) as a residue class ring Fq [X1 , . . . , Xt ]/I of the polynomial ring Fq [X1 ,. . . , Xt ], where X1 , . . . , Xt are transcendental over Fq , and I is the kernel of thecanonical homomorphism sending Xi to xi . Geil and Pellikaan [20], Miura [38]identified the following convenient representation of L(∞Q) by using Gröbner
basis theory [1]. The following review is borrowed from [34]. Hereafter, we
assume that the reader is familiar with the Gröbner basis theory in [1].
Let N0 be the set of nonnegative integers. For (m1 , . . . , mt ), (n1 , . . . , nt ) ∈ Nt0 ,we define the weighted reverse lexicographic monomial order ≻ such that (m1 ,. . . , mt ) ≻ (n1 , . . . , nt ) if a1 m1 + · · · + at mt > a1 n1 + · · · + at nt , or a1 m1 + · · · + at mt =3

a1 n1 + · · · + at nt , and m1 = n1 , m2 = n2 , . . . , mi−1 = ni−1 , mi < ni , for some1 ≤ i ≤ t. Note that a Gröbner basis of I with respect to ≻ can be computed by[41, Theorem 15], [47], [49, Theorem 4.1] or [51, Proposition 2.17], starting fromany affine defining equations of F/Fq .
Example 1 According to Høholdt and Pellikaan [25, Example 3.7],
u3 v + v3 + u = 0
is an affine defining equation for the Klein quartic over F8 . There exists a uniqueF8 -rational place Q such that (v)∞ = 3Q, (uv)∞ = 5Q, and (u2 v)∞ = 7Q. The
numbers 3, 5 and 7 is the minimal generating set of the Weierstrass semigroup at
Q. Choosing v as x1 , uv as x2 and u2 v as x3 , by [49, Theorem 4.1] we can see thatthe standard form of the Klein quartic is given by
X22 + X3 X1 , X3 X2 + X14 + X2 , X32 + X2 X13 + X3 ,which is the reduced Gröbner basis with respect to the monomial order ≻. We cansee that a1 = 3, a2 = 5, and a3 = 7.
Example 2 Consider the function field F9 (u1 , v2 , v3 ) with relations
v32 + v2 = u41 ,v33 + v3 = (v2 /u1 )4 .

(2)

This is the third function field in the asymptotically good tower introduced by
Garcia and Stichtenoth [19]. Substituting v2 with u1 u2 and v3 with u2 u3 in Eq. (2)we have affine defining equations
u21 u32 + u2 − u31 = 0,

u22 u33 + u3 − u32 = 0.

The function u1 has a unique pole Q in F9 (u1 , u2, u3 ) = F9 (u1 , v2 , v3 ). The minimal
generating set of the Weiestrass semigroup H(Q) at Q is 9, 12, 22, 28, 32 and 35[52, Example 4.11]. It has genus 22 and 77 F9 -rational points different from Q[19].
Define six functions x1 = u1 , x2 = u1 u2 , x3 = u21 u2 u3 , x4 = u31 u22 u23 , x5 =((u1 u2 )2 + 1)u2 u3 and x6 = ((u1 u2 )2 + 1)u22 u23 . We have (x1 )∞ = 9Q, (x2 )∞ =12Q, (x3 )∞ = 22Q, (x4 )∞ = 35Q, (x5 )∞ = 28Q and (x6 )∞ = 32Q [50]. From
this information and [49, Theorem 4.1] we can compute the 15 polynomials in
the reduced Gröbner basis of the ideal I ⊂ F9 [X1 , . . . , X6 ] defining L(∞Q) as{X23 −X14 +X2 , X5 X2 −X3 X12 , X6 X2 −X4 X1 , X32 −X4 X1 , X3 X22 −X5 X12 +X3 , X5 X3 −X6 X12 ,4X6 X3 − X16 + X5 X12 + X2 X12 , X52 − X4 X2 X1 − X6 , X4 X3 − X2 X15 + X3 X13 + X22 X1 ,X4 X22 − X6 X13 + X4 , X6 X5 − X22 X14 + X3 X2 X12 + X5 , X5 X4 − X17 + X5 X13 + X2 X13 ,X62 − X5 X14 + X4 X2 X1 + X3 X12 + X6 , X6 X4 − X3 X15 + X6 X13 + X3 X2 X1 , X42 − X3 X2 X14 +X4 X13 + X5 X12 − X3 }. Note that polynomials in the above Gröbner basis are in
the ascending order with respect to the monomial order ≺ while terms in eachpolynomial are in the descending order with respect to ≺.
For i = 0, . . . , a1 − 1, we define bi = min{m ∈ H(Q) | m ≡ i (mod a1 )},and Li to be the minimum element (m1 , . . . , mt ) ∈ Nt0 with respect to ≺ such thata1 m1 + · · · + at mt = bi . Note that bi ’s are the well-known Apéry set [40, Lemmas
2.4 and 2.6] of the numerical semigroup H(Q). Then we have ℓ1 = 0 if we write
Li as (ℓ1 , . . . , ℓt ). For each Li = (0, ℓi2 , . . . , ℓit ), define yi = xℓ2i2 · · · xℓt it ∈ L(∞Q).
The footprint of I, denoted by ∆(I), is {(m1 , . . . , mt ) ∈ Nt0 | X1m1 · · · Xtmt is
not the leading monomial of any nonzero polynomial in I with respect to ≺}, anddefine Ω0 = {xm1 1 · · · xmt t | (m1 , . . . , mt ) ∈ ∆(I)}. Then Ω0 is a basis of L(∞Q) as
an Fq -linear space [1], two distinct elements in Ω0 have different pole orders at Q,andΩ0 = {xm1 xℓ22 · · · , xℓt t | m ∈ N0 , (0, ℓ2, . . . , ℓt ) ∈ {L0 , . . . , La1 −1 }}= {xm1 yi | m ∈ N0 , i = 0, . . . , a1 − 1}.

(3)

Equation (3) shows that L(∞Q) is a free Fq [x1 ]-module with a basis {y0 , . . . ,ya1 −1 }. Note that the above structured shape of Ω0 reflects the well-known property of every weighted reverse lexicographic monomial order, see the paragraphpreceding to [14, Proposition 15.12].
Example 3 For the curve in Example 1, we have y0 = 1, y1 = x3 , y2 = x2 .
Let vQ be the unique valuation in F associated with the place Q. The semigroup H(Q) is equal to {ia1 − vQ (y j ) | 0 ≤ i, 0 ≤ j < a1 } [40, Lemma 2.6]. By [34,Proposition 3.18], for each nongap s ∈ H(Q) there is a unique monomial xi1 y j ∈ Ω0with 0 ≤ j < a1 such that −vQ (xi1 y j ) = s, and let us denote this monomial by ϕ s .
Let Γ ⊂ H(Q), and we may consider the one-point codesCΓ = h{ev(ϕ s ) | s ∈ Γ}i,(4)where h·i denotes the Fq -linear space spanned by ·. Since considering linearly
dependent rows in a generator matrix has no merit, we assumebΓ ⊆ H(Q),
5

(5)

b
where H(Q)= {u ∈ H(Q) | Cu , Cu−1 }. One motivation for considering thesecodes is that it was shown in [3] how to increase the dimension of the one-point
codes without decreasing the lower bound dAG for the minimum distance. The
bound dAG (CΓ ) is defined for CΓ as follows [3]: For s ∈ Γ, letbλ(s) = ♯{ j ∈ H(Q) | j + s ∈ H(Q)}.

(6)

Then dAG (CΓ ) = min{λ(s) | s ∈ Γ}. It is proved in [21] that dAG gives the same
estimate for the minimum distance as the Feng-Rao bound [16] for one-point dual
AG codes when both dAG 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 isalso proved in [21] that dAG (CΓ ) can be obtained from the bounds in [4, 12, 13],hence dAG can be understood as a particular case of these bounds [4, 12, 13].

3 Procedure of New List Decoding based on Votingin Gröbner Bases
3.1 Overall Structure
Suppose that we have a received word ~r ∈ Fnq . We shall modify the unique decoding algorithm proposed by Lee et al. [31] so that we can find all the codewords in
CΓ in Eq. (4) within the Hamming distance τ from ~r. The overall structure of themodified 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 [31]. Steps 1 and 3 are not given in [31]. Each stepis described in the following subsections in Section 3. We shall analyze timecomplexity except the precomputation part of the algorithm.

63.2 Modified Definitions for the Proposed Modification
We retain notations from Section 2. In this subsection, we modify notations anddefinitions in [31] to describe the proposed modification to their algorithm. We
also introduce several new notations. Define a set Ω1 = {xi1 y j zk | 0 ≤ i, 0 ≤ j < a1 ,k = 0, 1}. Our Ω1 is Ω in [31]. Recall also that Ω0 = {ϕ s | s ∈ H(Q)}.
Since the Fq [x1 ]-module L(∞Q)z ⊕ L(∞Q) has a free basis {y j z, y j | 0 ≤j < a1 }, 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′i′monomials xi11 y j zit+1 and x11 y j′ zit+1 , first rewrite y j and y j′ by x2 , . . . , xt defined in
′
i′ i′
i′
i′ ′
Section 2 and get xi11 y j zit+1 = xi11 xi22 · · · xitt zit+1 and x11 y j′ zit+1 = x11 x22 · · · xtt zit+1 . For a
i′ i′
i′ ′
nongap s ∈ H(Q), we define the monomial order xi11 xi22 · · · xitt zit+1 <s x11 x22 · · · xtt zit+1i′ i′i′parametrized by s if it+1 s − vQ (xi11 xi22 · · · xitt ) < i′t+1 s − vQ (x11 x22 · · · xtt ) or it+1 s −i′ i′i′vQ (xi11 xi22 · · · xitt ) = i′t+1 s − vQ (x11 x22 · · · xtt ) and i1 = i′1 , i2 = i′2 , . . . , iℓ−1 = i′ℓ−1 andiℓ > i′ℓ for some 1 ≤ ℓ ≤ t + 1. Observe that the restriction of <s to Ω0 is equalto ≺ 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 formodules, not for ideals.
For f ∈ L(∞Q)z ⊕ L(∞Q), γ( f ) denotes the number of nonzero terms in fwhen f is expressed as an Fq -linear combination of monomials in Ω1 . γ,1 ( f )denotes the number of nonzero terms whose coefficients are not 1 ∈ Fq .
For the code CΓ in Eq. (4), define the divisor D = P1 +· · ·+ Pn . Define L(−G +S∞Q) = ∞
i=1 L(−G +iQ) for a positive divisor G of F/Fq . Then L(−D +∞Q) is an
ideal of L(∞Q) [33]. Let ηi be any element in L(−D+∞Q) such that lm(ηi ) = x1j yi
with j being the minimal given i. Then by [31, Proposition 1], {η0 , . . . , ηa1 −1 } isa Gröbner basis for L(−D + ∞Q) with respect to <s as an Fq [x1 ]-module. For anonnegative integer s, define Γ(≤s) = {s′ ∈ Γ | s′ ≤ s}, Γ(>s) = {s′ ∈ Γ | s′ > s}, andprec(s) = max{s′ ∈ H(Q) | s′ < s}. We define prec(0) = −1.

3.3 Precompuation before Getting a Received Word
Before getting ~r, we need to compute the Pellikaan-Miura standard form of thealgebraic curve, y0 (= 1), y1 , . . . , ya1 −1 , and ϕ s for s ∈ H(Q) as defined in Section
2. Also compute η0 , . . . , ηa1 −1 , which can be done by [33].
For each (i, j), express yi y j as an Fq -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(yi y j ),7

which will be used in Eqs. (14) and (22).
b
Find elements ϕ s ∈ Ω0 with s ∈ H(Q).
There are n such elements, which wedenote by ψ1 , . . . ψn such that −vQ (ψi ) < −vQ (ψi+1 ). Compute the n × n matrix
−1 ψ1 (P1 ) · · · ψ1 (Pn ) 


..
..
..
M = 
 .
.
.
.


ψn (P1 ) · · · ψn (Pn )(7)

3.4 Multiplication and Division in an Affine Coordinate Ring
In both original unique decoding algorithm [31] 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 quotientg/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.
3.4.1 Multiplication in an Affine Coordinate Ring
The normal form of g, for g ∈ L(∞Q), is the expression of g written as an Fq 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 yi y j beaX
1 −1
yk fi, j,k (x1 ).
k=0with fi, j,k (x1 ) ∈ Fq [x1 ], which is computed in Section 3.3.
We denote by X1 , Y1 , . . . , Ya1 −1 algebraically independent variables over Fq .
1. Assume that g and h are in their normal forms. Change yi to Yi and x1 to X1
in g, h for i = 1, . . . , a1 − 1. Recall that y0 = 1. Denote the results by G, H.
2. Compute GH. This step needs
γ(g) × γ(h)multiplications in Fq .

8(8)

3. Let GH =P

0≤i, j<a1 Yi Y j FG,H,i, j (X1 ). Then we have

X

gh =

FG,H,i, j(x1 )0≤i, j<a1

aX
1 −1

yk fi, j,k (x1 ).

(9)

k=0

Pa1 −1Pa1 −1
Computation of FG,H,i, j(X1 ) k=0
yk fi, j,k (x1 ) needs at most γ,1 ( k=0
yk fi, j,k (x1 ))γ(FG,H,i, j(x1 )) multiplications in Fq . Therefore, the total number of multiplications in Fq in this step is at most
X

aX
1 −1

γ(FG,H,i, j(x1 ))γ,1 (

0≤i, j<a1

yk fi, j,k (x1 )).

(10)

k=0

Therefore, the total number of multiplications in Fq is at mostγ(g) × γ(h) +

X

aX
1 −1

γ(FG,H,i, j (x1 ))γ,1 (

0≤i, j<a1

yk fi, j,k (x1 )).

(11)

k=0

Define Eq. (11) as multi(g, h).
We emphasize that when the characteristic of Fq is 2 and all the coefficients ofdefining equations belong to F2 , which is almost always the case for those cases
Pa1 −1of interest for applications in coding theory, then γ,1 ( k=0
yk fi, j,k (x1 )) in Eq. (11)is zero. This means that L(∞Q) has little additional overhead over Fq [X] forcomputing products of their elements in terms of the number of Fq -multiplications
and divisions.
Remark 4 Define (i, j) to be equivalent to (i′ , j′ ) if yi y j = yi′ y j′ ∈ L(∞Q). Denoteby [i, j] the equivalence class represented by (i, j). For (i, j), (i′, j′) ∈ [i, j] we havefi, j,k (x1 ) = fi′ , j′ ,k (x1 ), which is denoted by f[i, j],k (x1 ). The right hand side of Eq. (9)can be written as a −1
1
X  X
 X

FG,H,i′ , j′ (x1 )yk f[i, j],k (x1 ).
(12)

[i, j](i′ , j′ )∈[i, j]

k=0

By using Eq. (12) instead of Eq. (9), we have another upper bound on the numberof multiplications as


aX
1 −1
X  Xyk f[i, j],k (x1 )).
(13)
FG,H,i′ , j′ (x1 ) γ,1 (γ(g) × γ(h) +γ [i, j](i′ , j′ )∈[i, j]

k=0

9Since Xγ 

(i′ , j′ )∈[i, j]
FG,H,i′, j′ (x1 ) ≤X

γ(FG,H,i′ , j′ (x1 )),(i′ , j′ )∈[i, j]

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.
3.4.2 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.
1. Initialize σ = 0. Also initialize ζ = 0.
2. Check if −vQ (g) ∈ −vQ (h) + H(Q). If not, declare that g does not belong to
the principal ideal of L(∞Q) generated by h, and finish the procedure.
3. Let ϕ s ∈ Ω0 such that −vQ (g) = −vQ (ϕ s h). Observe that lc(ϕ s lm(h)) =lc(ys mod a1 y−vQ (h) mod a1 ) and that lc(ys mod a1 y−vQ (h) mod a1 ) is precomputed as
Section 3.3. Let
Fq ∋ t = lc(g)/(lc(h) ×).
lc(ϕ s lm(h))| {z}Precomputed in Section 3.3(14)Computation of tϕ s needs one multiplication and one division in Fq . Observe that −vQ (g − tϕ s h) < −vQ (g).
4. Compute the normal form of tϕ s h, which requires at most multi(tϕ s , h) multiplications in Fq . Increment ζ by 2 + multi(tϕ s , h).
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 upperbound on the number of multiplications and divisions in Fq 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
[36].
10

3.5 Initialization after Getting a Received Word ~rP
Let (i1 , . . . , in )T = M~r, where M is defined in Eq. (7). Define h~r = nj=1 i j ψ j . Then
we have ev(h~r ) = ~r. The computation of h~r from ~r needs at most n2 multiplications
in Fq .
Let N = −vQ (h~r ). For i = 0, . . . , a1 − 1, compute g(N)= ηi ∈ L(∞Q) andi(N)fi = yi (z − h~r ) ∈ L(∞Q)z ⊕ L(∞Q). The computation of fi(N) needs at most
multi(yi , h~r ) multiplications in Fq . Therefore, the total number of multiplicationsin the initialization is at most
aX
1 −1
2
n +
multi(yi , h~r ).
(15)
i=0

Let s = N and execute the following steps.

3.6 Three Termination Criteria of the Iteration
After finishing the initialization step in Section 3.5, we iteratively compute fi(s)and g(s)i with N ≥ s ∈ H(Q) ∪ {−1} and w s with N ≥ s ∈ H(Q) from larger s tosmaller 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 fi(s)and g(s)i for N ≥ s ∈ H(Q) ∪ {−1}. We describe the first part in Section 3.6.
Let fmin = α0 + zα1 having the smallest −vQ (α1 ) among f0(s), . . . , fa(s)
. In
1 −1
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 [2, Theorem 12] for the case g = 0 to g > 0.
Ali and Kuijper [2, Theorem 12] proved that if the number δ of errors satisfies
2δ < dRS (C s ), where dRS (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 AliKuijper’s algorithm as −α0 /α1 . To one-point primal AG codes, dRS (C s ) can begeneralized as either dAG (C s ) or n − s − g. The former generalization dAG (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 [31]. The firstone was proposed in [22] 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 ∈ Fnq .
11

3.6.1 First Criterion for Judging Termination
If• s ∈ Γ,• dAG (CΓ(≤s) ) > 2τ, and• −vQ (α1 ) ≤ τ + gthen do the following:
1. Compute α0 /α1 ∈ F. This needs at mostquot(α0 , α1)(16)multiplications and divisions in Fq .
2. If α0 /α1 ∈ L(∞Q) and α0 /α1 can be written as a linear combination ofmonomials in {ϕ s′ ∈ s′ ∈ Γ(≤s) }, then do the following:(a) If dAG (CΓ ) > 2τ or −vQ (α1 ) ≤ τ then include the coefficients ofP−α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ into the list of transmitted information vectors, and avoid proceeding with the rest of the decoding procedure.
P(b) Otherwise compute ev(−α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ ). This needs at mostXnγ(−α0 /α1 +(17)
w s′ ϕ s′ )s′ ∈Γ(>s)

multiplications and divisions in Fq .
(c) If



X


wt ev(−α0 /α1 +ws′ ϕ s′ ) − ~r ≤ τ,s′ ∈Γ(>s)

Pthen include the coefficients of −α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ into the list oftransmitted information vectors, and avoid proceeding with s. Otherwise, continue the iterations unless s < n − g − 2τ.

12

3.6.2 Second Criterion for Judging Termination
If s = max{s′ ∈ Γ | s′ < n − 2τ − g}, then do the following:
1. If −vQ (α1 ) > τ + g then stop proceeding with iteration.
2. Otherwise compute α0 /α1 ∈ F. This needs at mostquot(α0 , α1)(18)multiplications and divisions in Fq .
3. If 2τ < dAG (CΓ ), α0 /α1 ∈ L(∞Q), and α0 /α1 can be written as a linear
combination of monomials in {ϕ s′ ∈ s′ ∈ Γ(≤s) } then declare the coefficientsPof −α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ as the only transmitted information and finish.
Otherwise declare “decoding failure” and finish.
4. If 2τ ≥ dAG (CΓ ), α0 /α1 ∈ L(∞Q) and α0 /α1 can be written as a linear
combination of monomials in {ϕ s′ ∈ s′ ∈ Γ(≤s) }, then do the following:P(a) If −vQ (α1 ) ≤ τ then include the coefficients of −α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′
into the list of transmitted information vectors, and avoid proceedingwith s.
P(b) Otherwise compute ev(−α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ ). This needs at mostXnγ(−α0 /α1 +(19)
w s′ ϕ s′ )s′ ∈Γ(>s)

multiplications and divisions in Fq .
(c) If



X


wt ev(−α0 /α1 +ws′ ϕ s′ ) − ~r ≤ τ,s′ ∈Γ(>s)

then include the coefficients of −α0 /α1 +transmitted information vectors.

Ps′ ∈Γ(>s) w s′ ϕ s′ into the list of

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

133.6.3 Third Criterion for Judging Termination
Just repeat the iteration until finding fi(s) at s = −1 for i = 0, . . . , a1 − 1. If 2τ <dAG (CΓ ) then declare the vector (ws : s ∈ Γ) as the only transmitted informationand finish.
If 2τ ≥ dAG (CΓ ) then do the following:
1. If α0 = 0 and −vQ (α1 ) ≤ τ then include the vector (ws : s ∈ Γ) into the listof transmitted information vectors. Finish the iteration.
2. If −vQ (α1 ) > τ + g then finish the iteration.
P
3. Otherwise compute ev( s∈Γ ws ϕ s ). This needs at mostXnγ( ws ϕ s )

(20)

s∈Γ

multiplications and divisions in Fq .
4. If



 X

wt ev( ws ϕ s ) − ~r  ≤ τ,s∈Γthen include the vector (ws : s ∈ Γ) into the list of transmitted information
vectors. Finish the iteration.

3.7 Iteration of Pairing, Voting, and Rebasing
The iteration of the original algorithm [31] consists of three steps, called pairing,
voting, and rebasing. We will make a small change to the original. Our modified
version is described below.
3.7.1 Pairing
Let
g(s)
i =

X

ci, j y j z +0≤ j<a1fi(s) =

X0≤ j<a1X

di, j y j , with ci, j , di, j ∈ Fq [x1 ],0≤ j<a1

ai, j y j z +Xbi, j y j , with ai, j , bi, j ∈ Fq [x1 ],0≤ j<a114and let ν(s)= lc(di,i ). We assume that lt( fi(s) ) = ai,i yi z and lt(g(s)
ii ) = di,i yi . For′
0 ≤ i < a1 , as in [31] there are unique integers 0 ≤ i < a1 and ki satisfying−vQ (ai,i yi ) + s = a1 ki − vQ (yi′ ).
Note that by the definition abovei′ = i + s mod a1 ,(21)

and the integer −vQ (ai,i yi ) + s is a nongap if and only if ki ≥ 0. Now let ci =degx1 (di′ ,i′ ) − ki . Note that the map i 7→ i′ is a permutation of {0, 1, . . . , a − 1} andthat the integer ci is defined such that a1 ci = −vQ (di′ ,i′ yi′ ) + vQ (ai,i yi ) − s.
3.7.2 Voting
For each i ∈ {0, . . . a1 − 1}, we set
bi,i′ [xk1i ]µi = lc(ai,i yi ϕ s ), ws,i = −, c̄i = max{ci , 0},
µi

(22)

where bi,i′ [xk1i ] denotes the coefficient of xki of the univariate polynomial bi,i′ ∈Fq [x1 ]. We remark that the leading coefficient µi must be considered after expressing ai,i yi ϕ s by monomials in Ω0 .
Observe that lc(yi ϕ s ) = lc(yi ys mod a1 ) and that lc(yi ys mod a1 ) 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
2a1
(23)
excluding negation from the number of multiplication.
Let
1 X
ν(s) =(24)
max{−vQ (ηi′ ) + vQ (yi ) − s, 0}.
a1 0≤i<a1

We consider two different candidates depending on whether s ∈ Γ or not:• If s ∈ H(Q) \ Γ, set
w = 0.
• If s ∈ Γ, let w be one of the element(s) in Fq with
X
X
c̄i ≥
c̄i − 2τ + ν(s).
w=ws,i(25)(26)

w,ws,iLet ws = w. If several w’s satisfy the condition above, repeat the rest of thealgorithm for each of them.
153.7.3 Rebasing
In all of the following cases, we need to compute the normal form of the productP 1 −1P 1 −1wϕ s × aj=0
ai, j y j , and the product wϕ s × aj=0
ci, j y j . For each i, the number ofmultiplications is≤ multi(wϕ s ,

aX
1 −1

ai, j y j ) + multi(wϕ s ,

j=0

aX
1 −1

ci, j y j ),

(27)

j=0

where multi(·, ·) is defined in Section 3.4.1.
• If ws,i = w, then let(prec(s))

gi′= g(s)i′ (z + wϕ s ),fi(prec(s)) = fi(s) (z + wϕ s )where the parentheses denote substitution of the variable z and let νi(prec(s))
=
′
ν(s)
.
The
numberofmultiplications
in
this
case
is
bounded
by
Eq.
(27).
i′
• If ws,i , w and ci > 0, then letgi(prec(s))= fi(s) (z + wϕ s ),′(prec(s))

fi(prec(s))

and let νi′µi (w − ws,i ) (s)gi′ (z + wϕ s )
ν(s)
′
i

= µi (w − ws,i ).

Computation of
product of= xc1i fi(s)(z + wϕ s ) −µi (w−ws,i )ν(s)i′needs one multiplication and one division. Theµi (w−ws,i )(s)and g(s)i′ (z + wϕ s ) needs γ(gi′ (z + wϕ s )) multiplications,
ν(s)
′
i

where γ is defined in Section 3.4.1. Thus, the number of multiplications anddivisions is≤ 2 + γ(g(s)(28)
i′ (z + wϕ s )) + Eq. (27).
• If ws,i , w and ci ≤ 0, then letgi(prec(s))= g(s)′i′ (z + wϕ s ),(prec(s))

fi= fi(s) (z + wϕ s ) −16µi (w − ws,i ) −ci (s)x1 gi′ (z + wϕ s )
ν(s)
′
i

(prec(s))

and let νi′= ν(s)i′ .

Computation of
product ofµi (w−ws,i )ν(s)i′needs one multiplication and one division. Theµi (w−ws,i )(s)and g(s)′ (z + wϕ s ) needs γ(gi′ (z + wϕ s )) multiplications,
i
ν(s)
i′

where γ is defined in Section 3.4.1. Thus, the number of multiplications anddivisions is ≤ Eq. (28).
After computing fi(prec(s)) and g(prec(s))
as above, update the program variable s toiprec(s) and go to the beginning of Section 3.6.

3.8 Difference to the Original Method
In this subsection, we review advantages of our modified algorithm over the original [31].
• Our version can handle any one-point primal AG codes, while the originalcan handle codes only coming from the Cab curves [37]. This generalizationis enabled only by replacing y j in [31] by y j defined in Section 2.
• Our version can find all the codeword within Hamming distance τ from thereceived word ~r, while the original is a unique decoding algorithm.
• Our version does not compute fi(s) , 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 [17], 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 [2, Theorem 12]
and do not exist in the original [31].
• The third termination criterion is essentially the same as the original [31],but examination of the Hamming distance between the decoded codewordand ~r is added when 2τ ≥ dAG (CΓ ).

17• The original [31] is suitable for parallel implementation on electric circuit
similar to the Kötter architecture [27]. Our modified version retains thisadvantage.

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.

4.1 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 ws , define ~r(N) = ~r and recursively define ~r(prec(s)) = ~r(s) − ev(ws ϕ s ). By
P
definition ~r(−1) = ~r − ev( s∈Γ ws ϕ s ).
The following lemma explains why the authors include “Gröbner bases” in thepaper title. The module I~r(N) was used in [5, 18, 28, 30, 35, 42, 43] but the use ofI~r(s) with s < N was new in [31].
Lemma 5 Fix s ∈ H(Q) ∪ {−1}. Let ~r(s) correspond to ws (s ∈ Γ) chosen by the
decoding algorithm. Define the Fq [x1 ]-submodule I~r(s) of L(∞Q)z ⊕ L(∞Q) by
I~r(s) = {α0 + α1 z | α0 , α1 ∈ L(∞Q), vPi (α0 + ri(s) α1 ) ≥ 1, 1 ≤ i ≤ n},(29)

where ~r(s) = (r1(s) , . . . , rn(s) ). Then { fi(s) , g(s)i | i = 0, . . . , a1 − 1} is a Gröbner basisof I~r(s) with respect to <s as an Fq [x1 ]-module.
Proof. This lemma is a generalization of [31, Proposition 11]. We can prove thislemma in exactly the same way as the proof of [31, Proposition 11] with replacingy j in [31] with y j and s − 1 in [31] by prec(s).
The following proposition shows that the original decoding algorithm [31] cancorrect errors up to half the bound dAG (CΓ ), which was not claimed in [31].
Proposition 6 Fix s ∈ Γ. Let λ(s) as defined in Eq. (6) and ν(s) as defined in Eq.
(24). Then ν(s) = λ(s).

18bProof. Let T i = { j ∈ H(Q) | j ≡ i (mod a1 ), j + s ∈ H(Q)},then we haveλ(s) = ♯T 0 + · · · + ♯T a1 −1 . Moreover, observe thatb
H(Q) \ H(Q)= {−vQ (ηi xk1 ) | i = 0, . . . , a1 − 1, k = 0, 1, . . .}.

Therefore, for s ∈ Γ we have
Ti =
=
=
=

b
{ j ∈ H(Q) | j ≡ i (mod a1 ), j + s ∈ H(Q)}b{ j ∈ H(Q) | j ≡ i (mod a1 ), j + s < H(Q) \ H(Q)}{ j ∈ H(Q) | j ≡ i (mod a1 ), j + s < {−vQ (ηi′ xk1 ) | k ≥ 0}}{−vQ (yi xm1 ) | s − vQ (yi xm1 ) < {−vQ (ηi′ xk1 ) | k ≥ 0}},where the third equality holds by Eq. (21). By the equalities above, we see()−vQ (ηi′ ) + vQ (yi ) − s♯T i = max 0,,−vQ (x1 )which proves the equality ν(s) = λ(s).
Lee et al. [31] showed that their original decoding algorithm can correct up
to ⌊(dLBAO (Cu ) − 1)/2⌋ errors, where dLBAO (Cu ) = min{ν(s) | s ∈ H(Q), s ≤ u}.
Proposition 6 implies that dLBAO (Cu ) is equivalent to dAG (Cu ) for every one-point
primal code Cu , and therefore [3, Theorem 8] implies [31, Proposition 12]. In
another recent paper [23] we proved that dAG and dLBAO are equal to the Feng-Rao
bound as defined in [6, 32] for Cu .

4.2 Lower Bound for the Number of Votes
In Section 4.2 we discuss the number of votes (26) which a candidate ws,i receives.
Since we study list decoding, we cannot assume the original transmitted codeword
nor the error vector as in [31]. Nevertheless, the original theorems in [31] allow
natural generalizations to the list decoding context.
Lemma 7 Fix s ∈ Γ. For s′ ∈ Γ(>s) , fix a sequence of ws′ chosen by the decoding
algorithm, and define ~r(s) corresponding to the chosen sequence of ws′ . Fix ω s ∈Fq . Let ~e = (e1 , . . . , en )T be a nonzero vector with the minimum Hamming weightin the coset ~r(s) − ev(ω s ϕ s ) + C s−1 , where C s−1 is as defined in Eq. (1). Define\J~e =L(−Pi + ∞Q)
ei ,0



X 

Pi  (by [33]).
= L ∞Q −
ei ,0

19

Let {ǫ0, . . . , ǫa1 −1 } be a Gröbner basis for J~e as an Fq [x1 ]-module with respect tok<s (for any integer s), such that lm(ǫ j ) = x1j y j .
Under the above notations, we have−vQ (ǫi ) + vQ (ai,i yi ) ≥ a1 c̄i ,min{−vQ (ǫi ) + s, −vQ (ηi′ )} ≥ −vQ (di′ ,i′ yi′ ),for i with ws,i , ω s , andmin{−vQ (ǫi ) + s, −vQ (ηi′ )} ≥ −vQ (di′ ,i′ yi′ ) − a1 c̄i ,for i with ws,i = ω s .
Proof. The proof is the same as those of [31, Propositions 7 and 8], with replacingy j in [31] by y j , δ(·) in [31] by −vQ (·).
The following lemma is a modification to [31, Proposition 9] for the list decoding.
Lemma 8 We retain notations from Lemma 7. We haveXXa1c̄i ≥ a1c̄i − 2a1 wt(~e)
ws,i =ω s+X

ws,i ,ω smax{−vQ (ηi′ ) + vQ (yi ) − s, −vQ (ǫi ) + vQ (yi )}.

0≤i<a1

Proof. Lemma 7 implies
XX−vQ (di′ ,i′ yi′ ) − min{−vQ (ǫi ) + s, −vQ (ηi′ )}a1 c̄i ≥ws,i =ω s

ws,i =ω s≥

X−vQ (di′ ,i′ yi′ ) − min{−vQ (ǫi ) + s, −vQ (ηi′ )}0≤i<a1andX

a1 c̄i ≤ws,i ,ω s

X−vQ (ǫi ) + vQ (ai,i yi )ws,i ,ω s≤

X−vQ (ǫi ) + vQ (ai,i yi ).

0≤i<a120

Now we have a chain of inequalities
XX
a1 c̄i −a1 c̄i
ws,i =ω s≥X

ws,i ,ω s−vQ (di′ ,i′ yi′ ) − min{−vQ (ǫi ) + s, −vQ (ηi′ )}0≤i<a1−X−vQ (ǫi ) + vQ (ai,i yi )0≤i<a1=X−vQ (di′ ,i′ yi′ ) − vQ (ai,i yi )0≤i<a1=− min{−vQ (ǫi ) + s, −vQ (ηi′ )} + vQ (ǫi )X−vQ (ηi′ ) − vQ (yi )0≤i<a1=+ max{+vQ (ǫi ) − s, +vQ (ηi′ )} + vQ (ǫi )X
max{−vQ (ηi′ ) + vQ (yi ) − s, −vQ (ǫi ) + vQ (yi )}0≤i<a1−X

2(−vQ (ǫi ) + vQ (yi ))0≤i<a1

where at Eq. (30) we used the equality
X
X
′
′
′
−vQ (di ,i yi ) +−vQ (ai,i yi )0≤i<a1=X

0≤i<a1

=

X

0≤i<a

X 1
−vQ (di,i yi ) +−vQ (ai,i yi )0≤i<a1(−vQ (di,i ) − vQ (ai,i )) +0≤i<a1= a1 n +
=

X

X

=

−2vQ (yi )0≤i<a1(−vQ (ηi ) + vQ (yi )) +−vQ (η ) +i′

0≤i<a1−2vQ (yi )0≤i<a10≤i<a1X

X

X

X−2vQ (yi )0≤i<a1−vQ (yi )0≤i<a1

shown in [31, Lemma 2 and Eq. (1)]. Finally note thatX
2(−vQ (ǫi ) + vQ (yi ))0≤i<a1

21

(30)

=

X

2a1 degx1 (ǫi ) = 2a1 wt(~e)

0≤i<a1by [31, Eq. (3)].
The following lemma is a modification to [31, Proposition 10] for list decoding, and provides a lower bound for the number of votes (26) received by any
candidate ω s ∈ Fq , as indicated in the section title.
Proposition 9 We retain notations from Lemma 7. Let ν(s) be as defined in Eq.
(24). We have
X
X
c̄i ≥
c̄i − 2wt(~e) + ν(s).
ws,i =ω s

ws,i ,ω s

Proof. We haveX

max{−vQ (ηi′ ) + vQ (yi ) − s, −vQ (ǫi ) + vQ (yi )}0≤i<a1≥X

max{−vQ (ηi′ ) + vQ (yi ) − s, 0}0≤i<a1as −vQ (ǫi ) + vQ (yi ) ≥ 0 for 0 ≤ i < a1 .

4.3 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 theeasiest to analyze, we start with the third one.
P
Fix a sequence ws for s ∈ Γ. If wt(~r − ev( s∈Γ ws ϕ s )) ≤ τ then the sequence
ws is found by the algorithm because of Proposition 9. When 2τ < dAG (CΓ ), by
Proposition 6 the decoding is not list decoding, and the algorithm just declares thesequence ws as the transmitted information.
On the other hand, if 2τ ≥ dAG (CΓ ), then the found sequence could correspondto 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 Fq ,the algorithm checks some sufficient conditions to decide the Hamming distance22

between the found codeword and the received word ~r. Let ~r(−1) = (r1(−1) , . . . , rn(−1) ).
When α0 = 0 in Section 3.6.3, by Lemma 5, we haveX
wt(~r − ev( ws ϕ s )) = wt(~r(−1) )
s∈Γ

≤

X

vPi (α1 )ri(−1) ,0≤ −vQ (α1 ),because Eq. (29) and α0 = 0 implies that vPi (α1 ) ≥ 1 for ri(−1) , 0. By theabove equation, −vQ (α1 ) ≤ τ implies that the found codeword is within Hamming
distance τ from ~r. This explains why the algorithm can avoid computation of theevaluation 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 conditionPof Step 2 in Section 3.6.3 implies that wt(~r − ev( s∈Γ ws ϕ s )) > τ. Suppose thatPwt(~r − ev( s∈Γ ws ϕ s )) ≤ τ. Then there exists β1 ∈ L(∞Q) such that vPi (β) ≥ 1 forri(−1) , 0, −vQ (β) ≤ τ + g, and β1 z ∈ I~r(−1) . Because the leading term of β1 z must be
divisible by lt( fi(−1) ) for some i by the property of Gröbner bases, we must have−vQ (α1 ) ≤ −vQ (β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 foundcodeword and ~r in Steps 3 and 4 in Section 3.6.3.

4.4 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 therequired codewords. For explanation, we present slightly rephrased version offacts in [6].
Lemma 10 [6, Lemma 2.3] Let β1 z + β0 ∈ I~r(s) with lt(β1 z + β0 ) = lt(β1 z) withrespect to <s and −vQ (β1 ) < n − τ − s. If there exists f ∈ L(sQ) such thatwt(ev( f ) − ~r(s) ) ≤ τ, then we have f = −β0 /β1 .
Proof. Observe that lt(β1 z + β0 ) = lt(β1 z) implies that −vQ (β0 ) ≤ −vQ (β1 ) + s <n−τ. The claim of Lemma 10 is equivalent to [6, Lemma 2.3] with A = (n−τ−1)Q
and G = sQ. Note that the assumption deg A > (n + deg G)/2 + g − 1 was not usedin [6, Lemma 2.3] but only in [6, Lemma 2.4].
Note
23

that the following proposition was essentially proved in [6, Proposition 2.10], [26,Section 14.2], and [48, Theorem 2.1] with b = 1.
Proposition 11 Let α0 and α1 be as in Section 3.6.2. If s < n − g − 2τ and there
exists f ∈ L(sQ) such that wt(ev( f ) − ~r(s) ) ≤ τ, then we have f = −α0 /α1 .
Proof. Let g ∈ L(∞Q) such that g(Pi ) = 0 if f (Pi ) , ri(s) , and assume that g has theminimum pole order at Q among such elements in L(∞Q). Then −vQ (g) ≤ τ + g.
One has that gz − f g ∈ I~r(s) and lt(gz − f g) = lt(gz) with respect to <s . By theproperty of Gröbner bases, lt(gz) is divisible by lt( fi(s) ) for some i, which implies−vQ (α1 ) ≤ −vQ (g) ≤ τ + g. By Lemma 10 we have f = −α0 /α1 .
We explain how the procedure in Section 3.6.2 works as desired. When thecondition 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) .
P
When 2τ < dAG (CΓ ), then the algorithm declares −α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ as
the unique codeword.
When 2τ ≥ dAG (CΓ ), then the algorithm examines the found codeword closeenough to ~r in Steps 4a and 4b in Section 3.6.2. When −vQ (α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 andexamine its Hamming distance to ~r(s) .
By Proposition 11, the codeword must be found at s = max{s′ ∈ Γ | s′ <n − 2τ + g}. Therefore, we do not execute the iteration at s < max{s′ ∈ Γ | s′ <n − 2τ + g}.

4.5 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 anothercodeword within Hamming distance τ from ~r(s) when the algorithm already foundone. So the algorithm can stop iteration with smaller s once a codeword is foundP
as ev(−α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ ).
The algorithm does not examine conditions when −vQ (α1 ) > τ + g by the same
reason as Sections 4.3 and 4.4. When 2τ < dAG (CΓ ), then the algorithm declaresP−α0 /α1 + s′ ∈Γ(>s) ws′ ϕ s′ as the unique codeword.
When 2τ ≥ dAG (CΓ ), then the algorithm examines the found codeword closeenough to ~r in Steps 2a–2c in Section 3.6.1. When −vQ (α1 ) ≤ τ we can avoid
24computation of the evaluation map ev by the same reason as Section 4.3, which ischecked at Step 2a.
By Proposition 11, the codeword must be found at some s ≥ max{s′ ∈ Γ | s′ <n − 2τ + g}. Therefore, we do not execute the iteration at s < max{s′ ∈ Γ | s′ <n − 2τ + g}.

4.6 Upper Bound on the Number of Iterations
Observe that for s > max Γ we set always ws 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 orone, because at most one w ∈ Fq can satisfy Eq. (26). Therefore, we have upperbounds for the number of iterations, counting executions of Rebasing in Section
3.7.3, as♯{s ∈ H(Q) | max Γ ≤ s < N} + expq (♯{s ∈ Γ | ν(s) ≤ 2τ})×♯{s ∈ H(Q) ∪ {−1} | s < max Γ}(31)

for the third criterion for judging termination, where expq (x) = q x , and♯{s ∈ H(Q) | max Γ ≤ s < N)} + expq (♯{s ∈ Γ | ν(s) ≤ 2τ})×♯{s ∈ H(Q) | max{s′ ∈ Γ | s′ < n − 2τ − g} ≤ s < max Γ}(32)bfor 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 Nbdepents on ~r and N ≤ max H(Q).
Observe that the list decoding can be implemented as expq (♯{s ∈ Γ | ν(s) ≤2τ}) parallel execution of the unique decoding. Therefore, when one can afford
expq (♯{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.

5 Comparison to Conventional Methods
5.1 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 ofcodewords with the one-point primal codes on Klein quartic over F8 with n = 2325

dAG (CΓ )# Errors
=τ

18

4

1

2

3

11

10

4

5

6

Termination
Criterion
in Sec. 3.6
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd

# Iterations
Eq.(31),(32)
11
11
26
328
328
1,160
28,68028,68073,736
17
17
26
47
47
103
3,087
3,087
5,647

Avg.
8.00
11.00
26.00
196.63200.64219.07
11,996.34
12,055.56
12,436.00
14.64
16.64
25.64
35.20
38.20
45.41
1,507.95
1,511.28
1,535.23

Max.
8
11
26
260
269
313
13,353
13,41913,853
15
17
26
44
47
72
1,692
1,695
1,725

# Multiplications& Divisions in Fq
Avg.
Max.
1,170.09
1,254
844.98879
976.32
1,018
26,203.96
77,2098,349.67
15,457
7,813.76
10,083
1,626,658.69 2,490,386
608,535.03
711,315
580,504.03
642,419
1,324.76
1,484
1,161.52
1,293
1,329.07
1,468
3,673.78
5,549
2,915.04
3,622
3,072.08
3,769
164,274.07
188,797
113,592.10
130,810
113,472.30
130,697# Codewords
Found
Avg. Max.
1.00
1

1.34

3

19.75

28

1.00

1

1.00

1

1.11

3

26

Table 1: Decoding results of codes on the Klein quartic (Fq = F8 , g = 3 andn = 23)♯ΓdAG (CΓ )# Errors
=τ

55

6

2R

2N

3R

3N

4R

4N

Termination
Criterion
in Sec. 3.6
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd

# Iterations
Eq.(31),(32)
22
22
70
22
22
70
2,829
2,829
14,6052,829
2,829
14,605
851,981
851,9813,735,565
851,981
851,9813,735,565

Avg.
16.38
21.79
69.79
16.22
21.22
69.22
796.17800.66846.78750.73761.79872.97
21,376.57
21,384.19
21,458.60
21,744.53
21,769.88
21,985.53

Max.
17
22
70
17
22
70
1,139
1,143
1,191
817
825
917
33,18733,19833,32732,94332,962
33,174# Multiplications& Divisions in Fq
Avg.
Max.
9,049.77
9,495
5,483.91
5,614
6,331.16
6,530
9,005.92
9,477
5,414.32
5,607
6,291.44
6,527
289,992.45
2,154,489
116,784.32
164,299
117,848.30
130,366
334,588.68
360,413
120,575.80
131,791
119,940.46
134,297
8,012,813.23 14,988,534
2,431,318.50
3,763,057
2,432,782.60
3,761,206
10,952,709.73 16,938,498
2,457,072.25
3,801,066
2,439,145.90
3,805,702# Codewords
Found
Avg. Max.
1.00
1

1.00

1

1.00

2

2.28

5

1.48

4

4.29

5

27

Table 2: Decoding results of the one-point Hermitian codes (Fq = F16 , g = 6,n = 64 and ♯Γ = 55). The meanings of N and R in the third column is explainedin Section 5.1.

♯ΓdAG (CΓ )# Errors
=τ

39

20

9R

9N

10R

10N

11R

11N

Termination
Criterion
in Sec. 3.6
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd

# Iterations
Eq.(31),(32)
36
36
70
36
36
70
143
143
655
143
143
655
36,89536,895
159,775
36,89536,895
159,775

Avg.
30.77
35.77
69.77
30.73
35.73
69.73
74.99
80.99
112.9977.64
89.61
153.73
12,112.08
12,118.08
12,148.10
10,417.34
10,429.34
10,491.11

Max.
31
36
70
32
36
70
93
99
131
126
138
244
12,85912,865
12,895
12,285
12,297
12,357# Multiplications& Divisions in Fq
Avg.
Max.
10,726.51
11,1758,851.66
9,249
10,781.91
11,5049,747.36
12,0087,807.55
8,378
9,607.34
10,64537,643.43
47,17922,792.85
25,97225,023.33
28,39846,759.83
177,947
23,971.51
43,332
28,063.19
36,453
7,480,228.09 7,911,646
3,186,977.77 3,352,388
3,189,262.07 3,354,588
6,123,703.49 7,582,687
2,638,130.92 3,226,308
2,641,014.19 3,230,078# Codewords
Found
Avg. Max.
1.00
1

1.00

1

1.00

1

2.00

2

1.00

1

2.01

6

28

Table 3: Decoding results of the one-point Hermitian codes (Fq = F16 , g = 6,n = 64 and ♯Γ = 39). The meanings of N and R in the third column is explainedin Section 5.1.

♯ΓdAG (CΓ )# Errors
=τ

58

6

2

3

52

10

4

5

37

20

9

10

11

Termination
Criterion
in Sec. 3.6
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd
1st
2nd
3rd

# Iterations
Eq.(31),(32)
60
60
89
2,862
2,862
5,049
64
64
89
196,866
196,866
347,769
73
73
89
1,915
1,915
3,049
2,077
2,077
3,049

Avg.
38.85
59.30
88.30
62.50
79.62
106.62
46.94
63.25
88.25
48.96
66.17
89.17
57.28
72.34
88.34
58.67
74.39
88.39
225.59242.36254.36

Max.
42
60
89
120
134
161
51
64
89
163
178
201
60
73
89
61
75
89
253
268
280

# Multiplications& Divisions in Fq
Avg.
Max.
39,473.98
62,47912,255.73
13,34813,710.71
14,88636,350.41
72,46321,754.75
30,03023,556.44
31,55537,228.61
78,09015,212.23
16,70817,082.34
18,87924,776.23
88,893
20,660.52
69,176
22,591.78
71,26424,998.86
48,611
23,168.98
24,78425,655.70
27,67525,492.43
43,29427,355.54
29,452
29,678.00
31,836167,152.76 191,250
124,664.66 139,519
126,693.96 141,989# Codewords
Found
Avg. Max.
1.00
1

1.00

1

1.00

1

1.00

1

1.00

1

1.00

1

1.00

1

29

Table 4: Decoding results of codes on the curve in Example 2 (Fq = F9 , g = 22
and n = 77). We note that Eq. (31) give the same value for τ = 10 and τ = 11.

♯Γby using Examples 1 and 3, the one-point Hermitian codes over F16 with n = 64,
and the one-point primal codes on the curve in Example 2 over F9 with n = 77.
The program is implemented on the Singular computer algebra system [9].
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 Rebasingin Section 3.7.3), the sum of upper bounds on the number of multiplications anddivisions given in Eqs. (15), (16), (17), (18), (19), (20), (23), (27) and (28), andthe number of codewords found. Note also that Eq. (11) instead of Eq. (13) isused.
The parameter τ is set to the same as the number of generated errors in eachsimulation 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 thetransmitted codeword or completely randomly, respectively. The distribution ofcodewords is uniform on CΓ . That of error vectors is uniform on the vectors ofHamming weight τ.
In the code construction, we always try to use the Feng-Rao improved conb
struction. 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 dAG (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 [24].

5.2 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 thesmallest 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 [22] 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 fi(s) 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 thenumber 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.
30

The second criterion is faster when 2τ < dAG (CΓ ), while the third tends tobe faster when 2τ ≥ dAG (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τ < dAG (CΓ )than with 2τ ≥ dAG (CΓ ). We speculate the reason behind them as follows: When2τ ≥ dAG (CΓ ) and a wrong candidate is chosen at Eq. (26), after several iterationsof 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, thesecond criterion does not help much to decrease the number of iterations nor thecomputational complexity when a wrong candidate is chosen at Eq. (26), andthere are many occasions at which a wrong candidate is chosen at Eq. (26) when2τ ≥ dAG (CΓ ). On the other hand, when 2τ < dAG (CΓ ), the second criterion helps
to determine the transmitted information earlier than the third.

5.3 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.
On the other hand, we observe that the upper bound (32) is quite tight for τ = 5
in Table 1 and τ = 10N in Table 3. This suggests that improvement of Eq. (32)
may need some additional assumption.

5.4 Klein Quartic, (dAG(CΓ ), τ) = (4, 1) or (10, 4)
We can use [4, 6, 12, 13, 32] to decode this set of parameters. It is essentiallythe forward elimination in the Gaussian elimination, and it takes roughly n3 /3
multiplications. In this case n3 /3 = 4, 055. The proposed algorithm has the lower
complexity than [4, 6, 12, 13, 32].

5.5 Klein Quartic, (dAG(CΓ ), τ) = (4, 2) or (4, 3)
The code is Cu with u = 20, dim Cu = 18. There is no previously known algorithm
that can handle this case.

31

5.6 Klein Quartic, (dAG(CΓ ), τ) = (10, 5)
The code is Cu with u = 13, dim Cu = 11. According to Beelen and Brander[5, Figure 1], we can use the original Guruswami-Sudan [24] but it seems thatits 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
6443 /3 = 89, 029, 994 multiplications in F8 . The proposed algorithm is much
faster.

5.7 Klein Quartic, (dAG(CΓ ), τ) = (10, 6)
The code is Cu with u = 13, dim Cu = 11. There is no previously known algorithm
that can handle this case.

5.8 Hermitian, (dAG(CΓ ), τ) = (6, 2) or (20, 9)
We can use the BMS algorithm [45, 46] for this case. The complexity of [45, 46]
is estimated as O(a1 n2 ) and a1 n2 = 24, 576. The complexity of the proposed
algorithm seems comparable to [45, 46]. However, we are not sure which one isfaster.

5.9 Hermitian, (dAG(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 Cu we have to set u = 60,
whose AG bound [3] 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, (dAG(CΓ ), τ) = (20, 10)
The code is Cu with u = 44. The required multiplicity is 11, and the required
designed list size is 14. The fastest algorithm for the interpolation step seems [5].
Beelen and Brander [5, Example 4] estimates the complexity of their algorithmas O(λ5 n2 (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 ofmultiplications and divisions is λ5 n2 = 2, 202, 927, 104. The proposed algorithm
needs much fewer number of multiplications and divisions in F16 .
32

5.11 Hermitian, (dAG(CΓ ), τ) = (20, 11)
The Guruwsami-Sudan algorithm [24] can correct up to 10 errors and there seems
no previously known algorithm that can handle this case.

5.12 Garcia-Stichtenoth (Example 2), (dAG(CΓ ), τ) = (6, 2), (10, 4),or (20, 9)
We can use [4, 6, 12, 13, 32] to decode this set of parameters. It is essentiallythe forward elimination in the Gaussian elimination, and it takes roughly n3 /3
multiplications. In this case n3 /3 = 152, 177. The proposed algorithm has thelower complexity than [4, 6, 12, 13, 32].

5.13 Garcia-Stichtenoth (Example 2), (dAG (CΓ), τ) = (6, 3)
This is a Feng-Rao improved code with dimension 58. In order to realize a codewith the same dimension, we have to set u = 79 in Cu . The Guruswami-Sudan
algorithm [24] can correct no error in this set of parameters. There seems nopreviously known algorithm that can handle this case.

5.14 Garcia-Stichtenoth (Example 2), (dAG (CΓ), τ) = (10, 5)This is a Feng-Rao improved code with dimension 52. In order to realize a codewith the same dimension, we have to set u = 73 in Cu . The Guruswami-Sudan
algorithm [24] can correct 2 errors in this set of parameters. There seems nopreviously known algorithm that can handle this case.

5.15 Garcia-Stichtenoth (Example 2), (dAG (CΓ), τ) = (20, 10)
This is an ordinary one-point AG code Cu with u = 58 and dimension 37. The
Guruswami-Sudan algorithm [24] can correct 10 errors with the multiplicity 154
and the designed list size 178. We have to solve a system of 77 × (154 + 1)154/2 =918, 995 linear equations. It takes 918, 9953/3 = 258, 712, 963, 551, 308, 291
multiplications in F9 . The proposed algorithm is much faster.

33

5.16 Garcia-Stichtenoth (Example 2), (dAG (CΓ), τ) = (20, 11)
The Guruswami-Sudan algorithm [24] can correct up to 10 errors and there seems
no previously known algorithm that can handle this case.

6 Conclusion
In this paper, we modified the unique decoding algorithm for plane AG codes in[31] so that it can support one-point AG codes on any curve, and so that it cando the list decoding. The error correction capability of the original [31] and ourmodified algorithms are also expressed in terms of the minimum distance lower
bound in [3].
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 [45, 46] for onepoint Hermitian codes, and much faster than the standard list decoding algorithms[5, 24] for several cases.
The original decoding algorithm [31] allows parallel implementation on circuits like the Kötter architecture [27]. 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
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 MTM200764704, and the Spanish MINECO grant No. MTM2012-36917-C03-03. The computer experiments in this research was conducted on Singular 3.1.3 [9].

34References[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.
[2] 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.
[3] 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.
[4] 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.
[5] P. Beelen and K. Brander. Efficient list decoding of a class of algebraic-geometrycodes. Adv. Math. Commun., 4(4):485–518, 2010. doi:10.3934/amc.2010.4.485.
[6] 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.
[7] M. Bras-Amorós and M. E. O’Sullivan. The correction capability of theBerlekamp-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.
[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.
[9] W. Decker, G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3-13 — A computer algebra system for polynomial computations, 2011. URL
http://www.singular.uni-kl.de.
[10] 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.
[11] I. M. Duursma. Coset bound / shift bound. private communication, Nov. 2012.
[12] 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.
[13] 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.
[14] D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1995.
[15] H. Elbrønd Jensen, R. R. Nielsen, and T. Høholdt. Performance analysis of a35

decoding algorithm for algebraic-geometry codes. IEEE Trans. Inform. Theory,45(5):1712–1717, July 1999. doi:10.1109/18.771253.
[16] 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.
[17] G. L. Feng and T. R. N. Rao. Improved geometric Goppa codes partI, basic theory. IEEE Trans. Inform. Theory, 41(6):1678–1693, Nov. 1995.
doi:10.1109/18.476241.
[18] 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.
[19] A. Garcia and H. Stichtenoth. A tower of Artin-Schreier extensions of function
fields, attaining the Drinfeld-Vladut bound. Invent. Math., 121(1):211–222, July
1995. doi:10.1007/BF01884295.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraicgeometry codes. IEEE Trans. Inform. Theory, 45(4):1757–1767, Sept. 1999.
doi:10.1109/18.782097.
[25] 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.
[26] 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.
[27] R. Kötter. A fast parallel implementation of a Berlekamp-Massey algorithm foralgebraic-goemetric codes. IEEE Trans. Inform. Theory, 44(4):1353–1368, July
1998. doi:10.1109/18.681314.
[28] 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.
[29] 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.

36

doi:10.1016/j.jsc.2008.01.002.
[30] 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.
[31] 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.
[32] R. Matsumoto and S. Miura. On the Feng-Rao bound for the L-construction ofalgebraic geometry codes. IEICE Trans. Fundamentals, E83-A(5):926–930, May
2000. URL http://www.rmatsumoto.org/repository/e83-a_5_923.pdf.
[33] 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.
[34] 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.
[35] 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.
[36] C. P. McKeague. Elementary Algebra. Brooks Cole, Florence, KY 41022-6904,
USA, 9th edition, 2012. ISBN 0840064217.
[37] 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 publishedas Trans. IEICE, vol. J75-A, no. 11, pp. 1735–1745, Nov. 1992).
[38] S. Miura. Linear codes on affine algebraic curves. Trans. IEICE, J81-A(10):1398–
1421, Oct. 1998.
[39] 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.
[40] 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.
[41] 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.
[42] S. Sakata. On fast interpolation method for Guruswami-Sudan list decoding of one-point algebraic-geometry codes. In S. Boztaş and I. E. Shparlin-

37

ski, 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.
[43] 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.
[44] 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.
[45] 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.
[46] 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.
[47] 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.
[48] 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.
[49] L.-Z. Tang. A Gröbner basis criterion for birational equivalence ofaffine varieties. J. Pure Appl. Algebra, 123(1-3):275–283, Jan. 1998.
doi:10.1016/S0022-4049(97)00139-4.
[50] D. Umehara and T. Uyematsu. One-point algebraic geometric codes from ArtinSchreier extensions of Hermitian function fields. IEICE Trans. Fundamentals, E81A(10):2025–2031, Oct. 1998.
[51] W. V. Vasconcelos. Computational Methods in Commutative Algebra and Algebraic
Geometry, volume 2 of Algorithms and Computation in Mathematics. SpringerVerlag, Berlin, 1998.
[52] C. Voss and T. Høholdt. An explicit construction of a sequence of codes attaining
the Tsfasman-Vlăduţ-Zink bound. IEEE Trans. Inform. Theory, 43(1):128–135, Jan.
1997. doi:10.1109/18.567659.

38