Unique Decoding of General AG Codes

A unique decoding algorithm for general AG codes, namely multipoint evaluation codes on algebraic curves, is presented. It is a natural generalization of the previous decoding algorithm which was only for one-point AG codes. As such, it retains the same advantages of fast speed and regular structure with the previous algorithm. Compared with other known decoding algorithms for general AG codes, it is much simpler in its description and implementation.


I. INTRODUCTION
Goppa [1] was the first to define linear error-correcting codes on algebraic curves. For a divisor G whose support is disjoint from a set of rational points on the curve, divisor D being the sum of those rational points, he defined the evaluation code C L (D, G) and the differential code C Ω (D, G), the latter being the dual of the former. In the subsequent vast research works on Goppa's codes, now called AG codes, the focus was often on the dual of the evaluation code, that is, the differential code. The reason seems to be nothing else but the first successful decoding algorithm for AG code [2] was for the dual of the evaluation codes. Thus a lot of effort was put into finding curves with many rational points and thereon to construct differential codes with good parameters. To estimate the minimum distance of the codes, various lower bounds have been developed. For much the same reason, so-called onepoint codes that assume G = mQ for some positive integer m and a rational point Q are considered most often in the literature. These one-point differential codes can be decoded efficiently by the syndrome-based Berlekamp-Massey-Sakata algorithm with the Feng-Rao majority voting [3].
Guruswami and Sudan's list decoding [4] provided a fresh point of view that brought the evaluation codes back to the center. Using interpolation, they showed that evaluation codes can be decoded successfully beyond the capacity of the previous decoding algorithms for differential codes. Following this way of approaching the decoding problem of AG codes, the authors [5] reinterpreted Duursma's idea of the majority voting [6] in the context of the interpolation decoding, and introduced a unique decoding algorithm for one-point evaluation codes on Miura-Kamiya plane curves. The result was a combination of nice features of the interpolation-based list decoding and the performance of the classical syndrome decoding with the majority voting scheme. Shortly thereafter, Geil et al. [7] generalized the result for arbitrary one-point AG codes and for list decoding. The goal of this paper is to note that the basic idea of [5] is more widely applicable, and present an interpolation-based unique decoding algorithm for general evaluation AG codes. By general evaluation AG codes, we mean the evaluation codes C L (D, G) with an arbitrary divisor G, with the premise that there exists a rational point Q not in the support of D. These codes are often called multipoint evaluation codes. Prominent examples would be the two-point codes on maximal curves such as Hermitian, Suzuki, and Klein curves.
We find that the impact of the interpolation-based list decoding has already made Beelen and Høholdt [8] to construct a unique decoding algorithm that is very similar to ours. Their algorithm also adopts an iterative method using majority voting to find the interpolation polynomial that gives the corrected codeword. The major difference of our algorithm is that we do not need differentials to construct the algorithm and use Lagrange interpolation instead of syndromes computed from the received vector, and thus directly compute the coefficients, corresponding to the sent message, by majority voting. Thus our algorithm is much simpler to present and more streamlined to implement and deploy in practice. Fujisawa and Sakata [9] also presented a fast decoding algorithm for multipoint general AG codes using a variant of the classical Berlekamp-Massey-Sakata algorithm, but only to correct errors short of the Goppa bound. Their method, originally due to Drake and Matthews [10], is to embed the multipoint code isometrically into a onepoint code.
The core ideas of the present work that we add to [5] are all contained in the preliminary materials in Section II. For general facts and notations for algebraic curves and functions fields, we refer to [11]. Once the stage set, we describe in Section III the decoding algorithm in a parallel fashion to [5]. In Section IV, several examples and experimental results are provided. In the final Section, we conclude with some remarks.

II. PRELIMINARIES
Let X be a smooth geometrically irreducible projective curve defined over a finite field F. Let P 1 , P 2 , . . . , P n and Q be distinct rational points on X, and define D = P 1 + P 2 + · · · + P n . Let G be an arbitrary divisor on X, whose support is disjoint from that of D, but allowed to include Q.
Let F(X) be the function field of X over F. Let be the ring of all functions on X which have no poles other than Q. For f ∈ R, let ρ(f ) = −v Q (f ). The Weierstrass semigroup at Q is then It is well-known that Λ is a numerical semigroup whose number of gaps is the genus g of X. Let γ be the smallest positive integer in Λ, and let ρ(x) = γ with some x ∈ R. For each 0 ≤ i < γ, let a i be the smallest integer such that a i ≡ i (mod γ) and ρ(y i ) = a i for some y i ∈ R. Then, using the properties of ρ : R → Z ≥0 inherited from the valuation v Q , we can show that {y 0 , y 1 , . . . , y γ−1 } forms a basis of R as a free module of rank γ over F[x]. Hence {x k y i | k ≥ 0, 0 ≤ i < γ} is a vector space basis of R over F, and will be called the monomials of R. The set {a i | 0 ≤ i < γ} is usually referred to as the Apéry set of Λ. Now letR which is clearly a module over R. For f ∈R, let δ(f ) denote the smallest integer s such that f ∈ L(sQ + G). Note that simply . Thus the map δ :R → Z satisfies the following properties: Then Λ +Λ =Λ, and henceΛ contains all large enough integers. Therefore for each 0 ≤ i < γ, there exists the smallest integer b i such that b i ≡ i (mod γ) and δ(ȳ i ) = b i for someȳ i ∈R. Then using the properties of δ, we easily see that {ȳ i | 0 ≤ i < γ} forms a basis ofR as a free module of rank γ over F [x]. For s ∈Λ, if i = s mod γ and k = ( is a basis of R over F, and will be called the monomials ofR.
Let us consider the R-module where z is a variable. Note that it is also a free F[x]-module of rank 2γ with free basis Thus every element in Rz ⊕R can be written as a unique F-linear combination of the monomials in For the monomials, we will use the notations We now briefly review the Gröbner basis theory on Rz ⊕R, regarded as a free module of rank 2γ over F[x]. First we define monomial order > s . For an integer s, the weighted degree of a polynomial f z + g ∈ Rz ⊕R is defined as δ s (f z + g) = max{ρ(f ) + s, δ(g)}.
In particular, for monomials, we have For more discussion on Proposition 1 and on the general theory of Gröbner bases, we refer to [12].
The evaluation map ev :R → F n , ϕ → (ϕ(P 1 ), ϕ(P 2 ), . . . , ϕ(P n )) is linear over F. Thus the AG code is a linear code of length n over F. Let us assume |G| < n so that the functions in L(G) correspond one-to-one with the codewords in C under ev. Note that {ϕ s | s ∈Λ, s ≤ 0} is a basis of L(G) as a vector space over F. Hence the dimension of C is k = |{s ∈Λ | s ≤ 0}|. So {s ∈ Λ | s ≤ 0} = {s 0 , s 1 , . . . , s k−1 }. We will also assume the nonsystematic encoding by evaluation. Thus a message ω = (ω s0 , ω s1 , . . . , Note that the map ev is surjective onto F n . Indeed by the Riemann-Roch theorem, we see that ev(L(sQ + G)) = F n for s ≥ n − |G| + 2g − 1. Let h i ∈R be such that ev(h i ) is the ith element of the standard basis of F n . Let J be the kernel of ev. Note that J is a submodule ofR over R, and also over such that degȳ(lt(η i )) = i.
Proof: The first equality is a standard result of the Gröbner basis theory. To see the second equality, note that for all large enough s, The goal of a decoding algorithm is to recover µ, and also c if necessary, from v. We consider the interpolation module Using the Gröbner basis theory, we will extract µ from I v . Let Hence by the criterion in Proposition 1, the set is a Gröbner basis of I v with respect to > δ(hv) . The ideal of the error vector e is also a submodule of R over F[x], and has a Gröbner basis {ǫ i | 0 ≤ i < γ} with respect to > s such that deg y (lt(ǫ i )) = i. We prove the following by the same argument as before.

III. DECODING ALGORITHM
Notice that this section is adapted from the corresponding section in [5] for the present general setup, with some changes in notations. Some minor errors are also corrected.

A. Theory
The basic idea of our decoding algorithm is to iteratively compute the coefficients ω s of the function µ. For and for s ∈Λ, , for which we suppress the necessary superscript (s) for legibility.
Now let w be an element of F. For each 0 ≤ i < γ, let where the parentheses denote substitution of the variable z. The automorphism of the module Rz ⊕R induced by the substitution z → z +wϕ s preserves leading terms with respect to > s . Therefore the setB with respect to > s . However, with respect to > s−1 ,B may not be a Gröbner basis ofĨ. The following procedure modifieŝ B to obtain a Gröbner basis ofĨ with respect to > s−1 .
For each 0 ≤ i < γ, there are unique integers 0 ≤ i ′ < γ and k i satisfying such that ρ(a i,i y i ) + s ∈Λ if and only if k i ≥ 0. Let and where the bracket notation f [x k ] refers to the coefficient of the term x k in f . Observe that i ′ = (i + s) mod γ, and hence the map i → i ′ is a permutation of {0, 1, . . . , γ − 1} and that the integer c i is defined such that and if w i = w and c i > 0, let and if w i = w and c i ≤ 0, let where ν Proof: Let 0 ≤ i < γ. We consider the pair By the assumption that B (s) is a Gröbner basis of I v (s) with respect to > s , we have for 0 ≤ j < γ, Similarly we have for 0 ≤ j < γ with j = i, where the inequality is strict if and only if w = w i by the definition of w i in (4).
Now we consider the setB with respect to > s−1 . For the case that w i = w, by (6), In the case that w i = w and c i > 0, we have (7). Observe that and by (9) and (5), This implies that there is a canceling of the leading coefficients in (7). Therefore, together with (9), we have For the case that w i = w and c i ≤ 0, we have (8). By almost the same argument as above, we can show that Finally it is clear thatB still generates the moduleĨ. From (10), (11), and (12), we see thatB is a Gröbner basis ofĨ with respect to > s−1 , by the criterion in Proposition 1. For the following, it is important to keep in mind that the values w i , c i are determined only by B (s) and independent of w althoughB is clearly dependent on w.
Proof: Lemmas 9 and 10 imply where we used the equality shown by Lemma 4 and Proposition 2, and the equality shown by Proposition 3. Let for s ∈Λ, s ≤ 0. Then define Proof: Just note that ρ(ǫ i ) − ρ(y i ) ≥ 0 for 0 ≤ i < γ.
Proof: Note that To show the last equality, pick any f inR. Then for all large enough s.
a) Initialization: Let N = δ(h v ), and let B (N ) be the Gröbner basis of I v with respect to > N , Let w s = 0 for s with N < s ≤ 0, s ∈Λ. The following steps Pairing, Voting, and Rebasing are iterated for s decreasing from N to c) Voting: If s > 0 or s / ∈Λ, then for i with k i ≥ 0, let and for i with k i < 0, let w i = 0, µ i = 1. Let w = 0 in both cases. If s ≤ 0 and s ∈Λ, then for each i, let and letc i = max{c i , 0}, and let w be the element of F with the largest w=wic i , and let w s = w. d) Rebasing: For each i, do the following. If w i = w, then let g and let ν and let ν and let ν e) Output: After the iterations, output the recovered message (w s0 , w s1 , . . . , w s k−1 ).
We now give an overview of the algorithm. Note that the decoding algorithm is in one of two phases while s decreases from N to s 0 . The first phase is when s > 0 or s / ∈Λ, and the second phase is when s ≤ 0, s ∈Λ. In the first phase, the Gröbner basis In the second phase, the algorithm determines w s by majority voting and updates B (s) such that B (s−1) is a Gröbner basis of When the algorithm terminates, w s are determined for all s ∈ Λ, s ≤ 0.

Proposition 14.
For N ≥ s ≥ s 0 , the set B (s) is a Gröbner basis of I v (s) with respect to > s .
Proof: This is proved by induction on s. For s = N , this is true by (1). Now our induction assumption is that this is true for s. In the second phase, we already saw in Proposition 7 that B (s−1) is a Gröbner basis of I v (s−1) . So it remains to consider the first phase. The proof for this case is similar to that of Proposition 7. Suppose By the induction assumption, we have for 0 ≤ j < γ, Similarly, by the induction assumption, we have for 0 ≤ j < γ with j = i, δ s (a i,i y i z) > δ s (a i,j y j z) and for 0 ≤ j < γ with where the inequality is strict except when ρ(a i,i y i )+s ∈Λ and . Now in the case when w i = 0, by (14) and (17), In the case when w i = 0 and c i > 0, by (15), Observe that and by the equality in (17), Finally in the case when w i = 0 and c i ≤ 0, by (16), Then we can show that lt s−1 (f

C. Complexity
Recall that the main data with which the decoding algorithm works is essentially 2γ × 2γ array of polynomials in F[x] that represents B (s) . Each of the 2γ rows of the array are again viewed as pairs of vectors in F[x] γ . To optimize the speed complexity of the algorithm, it is necessary to precompute and store required information as vectors in F[x] γ before the error correction processing for the received vector v begins.
For the Initialization step, we precompute h i for 1 ≤ i ≤ n and η i for 0 ≤ i < γ in the vector form. Then for given v, h v is computed just as an F-linear combination of the vectors. Thus the setup of the initial Gröbner basis B (N ) is straightforward.
In the Rebasing step, the most intensive computation is the substitution of z with z + wϕ s . As ϕ s is in the form x kȳ i , the computation is facilitated if y iȳj for 0 ≤ i, j < γ is precomputed in the vector form. The necessity of the precomputation of y iȳj was first noted in [13] for the case of general one-point codes.
If the output of the algorithm at the Output step should be the corrected codeword, say, under systematic encoding, then precomputation of the vectors ev(ϕ si ) in F n for 0 ≤ i ≤ k − 1, essentially the generator matrix of the code C, would be necessary.

Proposition 16. Lagrange basis polynomial h i can be chosen such that the maximum degree of the polynomials in the vector form of h i is bounded by
Proof: By the Riemann-Roch, we can choose h i in

Proposition 17. The maximum degree of the polynomials in the vector form of η i is bounded by
Proof: Since dim FR /J = n, there can be no more than n monomials preceding lm(η i ), which implies δ(η i ) ≤ s n . Recall that Λ + s 0 ⊂Λ. Therefore s n ≤ s 0 + n + g. Suppose Since δ(ȳ j ) ≥ s 0 , we have deg(η ij ) ≤ (n + g)/γ.

Proposition 18.
The maximum degree of the polynomials in the 2γ × 2γ array during an execution is bounded by If g = 0, then it is bounded by n.
Proof: First observe that the behavior of the algorithm is such that the maximum of δ(f ) for f ∈ B (s) is monotonically decreasing through the iterations. So it suffices to consider δ(η i ) and δ(y i h v ) in the initial basis B (N ) . Since δ(h i ) ≤ n − |G| + 2g − 1 and ρ(y i ) = a i ≤ 2g + γ − 1 by the definition of a i , we have On the other hand, δ(η i ) ≤ s 0 + n + g. Hence during the execution, we have for f ∈ B (s) , δ(f ) = max{γ + n − |G| + 4g − 2, s 0 + n + g}, from which we deduce that the maximum degree of the polynomials in the array is bounded by max{1 + (n + 4g − 2)/γ, (n + g)/γ}, where the former is larger if g > 0. If g = 0, the latter is larger, and is n.

Proposition 19. The number of iterations is at most
Proposition 20. If g > 0, an execution of the decoding algorithm takes O((n + 4g)(n + 2g)g) multiplications. For g = 0, it takes O(n 2 ) multiplications. The implicit constant is absolute.
Proof: For the first phase iteration, the update for each pair of the upper and lower rows of the array takes O(n + 4g + γ) multiplications. Hence for the whole array, it takes O((n + 4g + γ)γ). For the second phase iteration, note that the maximum degree of the polynomials in the vector form of y iȳj is (4g + 2γ − 2)/γ. Hence the substitution operation for each row takes O((n + 4g)(2g + γ)/γ). For the whole array, it is O((n + 4g)(2g + γ)).
If g > 0, then γ ≤ g, so an iteration in either of first phase and second phase takes O((n + 4g)g) multiplications. Thus for N iter number of iterations, it takes O((n + 4g)(n + 2g)g) multiplications. On the other hand, γ = 1 for g = 0.
Finally the dominant part of the computation of the initial basis B (N ) is the computation of h v , which takes O(n(n + 2g)) multiplications.

IV. EXAMPLES
In this section, we give some explicit examples illustrating our decoding algorithm. We implemented the algorithm in Magma [14]. In particular, for the computation of y i andȳ i , Heß' algorithm [15] is heavily used as implemented in Magma. For the computation of η i , we used a custom FGLM algorithm [16].
Then the AG code C = C L (D, G) is a [26, 15,9] linear code over F 9 .

C. Two-Point Code on a Suzuki Curve
Let us consider the Suzuki curve over F 8 . The genus of the curve is g = 14. This curve has 65 rational points including one cusp at infinity. Let G = 15O + 24Q where O is the origin and Q is the unique place at the cusp. Let D be the sum of other 63 rational points.
Then the code C L (D, G) is a [63, 26, ≥ 25] linear code over F 8 with the best known minimum distance for codes of length 63 and dimension 26 over F 8 [17]. We have d LO = 25.
Recall that n = 63, g = 14, and γ = 8. The maximum degree of the polynomials in the vector forms of h i is 7 (N h = 11). The maximum degree of the polynomials in the vector forms of η i is 8 (N η = 9). In an experiment with 10 5 instances of decoding random errors of weight 12, the decoder performed at most 82 (N iter = 91) iterations with an 16 × 16 matrix of univariate polynomials at most 13 (N deg = 16) degree over F 8 . It took 0.0397 second to decode one instance on Macbook Pro, taking O(151606) multiplications according to Proposition 20.

D. Two-Point Reed-Solomon Code
The projective line over F 64 is a curve with genus 0 whose function field is the rational function field F 64 (x). It has 65 Note that n = 63, g = 0 and γ = 1. The maximum degree of the polynomials in the vector forms of h i is 62 = N h . The degree of the polynomial in the vector form of η 0 is 63 = N η . In an experiment with 10 5 instances of decoding random errors of weight 12, the decoder performed at most 63 = N iter iterations with 2 × 2 matrix of univariate polynomials at most 63 = N deg degree over F 64 . It took 0.0039 second to decode one instance, taking O(3969) multiplications.

V. REMARKS
We presented a unique decoding algorithm that can decode errors up to half of the bound d LO . Beelen and Høholdt's algorithm in [8] is similar in approach to ours, and can decode up to half of their generalized order bound. Thus we can speculate that d LO is related with the generalized order bound. Indeed it was shown in [7] that the bound d LO as defined in [5] coincides with the so-called Andersen-Geil bound d AG [18]. The relationship between these bounds may be treated in a separate place.
Geil and et al. [7] also showed that by a slight modification, the algorithm in [5] can be turned to a list decoding algorithm. The same can be done with the present general algorithm, but we leave out the details.