Generalized Sudan’s List Decoding for Order
Domain Codes
Olav Geil1 and Ryutaroh Matsumoto2
1

Department of Mathematical Sciences, Aalborg University, Denmark
olav@math.aau.dk
2
Department of Communications and Integrated Systems, Tokyo Institute ofTechnology, Japanryutaroh@rmatsumoto.org

Abstract. We generalize Sudan’s list decoding algorithm without multiplicity to evaluation codes coming from arbitrary order domains. The
number of correctable errors by the proposed method is larger than theoriginal list decoding without multiplicity.

1

Introduction

Høholdt et al. [6] proposed the new framework for algebraic code construction,
which they called evaluation codes. Evaluation codes are deﬁned by either generator matrices or parity check matrices. Evaluation codes deﬁned by parity
check matrices include many classes of algebraic codes, including generalized
Reed-Muller, Reed-Solomon, and one-point geometric Goppa codes CΩ (D, G),
and they provided lower bounds on the minimum Hamming distance and decoding algorithms in a uniﬁed manner, while relatively little work was done for
evaluation codes deﬁned by generator matrices in [6]. The framework of evaluation codes and order domains was later generalized by O’Sullivan [7], Geil and
Pellikaan [3].
Andersen and Geil [1] studied the evaluation codes deﬁned by generator matrices, which also include generalized Reed-Muller, Reed-Solomon, and one-point
geometric Goppa codes CL (D, G), and they also provided lower bounds on theminimum Hamming distance in a uniﬁed manner. Their work [1] can be regarded
as a generator matrix counterpart of [6]. In this paper we study evaluation codesdeﬁned by generator matrices.
On the other hand, Sudan [10] and Guruswami-Sudan [5] proposed the list
decoding algorithms for Reed-Solomon and one-point geometric Goppa codes,
and the latter method dramatically increased the number of correctable errors of
the conventional bounded distance decoding algorithm, such as the BerlekampMassey algorithm. Following those work, Shokrollahi and Wasserman [9] generalized the Sudan method [10] to one-point geometric Goppa codes, and PellikaanThis research is in part supported by the Danish National Science Research Council Grant FNV-21040368 and the MEXT 21st Century COE Program: Photonics
Nanodevice Integration Engineering.

S. Boztaş and H.F. Lu (Eds.): AAECC 2007, LNCS 4851, pp. 50–59, 2007.
c Springer-Verlag Berlin Heidelberg 2007
Generalized Sudan’s List Decoding for Order Domain Codes

51

and Wu [8] generalized the Guruswami-Sudan method [5] to generalized ReedMuller codes as the ﬁrst algorithm among three new list decoding algorithms in[8]. Augot and Stepanov [2] improved the estimation of error-correcting capability of the ﬁrst algorithm in [8].
However, up to now, nobody has successfully generalized the list decoding
algorithms [10,5] to evaluation codes from arbitrary order domains. The diﬃculty lies in the fact that existing methods [10,5,8] deal with codes coming frompolynomial rings or their factor rings and utilize their polynomial structure suchas the degree of a polynomial and the pole order of an algebraic function.
We will distill essential ingredients from Sudan’s original decoding method[10], which allow us to carry over it to evaluation codes from arbitrary orderdomains. After that, we examine the error-correcting capability of the proposed
generalization when we apply it to generalized Reed-Muller and one-point geometric Goppa codes, and show that the proposed method can correct moreerrors than [9] and the ﬁrst algorithm in [8]. We have to note that the proposed
method usually cannot correct more errors than the Guruswami-Sudan method[5] with multiplicity.
The paper is organized as follows. In Section 2 we present the modiﬁed Sudan
decoding algorithm without multiplicity. Our description does not require thatthe reader has any previous experience with order domains. Some knowledge
about generalized Reed-Muller and one-point geometric Goppa codes should do.
In Section 3 we study decoding of generalized Reed-Muller codes. We compare
our ﬁndings to the results by the ﬁrst algorithm of Pellikaan and Wu in [8] andby Augot and Stepanov in [2]. Then in Section 4 we apply our method to somecodes coming from norm-trace curves.

2

Decoding of Order Domain Codes

In this section we state the modiﬁed decoding algorithm for a large family ofcodes deﬁned from order domains. We provide translations into the case of generalized Reed-Muller codes and one-point geometric Goppa codes. Our presentation relies on [1,3,7].
Deﬁnition 1. Let R be an Fq -algebra and let Γ be a subsemigroup of Nr0 forsome r. Let ≺Nr0 be a monomial ordering on Nr0 . A surjective map ρ : R →Γ−∞ := Γ ∪ {−∞} that satisﬁes the following six conditions is said to be aweight function(W.0) ρ(f ) = −∞ if and only if f = 0(W.1) ρ(af ) = ρ(f ) for all nonzero a ∈ Fq
(W.2) ρ(f + g) Nr0 max{ρ(f ), ρ(g)} and equality holds when ρ(f ) ≺Nr0 ρ(g)(W.3) If ρ(f ) ≺Nr0 ρ(g) and h = 0, then ρ(f h) ≺Nr0 ρ(gh)(W.4) If f and g are nonzero and ρ(f ) = ρ(g), then there
exists a nonzero a ∈ Fq such that ρ(f − ag) ≺Nr0 ρ(g)(W.5) If f and g are nonzero then ρ(f g) = ρ(f ) + ρ(g).

52

O. Geil and R. Matsumoto

An Fq -algebra with a weight function is called an order domain over Fq . The
triple (R, ρ, Γ ) is called an order structure and Γ is called the value semigroupof ρ.
We have the following two standard examples of weight functions.
be
Example 1. Consider the polynomial ring R = Fq [X1 , . . . , Xm ] and let ≺Nm
0
m
given
by
(i
,
.
.
.
,
i
)
≺
(j
,
.
.
.
,
j
the graded lexicographic ordering on Nm
1
m
N0
1
m)
0
if either i1 + · · · + im < j1 + · · · + jm holds or i1 + · · · + im = j1 + · · · + jm
holds, but left most non-zero entry of j1 − i1 , . . . , jm − im ) is positive. The map
im{(i1 , . . . , im ) | X1i1 · · · Xm
∈ Supp(F )} ifρ : R → Nm
0 ∪ {−∞}, ρ(F ) := max≺Nm0
F = 0 and ρ(0) := −∞ is a weight function.
Example 2. Let Q be a rational place of a function ﬁeld in one variable over
Fq . Then R = ∪∞m=0 L(mQ) is an order domain with a weight function givenby ρ(f ) = −νQ (f ). Clearly, in this case the value semigroup Γ is simply the
Weierstrass semigroup corresponding to Q and the monomial ordering is theunique monomial ordering on N0 .
For the code construction we will need a few results.
Theorem 1. Let (R, ρ, Γ ) be an order structure. Then any set B = {fγ |ρ(fγ ) = γ}γ∈Γ constitutes a basis for R as a vector space over Fq . In particular{fλ ∈ B | λ  γ} constitutes a basis for Rγ := {f ∈ R | ρ(f )  γ}.
A basis as in Theorem 1 is known in the literature as a well-behaving basis.
In the remaining part of this section we will always assume that some ﬁxed
well-behaving basis has been chosen for the order domain under consideration.
Deﬁnition 2. Let R be an Fq -algebra. A surjective map ϕ : R → Fnq is calleda morphism of Fq -algebras if ϕ is Fq -linear and ϕ(f g) = ϕ(f ) ∗ ϕ(g) for all
f, g ∈ R, where ∗ denotes the componentwise multiplication of two vectors.
The class of codes E(λ) below includes as we shall recall generalized Reed-Muller
codes as well as one-point geometric Goppa codes.
Deﬁnition 3. Consider an order domain R over Fq and a corresponding morphism ϕ : R → Fnq . For λ ∈ Γ we deﬁne E(λ) := ϕ(Rλ ).
m

Example 3. This is a continuation of Example 1. Consider Fqq = {P1 , . . . , Pqm }mand let ϕ : Fq [X1 , . . . , Xm ] → Fqq be given by ϕ(F ) = (F (P1 ) . . . , F (Pqm )).
If we choose λ = (u, 0, . . . , 0) then E(λ) is simply the generalized Reed-Muller
code RMq (u, m) no matter how the well-behaving basis for the order domain
R = Fq [X1 , . . . , Xm ] has been chosen. For simplicity we choose in this paper
always the well-behaving basis B to be the set of monomials in X1 , . . . , Xm .
Example 4. This is a continuation of Example 2. Let {P1 , . . . , Pn } be rational places diﬀerent from Q and consider the morphism ϕ : R → Fnq given by
ϕ(f ) = (f (P1 ), . . . , f (Pn )). The code E(λ) is the one-point geometric Goppa
code CL (D, λQ) where D = P1 + · · · + Pn .

Generalized Sudan’s List Decoding for Order Domain Codes

53

We next consider some terminology from [1].
Deﬁnition 4. Let α(1) := 0 and deﬁne for i = 2, 3, . . . , n recursively α(i) to be
the smallest element in Γ that is greater than α(1), α(2), . . . , α(i−1) and satisﬁes
ϕ(Rγ )  ϕ(Rα(i) ) for all γ < α(i). Write Δ(R, ρ, ϕ) = {α(1), α(2), . . . , α(n)}.
Deﬁnition 5. For η ∈ Δ(R, ρ, ϕ) = {α(1), α(2), . . . , α(n)} deﬁne
M (η) := (η + Γ ) ∩ Δ(R, ρ, ϕ)
where η + Γ means {η + λ | λ ∈ Γ }. Let σ(η) := #M (η).
The ﬁrst part of the following theorem plays a fundamental role in our modiﬁcation of the Sudan decoding algorithm without multiplicity.
Theorem 2. If c ∈ E(λ) but c ∈ E(η) for any η with η ≺Nr0 λ then wH (c) ≥σ(λ) holds. In particular we have d(E(λ)) ≥ min{σ(η) | η ∈ Δ(R, ρ, ϕ), η  λ}.
Example 5. The above bound gives the true minimum distances of generalized
Reed-Muller codes and of Hermitian codes. For the case of one-point geometric Goppa codes the bound is an improvement to the usual bound by Goppa
which states that the minimum distance of a one-point geometric Goppa code
CL (D, λQ) is at least n − λ. More precisely, we have σ(λ) ≥ n − λ for any
λ ∈ Δ(R, ρ, ϕ). For high dimensions the inequality is in general sharp.
Theorem 2 suggests the following improved code construction.
Deﬁnition 6. Given any ﬁxed basis B = {fγ | ρ(fγ ) = γ}γ∈Γ as in Theorem 1
we deﬁne Ẽ(δ) := SpanFq {ϕ(fα(i) ) | α(i) ∈ Δ(R, ρ, ϕ) and σ(α(i)) ≥ δ}.
We have
Theorem 3. d(Ẽ(δ)) ≥ δ.
The codes Ẽ(δ) are sometimes very much better than the corresponding codes
E(λ). This is for instance the case for the improved generalized Reed-Muller
codes known as hyperbolic codes (or Massey-Costello-Justesen codes). Regarding one-point geometric Goppa codes the picture very much relies on which
particular curve we consider, but the improvement may also in this case be signiﬁcant. The idea of controlling the minimum distance of a code by choosing thefunctions fλ to be used in the code construction in a clever way will be one of themain ingredients of our modiﬁed Sudan decoding algorithm without multiplicity.
We now describe the modiﬁed Sudan decoding algorithm without multiplicity
for the codes E(λ) and Ẽ(δ). To ease notation we state the algorithm for a larger
class of codes, namely for any code C of the form
C = SpanFq {ϕ(fλ1 ), . . . , ϕ(fλk )} where {λ1 , . . . , λk } ⊆ Δ(R, ρ, ϕ).

(1)

The ﬁrst part of the decoding algorithm is to ﬁnd a proper interpolation polynomial Q(Z) with coeﬃcients from the order domain R. To set up the decoding
procedure for a given ﬁxed code C we ﬁrst need to describe sets from which
we will allow the coeﬃcients to be chosen. To this end consider the following
deﬁnition.

54

O. Geil and R. Matsumoto

Deﬁnition 7. Given a code C as above let E be some ﬁxed value (representing
the number of errors we would like to correct). For s ∈ N0 deﬁneL(E, s) := {λ ∈ Δ(R, ρ, ϕ) | for all i1 , . . . , is ∈ {1, . . . , k} we haves
fλfλiv ∈ Span{fα(1) , . . . , fα(n) } and

(2)

v=1

σ(λi ) > E for all fλi ∈ SuppB (fλsfλiv )},(3)v=1

where SuppB (f ) of f ∈ R is the set of g ∈ B that appears in the unique linear
combination of f by elements in B.
Note, that there is no requirement that i1 , . . . , is are pairwise diﬀerent. Note alsothat the set L(E, s) relies on the actual choice of well-behaving basis {fλ }λ∈Γ .
Further we observe that for large values of s we have L(E, s) = ∅. What wewill need for the modiﬁed version of Sudan type decoding without multiplicity∞
to work is a number E such that s=0 #L(E, s) > n. As indicated above thevalue E will be the number of errors we can correct and therefore we would ofcourse like to ﬁnd a large value of E such that the above condition is met. On
the other hand the smallest value t such thatt#L(E, s) > n

(4)

s=0

holds will to some extent reﬂect the complexity of the decoding algorithm. So
in some situations it might be desirable to choose a smaller value of E thanthe largest possible one to decrease the complexity of the algorithm. Choosing
parameters E and t and calculating the corresponding sets L(E, 0), . . . , L(E, t)
is something that is done when setting up the decoding system. Hence, thecomplexity of doing this is not of very high importance. However, as we will
demonstrate in the case of generalized Reed-Muller codes, there are often tricks
to ease the above procedure. We are now able to describe the modiﬁed Sudan
decoding algorithm without multiplicity.
Algorithm 1
Input: A code C as in (1), parameters E, t such that (4) is met and corresponding
sets L(E, 0), . . . , L(E, t). A received word r
Output: A list of at most t codewords that contains all codewords within distanceat most E from r
Step 1. Find Q0 , . . . , Qt ∈ R not all zero such that Qs ∈ SpanFq {fλ | λ ∈ L(E, s)}for s = 0, . . . , t and such that ts=0 (ϕ(Qs )) ∗ rs = 0 holds. (Here rs means thecomponent wise productof r with itself s times and r 0 = 1.)
t
Step 2. Factorize s=0 Qs Z s ∈ R[Z] and detect all possible f ∈ R such thatZ − f appears as a factor, which can be done by the method of Wu [11].
Step 3. Return {ϕ(f ) | f is a solution from step 2}.

Generalized Sudan’s List Decoding for Order Domain Codes

55

Theorem 4. Algorithm 1 gives the claimed output.
Proof: Condition (4) ensures that the set of linear equations in step 1 has
more indeterminates than equations. Therefore Q0 , . . . , Qt as described in step
1 indeed do exist.
Consider any code word c. That is, let c = ϕ(f ) where f is of the form
f = kv=1 βv fλv . From the conditions (2) and (3) we get thatsQi f i ∈ Span{fα(1) , . . . , fα(n) }

(5)

i=0

holds and thatsQi f i ) satisﬁes σ(α(v)) > E.
all fα(v) ∈ SuppB (

(6)

i=0

Assume now that c = ϕ(f ) is a code word within Hamming
t distance at mostt
E from r. But then s=0 (ϕ(Qs )) ∗ (ϕ(f ))s diﬀers from s=0 (ϕ(Qs )) ∗ rs = 0
in at most E positions implyingt
Qs f s )) ≤ E
wH (ϕ((7)

s=0

Combininglead to the conclusion
 (5), (6) and (7) with the ﬁrst part of Theorem 2that ϕ( ts=0 Qs f s ) = 0 must hold, and Eq. (2) implies ts=0 Qs f s = 0. Thatis, f is a zero of Q(Z). But order domains are integral domains and therefore
Quot(R) is a ﬁeld. It follows that Z − f divides Q(Z) ∈ Quot(R)[Z]. As theleading coeﬃcient of Z − f is 1 we conclude that Q(Z) = (Z − f )K(Z) for some
K(Z) with coeﬃcients in R. Hence, indeed Z − f appears in the factorization instep 2 of the algorithm. Finally, as Q(Z) has degree at most t the list in step 3
is of length at most t.

Remark 1. We have used the Hamming weight to ensure Q(Z) = 0 in the above
argument. The conventional method [10,9] used the degree of a polynomial andthe pole order of an algebraic function to ensure Q(Z) = 0. The use of Hamming
weight allows us to list-decode codes from any order domains.
The following example illustrates the nature of our modiﬁcation.
Example 6. Consider a one-point geometric Goppa code E(η) where η < n. Let,g be the genus of the function ﬁeld or equivalently let g = #N0 \Γ . The set
L (E, s) = {λ ∈ Γ | λ + sη < n − E}is easily calculated and we have L (E, s) ⊆ L(E, s). Replacing L(E, s) withL (E, s) in Algorithm 1 gives the traditional algorithm [9] without multiplicity
for the one-point geometric Goppa code E(η). Hence, for one-point geometricGoppa codes the modiﬁed algorithm can correct at least as many errors as theoriginal one and in cases where the sets L(E, s) are larger than the sets L (E, s)
we will be able to correct more errors by the modiﬁed algorithm.

56

3

O. Geil and R. Matsumoto

Generalized Reed-Muller Codes

In this section we consider the implementation of Algorithm 1 to the case ofgeneralized Reed-Muller codes of low dimensions. Recall, from Example 1 that wehave a weight function ρ : Fq [X1 , . . . , Xm ] → Nm
0 given by ρ(F ) = (i1 , . . . , im ) if
X i1 · · · X im is the leading monomial of F with respect to the monomial orderingfrom Example 1. Recall from Example 3 that we always choose the well-behavingbasis B of Fq [X1 , . . . , Xm ] to be simply the set of monomials in X1 , . . . , Xm . From
Deﬁnition 4, for the weight function under consideration the σ function is easily
calculated as followsm(q − iv ).
σ ((i1 , . . . , im )) =v=1

We get the following Lemma that signiﬁcantly eases the job with ﬁnding L(E, s).
Lemma 1. Let u < q and consider the generalized Reed-Muller code RMq (u, m).
The description of L(E, s) simpliﬁes toL(E, s) = {(l1 , . . . , lm ) ∈ Nm
0 |l1 + su, . . . , lm + su < q,
(q − l1 − su)(q − l2 ) · · · (q − lm ) > E,
..
.

(8)
(9)

(q − l1 ) · · · (q − lm−1 )(q − lm − su) > E}
Proof: To see that (9) corresponds to (3) we observe that the σ function fromthis section is concave. The fact that (8) corresponds to (2) follows from similararguments.
To decide how many errors our algorithm can correct we should according to (4)look for the largest possible E such that a t exists with ts=0 #L(E, s) > n = q m .
Of course such an E can always be found by an extensive trial and error. For thecase of m = 2 that is, codes of the form RMq (u, 2) we now give an approximative
trial and error method that requires only few calculations. It turns out that thisapproximative method is actually rather precise.
For a ﬁxed s the conditions to be satisﬁed are
l1 + su < q,
(q − l1 − su)(q − l2 ) > E,

l2 + su < q(10)(q − l1 )(q − l2 − su) > E(11)

We make the (natural) assumption
0 ≤ l1 , l2 < q.

(12)Equations (11) and (12) imply (10) which we therefore can forget about. WhenE < q, it is easy to lower-bound the number of solutions to (11) and (12). Under
the assumption E ≥ q we now want to count the number of possible solutions

Generalized Sudan’s List Decoding for Order Domain Codes57

to (11) and (12). The number of such solutions is bounded below by the area inthe ﬁrst quadrant of the points that are under both the curve
l2 = q −E
q − l1 − su

(13)E
q − l1(14)

as well as are under the curve
l2 = q − su −By symmetry these two curves intersect in two points of the form (γ, γ). We
have to use the point closer to the origin, which we calculate to be√
2q − su − s2 u2 + 4E
γ=.
2Therefore (again by symmetry) the area is
 γ

E
1
2
(q − su −)dl1 − γ 2
q − l12
0
1= 2(γ(q − su) − E(ln(q) − ln(q − γ)) − γ 2 )2A rougher but simpler estimate is found by approximating the above area withthe area of the polygon with corners (0, 0), (0, q − Eq − su), (γ, γ), (q − Eq − su, 0).
Here the second point is found by substituting l1 = 0 in (14) and the fourth
point is found by substituting l2 = 0 in (13). The estimate can serve as a lower
bound due to the fact that both functions in (13) and (14) are concave. The
area of the polygon is found to be γ(q − (E/q) − su). Whether we use the ﬁrst
estimate or the second estimate we would next like to know the largest value oft such that L(E, t) = ∅. But this is easily calculated from the requirement γ ≥ 0
implying t = (q − (E/q))/u. Combining the above results with Theorem 4 we
get.
Proposition 1. Consider the code RMq (u, 2) with u < q. For E ≥ q Algorithm 1 can correct at least E errors if the following holds
(q−E/q)/u


s=0

1
(2(γ(q − su) − E(ln(q) − ln(q − γ)) − γ 2 )) > q 2 .
2Corollary 1. Consider the code RMq (u, 2) with u < q. For E ≥ q Algorithm 1
can correct at least E errors if the following holds
(q−E/q)/u
s=0(γ(q −E− su)) > q 2 .
qAugot and Stepanov in [2] gave an improved estimate of the sum of multiplicities
in terms of the total degree of a multivariate polynomial as follows

58

O. Geil and R. Matsumoto

Theorem 5. The sum of multiplicities in Fm
q of an m-variate polynomial of
total degree d is upper bounded by dq m−1 . The number of zeros with multiplicity
r of such a polynomial is upper bounded by dq m−1 /r.
The above bound is better than the combination of Lemmas 2.4 and 2.5 in [8].
As noted by Augot and Stepanov Theorem 5 allows us to use more monomials
in the ﬁrst list decoding algorithm in [8], and the resulting decoding algorithm
has the larger error-correcting capability.
The error correcting capability of the modiﬁed list decoding algorithm with
Theorem 5 is compared with ours and the original Pellikaan-Wu. The multiplicity used in Augot and Stepanov’s estimate is 10. EP W , EP W A , Eours are theerror correcting capability of the original Pellikaan-Wu, Augot-Stepanov, andour method, respectively. Finally, EP W A1 respectively EP W A2 are the error correcting capability of the Augot-Stepanov modiﬁed the Pellikaan-Wu algorithm
when multiplicity is 1 respectively 2. q = 16, m = 2, n = 256.
u
2 3 4 5 6 7 8 9 10 11 12
EP W 63 46 34 26 19 14 10 7 5 3 2Eours 76 55 44 34 27 21 15 13 11 9 6
EP W A 118 99 83 70 59 49 41 33 25 19 11
EP W A1 47 31 15 -1 -17 -33 -33 -49 -49 -65 -65
EP W A2 87 63 47 31 23 7 -1 -9 -17 -25 -25
Remark 2. The authors of the present paper have done a lot of computer experiments regarding the error correcting capability of the proposed decoding method
for generalized Reed-Muller codes. In all of these experiments we were able tocorrect as many errors as Remark 2.1 in [8] guarantees Pellikaan-Wu algorithm(with multiplicity) to be able to.

4

One-Point Geometric Goppa Codes

As already mentioned our proposed decoding algorithm applies among otherthings to one-point geometric Goppa codes. In this section we will be concernedwith codes deﬁned from the norm-trace curve introduced in [4]. These are deﬁned
r
r−1
r−2
by the polynomial X (q −1)/(q−1) −Y q −Y q −· · · Y ∈ Fqr [X, Y ]. We consider
codes
(15)
CL (P1 + · · · + Pq2r−1 , sP∞ )where P1 , . . . , Pq2r−1 , P∞ are the rational places of the corresponding function
ﬁeld and P∞ is the unique place among these with νP∞ (x) < 0. We do not go
into detail with how to implement the proposed algorithm but present only someexamples.
Example 7. In this example we consider the norm-trace curve corresponding to
q = 2 and r = 6. These are of length n = 211 . In the table below s is the value
used in (15) whereas Eour is the error correcting capability of the proposedGeneralized Sudan’s List Decoding for Order Domain Codes

59

method and EGS1 is the error correcting capability of Sudan’s algorithm [10]without multiplicity. By 900-929 we indicate that maximal performance is anumber between 900 and 929. With multiplicity, Guruswami-Sudan’s algorithm[5] outperform the proposed method.
64
96
192 288 480
sEour 1008 900-929 660-669 527 346
EGS1 962 804
479 237 14
Example 8. In this example we consider the norm-trace curve corresponding to
q = 3 and r = 3. These are of length n = 35 . In the table below s is the value usedin (15) whereas Eour is the error correcting capability of the proposed method
and EGS1 is the error correcting capability of Sudan’s algorithm [10] without
multiplicity. With multiplicity, Guruswami-Sudan’s algorithm [5] outperform the
proposed method.
s 63 70 80 88
Eour 55 51 43 38
EGS1 53 47 39 33

References
1. Andersen, H.E., Geil, O.: Evaluation Codes From Order Domain Theory. Finite
Fields and Their Appl. (2007) doi:10.1016/j.ﬀa.2006.12.004
2. Augot, D., Stepanov, M.: Decoding Reed-Muller Codes with the GuruswamiSudan’s Algorithm. In: Slides of Talk Given by D. Augot at Workshop D1 Special Semester on Gröbner Bases and Related Methods, RICAM, Linz (2006),
http://www.ricam.oeaw.ac.at/specsem/srs/groeb/download/Augot.pdf
3. Geil, O., Pellikaan, R.: On the Structure of Order Domains. Finite Fields and Their
Appl. 8, 369–396 (2002)
4. Geil, O.: On Codes From Norm-Trace Curves. Finite Fields and Their Appl. 9,351–371 (2003)
5. Guruswami, V., Sudan, M.: Improved Decoding of Reed-Solomon and AlgebraicGeometry Codes. IEEE Trans. Inform. Theory 45(4), 1757–1767 (1999)
6. Høholdt, T., van Lint, J., Pellikaan, R.: Algebraic Geometry Codes. In: Pless,
V.S., Huﬀman, W.C. (eds.) Handbook of Coding Theory, pp. 871–961. Elsevier,
Amsterdam (1998)
7. O’Sullivan, M.E.: New Codes for the Berlekamp-Massey-Sakata Algorithm. Finite
Fields and Their Appl. 7, 293–317 (2001)
8. Pellikaan, R., Wu, X.-W.: List Decoding of q-ary Reed-Muller Codes. IEEE Trans.
Inform. Theory 50, 679–682 (2004)
9. Shokrollahi, M.A., Wasserman, H.: List Decoding of Algebraic-Geometric Codes.
IEEE Trans. Inform. Theory 45(2), 432–437 (1999)
10. Sudan, M.: Decoding of Reed Solomon Codes Beyond the Error Correction Bound.
J. Complexity 13, 180–193 (1997)
11. Wu, X.-W.: An Algorithm for Finding the Roots of the Polynomials Over Order
Domains. In: 2002 IEEE International Symposium on Information Theory, p. 202.
IEEE Press, New York (2002)