We reformulate an interpolationbased unique decoding algorithm of AG codes, using the theory of Gröbner bases of modules on the coordinate ring of the base curve. The conceptual description of the reformulated algorithm lets us better understand the majority voting procedure, which is central in the interpolationbased unique decoding. Moreover the smaller Gröbner bases imply smaller space and time complexity of the algorithm.
AMS Mathematics Subject Classification: 94B35, 94B27.
1. Introduction
Recently a new kind of unique decoding algorithm of algebraic geometry codes was presented
[4]
. The algorithm decodes the primal AG code that consists of codewords obtained by evaluation of functions at rational points of an algebraic curve, unlike the classical syndrome decoding algorithm that decodes the dual code. Based on Gröbner bases of modules over a univariate polynomial ring, the algorithm has a regular data and control structure that is suitable for parallel hardware implementation, like Kötter's algorithm for the syndrome decoding
[3]
. The ideas used can be traced back to
[2
,
1]
.
In this paper, we reformulate the previous algorithm, using the theory of Gröbner bases of modules on the coordinate ring of the base curve. This approach eliminates the technical complexity of the previous algorithm in a large degree, and results in a conceptually clean description of the algorithm which contributes to a better understanding of the majority voting procedure, which plays a central role in the interpolationbased unique decoding. Moreover the new approach allows the algorithm to work with smaller Gröbner bases so that it can run faster and uses less space than the previous algorithm in a serial implementation.
Comparing with the wellknown classical unique decoders of AG codes, BerlekampMasseySakata algorithm
[7]
and Kötter’s algorithm
[3]
, the features of the new algorithm put it in a unique place in the following table.
That is, the new algorithm corrects the evaluation code
C
on a plane curve
X
working with the Gröbner bases on
[
X
], the coordinate ring of
X
. Thus we may view the new algorithm as a
dual
version of the BMS algorithm.
Let us briefly review basic facts about AG codes. Like the previous algorithm in
[4]
and the BMS decoding algorithm in
[7]
, the new algorithm is formulated for the AG codes from the MiuraKamiya curves
[5]
, which include Hermitian curves as prominent special cases. A MiuraKamiya curve
X
is an irreducible plane curve defined by the equation
over a field
with gcd(
a
,
b
) = 1 and 0 ≠
d
∈
. It is well known that
X
has a unique point
P
_{∞}
at infinity and has a unique valuation
associated with it. Let
for
f
in the coordinate ring
R
of
X
. Then
δ
(
x
) =
a
and
δ
(
y
) =
b
. By the equation of the curve, a function in the coordinate ring
R
=
[
x
,
y
] =
[
X
,
Y
]/⟨
E
⟩ can be written as a unique
linear combination of the monomials
x^{i}y^{j}
with
i
≥ 0 and 0 ≤
j
<
a
, which we call
monomials of R
. The numerical semigroup of
R
at
P
_{∞}
,
is a subset of the Weierstrass semigroup at
P
_{∞}
. See
[6]
for basic terminology about numerical semigroups. As gcd(
a
,
b
) = 1, there is an integer
b
′ such that
b
′
b
≡ 1 (mod
a
). If
s
=
ai
+
bj
is a nongap, then
b′s
mod
a
=
j
, (
s
−
bj
)/
a
=
i
, and therefore
i
and
j
are uniquely determined. Hence the monomials of
R
are in onetoone correspondence with nongaps in
S
. For a nongap
s
, let
φ_{s}
denote the unique monomial with
δ
(
φ_{s}
) =
s
.
Let
P
_{1}
,
P
_{2}
, . . . ,
P_{n}
be nonsingular rational points of
X
. The evaluation map ev from
R
to the Hamming space
is the
linear map defined by
φ
↦ (
φ
(
P
_{1}
),
φ
(
P
_{2}
), . . . ,
φ
(
P_{n}
)). Let
u
be a fixed positive integer less than
n
and define
L_{u}
= {
f
∈
R

δ
(
f
) ≤
u
} = ⟨
φ_{s}

s
∈
S
,
s
≤
u
⟩, where brackets denote the linear span over
. Then the AG code
C_{u}
is defined as the image of
L_{u}
under ev. As
u
<
n
, ev is onetoone on
L_{u}
. So the dimension of the linear code
C_{u}
equals
L_{u}
= {
s
∈
S

s
≤
u
}.
In Section 2, we review the theory of the Gröbner bases of modules over the coordinate rings of algebraic curves, and outline the interpolationbased decoding algorithm. The algorithm operates by iterating two core steps, the Gröbner basis computation step and the message guessing step by the majority voting procedure. Sections 3 and 4 are devoted to these core steps. In Section 5, we demonstrate the algorithm with a Hermitian code. In the final section, we give some remarks about the complexity of the algorithm.
2. Interpolation decoding
We assume a codeword
c
in
C_{u}
is sent through a noisy communication channel and
v
∈
is the vector received from the channel. Let
v
=
c
+
e
with the error vector
e
. Then
c
= ev(
μ
) for a unique
where we assume that the vector (
ω_{s}

s
∈
S
,
s
≤
u
) is the message encoded into the codeword
c
. The decoding problem is essentially to find
ω_{s}
for all nongap
s
≤
u
from the given vector
v
.
For
s
≥
u
, let
v
^{(s)}
=
v
,
c
^{(s)}
=
c
, and
μ
^{(s)}
=
μ
. For nongap
s
≤
u
, let
and for gap
s
≤
u
, let
v
^{(s−1)}
=
v
^{(s)}
,
c
^{(s−1)}
=
c
^{(s)}
, and
μ
^{(s−1)}
=
μ
^{(s)}
. Note that
for all
s
. Hence we see that we can find
ω_{s}
iteratively.
A polynomial in
R
[
z
] defines a function on the product surface of
X
and the line
and can be evaluated at a point (
P
,
α
) with
P
∈
X
,
α
∈
. Hence we can define the
interpolation module
for
v
and similarly for
v
^{(s)}
. These interpolation modules are indeed modules over
R
, and finitedimensional vector space over
. Note that
where
J
= ∩
_{1≤i≤n}
m
_{i}
and ev(
h_{v}
) =
v
, and m
_{i}
= ⟨
x
−
α_{i}
,
y
−
β_{i}
⟩ is the maximal ideal of
R
associated with
P_{i}
= (
α_{i}
,
β_{i}
). Recall that by Lagrange interpolation,
h_{v}
can be computed fast from
v
. We will see that the key to find
ω_{s}
is the Gröbner basis of
with respect to a monomial order >
_{s}
, defined as follows.
Let
s
be an integer. For monomial
x^{i}y^{j}z^{k}
∈
R
[
z
], let
δ_{s}
(
x^{i}y^{j}z^{k}
) =
δ
(
x^{i}y^{j}
) +
sk
. In particular,
δ_{s}
(
x^{i}y^{j}z
) =
ai
+
bj
+
s
and
δ_{s}
(
x^{i}y^{j}
) =
δ
(
x^{i}y^{j}
) =
ai
+
bj
. The order >
_{s}
on
Rz
⊕
R
put the monomials in the order of their
δ_{s}
values, and breaks the tie with higher
z
degree. For
f
in
Rz
⊕
R
, the notations lt
_{s}
(
f
), lm
_{s}
(
f
), and lc
_{s}
(
f
) denote the leading term, the leading monomial, and the leading coefficient of
f
, respectively, with respect to >
_{s}
. Note that for
f
∈
Rz
⊕
R
, there are unique
f^{U}
and
f^{D}
∈
R
such that
f
=
f^{U}z
+
f^{D}
(the superscripts
U
and
D
may be read “upstairs” and “downstairs”, respectively, with
z
being the staircase). By the definitions, we have the following lemma.
Lemma 2.1.
Let f
=
f^{U}z
+
f^{D}
with
f^{U}
,
f^{D}
∈
R
.
Then
lm
_{s}
(
f
) ∈
Rz
⇔
δ
(
f^{U}
) +
s
≥
δ
(
f^{D}
),
where equality holds if and only if
lm
_{s}
(
f
) ∈
Rz and
lm
_{s−1}
(
f
) ∈
R
.
Now let
M
be a submodule of
Rz
⊕
R
. A finite subset
B
of
M
is called a
Gröbner basis
with respect to >
_{s}
if the leading term of every element of
M
is divided by the leading term of some element of
B
. We will write
where
are some index sets, with the understanding that each
G_{i}
is a basis element such that lm
_{s}
(
G_{i}
) ∈
R
and each
F_{j}
is a basis element such that lm
_{s}
(
F_{j}
) ∈
Rz
. The
sigma set
Σ
_{s}
= Σ
_{s}
(
M
) of
M
is the set of all leading monomials of the polynomials in
M
with respect to >
_{s}
. The
delta set
Δ
_{s}
= Δ
_{s}
(
M
) of
M
is the complement of Σ
_{s}
in the set of all monomials of
Rz
⊕
R
. For the case that
M
is an ideal of
R
, we may omit the superfluous s from the notations, and denote >
_{s}
simply by >. Note that if lm
_{s}
(
f
) ∈
Rz
, then lm
_{s}
(
f
) = lm(
f^{U}
)
z
, and if lm
_{s}
(
f
) ∈
R
, then lm
_{s}
(
f
) = lm(
f^{D}
). It is easy to see by the definition of Gröbner bases that
where Σ(
T
), Δ(
T
) with a set
T
of polynomials in
R
have natural definitions.
As
J
is an ideal of
R
, it has a Gröbner basis
with respect to >, and
since
J
is the ideal associated with the sum of
n
rational points on
X
. By (2), we see that
(
Rz
⊕
R
/
I_{v}
) =
(
R
/
J
) =
n
. Let
N
=
δ
(
h_{v}
). The set
is then a Gröbner basis of
I_{v}
with respect to >
_{N}
. Let us denote a Gröbner basis of
with respect to >
_{s}
by
Observe that if
s
is a nongap ≤
u
, then the set
is still a Gröbner basis of
with respect to >
_{s}
, but not with respect to >
_{s−1}
in general. These observations lead to the following interpolation decoding algorithm.
Interpolation Decoding Algorithm.
Let
v
be the received vector.

Initialize:Computehv. LetwhereN=δ(hv).

Main:Repeat the following forsfromNto 0.

M1:Ifsis a nongap ≤u, then make a guessw(s)forωs, and let

M2:ComputeB(s−1)from

Finalize:Output (w(s) nongaps≤u), wherew(s)= 0 forN
In the next section, we will elaborate on the step
M2
. The results in the section will lay a foundation for Section 4, in which we give details of the main steps
M1
and
M2
.
3. Gröbner basis computation
First we review the concept of the lcm, least common multiple, for the monomials of
R
. For two monomials
φ_{s}
and
φ_{t}
, we say
φ_{s}
divides
φ_{t}
if there exists a unique monomial λ such that
The unique monomial λ will be denoted by the quotient
φ_{t}
/
φ_{s}
. Note that
φ_{s}
divides
φ_{t}
if and only if
t
−
s
is a nongap, and in this case, actually λ =
φ
_{t−s}
. Therefore
φ_{s}
and
φ_{t}
do not divide each other if and only if
s
+
S
and
t
+
S
do not contain each other.
Proposition 3.1.
Suppose s
+
S and t
+
S do not contain each other
.
Then there are unique nongaps l
_{1}
and l
_{2}
such that
Indeed we can take l
_{1}
= min(
s
+ℕ
a
) ∩ (
t
+ℕ
b
)
and l
_{2}
= min(
s
+ℕ
b
) ∩ (
t
+ℕ
a
).
Proof.
Recall that
S
= ℕ
a
+ ℕ
b
. By the definitions of
l
_{1}
and
l
_{2}
, the inclusions
l
_{1}
+
S
⊂ (
s
+
S
)∩(
t
+
S
),
l
_{2}
+
S
⊂ (
s
+
S
)∩(
t
+
S
) are obvious. So it remains to show the reverse inclusion. Suppose
c
∈ (
s
+
S
)∩(
t
+
S
). Then
c
=
s
+
s
_{1}
a
+
s
_{2}
b
=
t
+
t
_{1}
a
+
t
_{2}
b
for some
s
_{1}
,
s
_{2}
,
t
_{1}
,
t
_{2}
∈ ℕ. By our assumption that
s
+
S
and
t
+
S
do not contain each other, we either have
s
_{1}
≥
t
_{1}
,
s
_{2}
<
t
_{2}
or
s
_{1}
<
t
_{1}
,
s
_{2}
≥
t
_{2}
. In the former case,
s
+(
s
_{1}
−
t
_{1}
)
a
=
t
+(
t
_{2}
−
s
_{2}
)
b
∈ (
s
+ℕ
a
)∩(
t
+ℕ
b
) ⊂
l
_{1}
+
S
, and hence
c
∈
l
_{1}
+
S
. In the latter case, similarly we have
c
∈
l
_{2}
+
S
. This shows that (
s
+
S
) ∩ (
t
+
S
) ⊂ (
l
_{1}
+
S
) ∪ (
l
_{2}
+
S
).
By the definition, we call
and
the
lcms
of
φ_{s}
and
φ_{t}
. In the case when
φ_{s}
divides
φ_{t}
, we will call
φ_{t}
the lcm of
φ_{s}
and
φ_{t}
.
Let
be a Gröbner basis of a submodule
M
of
Rz
⊕
R
with respect to >
_{s}
. We want to compute a Gröbner basis of the same module
M
with respect to >
_{s−1}
from
B
. Note that while lm
_{s−1}
(
G_{i}
) = lm
_{s}
(
G_{i}
) ∈
R
for all
, we may have either lm
_{s−1}
(
F_{j}
) = lm
_{s}
(
F_{j}
) ∈
Rz
or lm
_{s−1}
(
F_{j}
) ∈
R
depending on
. Let Σ
_{s}
and Δ
_{s}
denote the sigma set and the delta set of
M
with respect to >
_{s}
, respectively. Observe that Σ
_{s−1}
∩
Rz
⊂ Σ
_{s}
∩
Rz
, Σ
_{s−1}
∩
R
⊃ Σ
_{s}
∩
R
.
For those
such that lm
_{s−1}
(
F_{j}
) = lm
_{s}
(
F_{j}
) ∈
Rz
, define spoly(
F_{j}
) = {
F_{j}
}. If lm
_{s−1}
(
F_{j}
) ∈
R
∩Σ
_{s}
, then there is an
such that lm
_{s}
(
G_{i}
)lm
_{s−1}
(
F_{j}
), and then, with one such
i
, define
Finally, if lm
_{s−1}
(
F_{j}
) ∈
R
∩ Δ
_{s}
, then define
which is generally not a singleton set unlike the previous two cases.
Proposition 3.2.
For every f
∈ spoly(
F_{j}
), lm
_{s−1}
(
f
)
is in Rz
.
Proof.
Recall that lm
_{s}
(
F_{j}
) ∈
Rz
. Suppose lm
_{s−1}
(
F_{j}
) ∈
R
, and let
ψ
be an lcm of lm
_{s−1}
(
F_{j}
) and lm
_{s}
(
G_{i}
) for any
. Then by Lemma 2.1,
Therefore
On the other hand,
As the monic terms cancel each other,
Therefore
and hence by Lemma 2.1,
For the case when lm
_{s−1}
(
F_{j}
) ∈
R
∩ Σ
_{s}
, notice that lm
_{s−1}
(
F_{j}
) is the lcm.
Proposition 3.3.
A monomial φ is in R
∩ Σ
_{s−1}
if and only if there exists an
such that
lm
_{s−1}
(
G_{i}
)
φ or there exists a
such that
lm
_{s−1}
(
F_{j}
) ∈
R
∩Δ
_{s} and
lm
_{s−1}
(
F_{j}
)
φ
.
Proof.
Both lm
_{s−1}
(
G_{i}
)
φ
and lm
_{s−1}
(
F_{j}
)
φ
imply
φ
∈
R
∩ Σ
_{s−1}
. Let us show the converse. If
φ
∈
R
∩ Σ
_{s}
, then lm
_{s}
(
G_{i}
)
φ
for some
, and therefore lm
_{s−1}
(
G_{i}
)
φ
. As
R
∩ Σ
_{s−1}
⊃
R
∩ Σ
_{s}
, it remains to consider the case when
φ
∈
R
∩ (Σ
_{s−1}
＼ Σ
_{s}
).
Suppose
f
∈
M
is such that
φ
= lm
_{s−1}
(
f
) ∈
R
∩(Σ
_{s−1}
＼Σ
_{s}
). Since
φ
∉
R
∩Σ
_{s}
, we must have lm
_{s}
(
f
) ∈
Rz
, and hence by Lemma 2.1,
δ
(
f^{U}
)+
s
=
δ
(
f^{D}
) =
δ
(
φ
). Then lm
_{s}
(
F_{j}
)lm
_{s}
(
f
) for
. As lm
_{s}
(
F_{j}
) ∈
Rz
, we have
where actually equality holds as we will show now. Assume the contrary, that is,
Then
These imply
contradictory to the assumption
φ
∉
R
∩ Σ
_{s}
. Hence
and
Therefore lm
_{s−1}
(
F_{j}
)
φ
, and lm
_{s−1}
(
F_{j}
) ∈
R
∩ Δ
_{s}
.
roposition 3.4.
A monomial φ is in Rz
∩ Σ
_{s−1}
if and only if there exists a
such that
lm
_{s−1}
(
f
)
φ for some f
∈ spoly(
F_{j}
).
Proof.
By Proposition 3.2, the converse is clear. Let us assume
φ
∈
Rz
∩ Σ
_{s−1}
. Suppose
φ
= lm
_{s−1}
(
f
) for some
f
∈
M
. Then
φ
= lm
_{s}
(
f
), and there exists some
such that lm
_{s}
(
F_{j}
)
φ
. If lm
_{s−1}
(
F_{j}
) ∈
Rz
, then
F_{j}
∈ spoly(
F_{j}
) and lm
_{s−1}
(
F_{j}
) = lm
_{s}
(
F_{j}
)
φ
.
Suppose lm
_{s−1}
(
F_{j}
) ∈
R
∩Σ
_{s}
. Then there is an
such that lm
_{s}
(
G_{i}
)lm
_{s−1}
(
F_{j}
) and
and by (3),
Suppose lm
_{s−1}
(
F_{j}
) ∈
R
∩Δ
_{s}
. Note that
δ
(
f^{U}
)+
s
>
δ
(
f^{D}
),
and hence
Thus we see that
and hence there is an
such that
Now there is an lcm
ψ
of lm
_{s−1}
(
F_{j}
) and lm
_{s}
(
G_{i}
) such that
and
By (3),
and finally from (4),
Combining the above results, we obtain
Theorem 3.5.
Suppose that
is a Gröbner basis of M with respect to
>
_{s}
.
Then
is a Gröbner basis of M with respect to
>
_{s−1}
.
In general, the Gröbner basis may contain more elements than necessary. Indeed, we can reduce each set in the union by removing the redundant elements whose leading term is divisible by that of other elements in the set. We will denote this
reduced
Gröbner basis of
M
with respect to >
_{s−1}
by
4. Message Selection
The ideal of the error vector
e
defined by
has a Gröbner basis {
ϵ_{i}

i
∈
Ɛ
} with respect to >, and
Recall that
is a Gröbner basis of
with respect to >
_{s}
. Observe that
which results in
and hence
Therefore
Now let
s
be a nongap ≤
u
. Let us consider the module
for
w
∈
. Note that
is a Gröbner basis of
with respect to >
_{s}
since lm
_{s}
(
f
(
z
+
wφ_{s}
)) = lm
_{s}
(
f
) for all
. For the same reason,
Observe that
Hence
In Theorem 4.3 below, we will characterize
ω_{s}
as such a
w
that makes the value
smallest, provided that wt(
e
) is not too large. Recall that
in the following arguments.
Lemma 4.1.
For
Proof.
Observe that
Therefore
Hence
equivalent to the second equality.
Lemma 4.2.
Δ(
J_{e}φ_{s}
) = wt(
e
) +
s
.
Proof.
Note that
The equality 
S
＼ (
s
+
S
) =
s
holds for any numerical semigroup
S
, since
S
is closed under addition and contains all large enough integers.
Theorem 4.3.
The value
is smallest for w
=
ω_{s}
,
provided that
Δ(
J
) ∪ Δ(
Rφ_{s}
) −
s
> 2wt(
e
).
Proof.
We need to show that for
By (7) and the previous lemmas, a sufficient condition for the above is
since Δ(
J
) =
n
. Finally note that Δ(
J
) ∪ Δ(
J_{e}φ_{s}
) ≥ Δ(
J
) ∪ Δ(
Rφ_{s}
).

Note thatis smallest when so is
since
is independent of
w
. The value
can be computed using the Gröbner bases of
with respect to >
_{s}
and >
_{s−1}
. As we saw in Section 3, the Gröbner basis of
with respect to >
_{s−1}
is determined from
the Gröbner bases of
with respect to >
_{s}
. Precisely, according to Proposition 3.3, the set
is determined by the monomials
that lies in
We note that for each
there is a unique
w_{j}
∈
such that lm
_{s−1}
(
F_{j}
(
z
+
w_{j}φ_{s}
)) ∈
Rz
, and
if and only if
w
≠
w_{j}
. In fact,
where
d
is the coefficient of the monomial
Proposition 4.4.
Let
⊔
denote disjoint union
.
We have
Proof.
The first equality follows from Proposition 3.3. It remains to show that the second union is disjoint. Assume that for
c
_{1}
,
c
_{2}
∈
with
c
_{1}
≠
c
_{2}
, there is a monomial
φ
∈
R
such that
φ
is in the intersection of
and
Let
and monomials
ψ
, χ. Then we will show that
contradicting the assumption that
Indeed notice that
Hence the coefficient of the monomial
φ
in the first term of the polynomial in (8) is
where
d
_{1}
is the coefficient of the monomial
In the same way, the coefficient of the monomial
φ
in the second term after the minus in (8) is
where
d
_{2}
is the coefficient of the monomial
These two coefficients are different because we assumed
Hence (8) follows.
We observe that for
c
,
w
∈
with
w
≠
c
,
Therefore this set is independent of
w
, and is determined by
B
^{(s)}
. Let
Then Proposition 4.4 implies
is smallest when
w
=
c
with
d_{c}
largest. Now we elaborate the main steps of the interpolation decoding algorithm as follows.

M1:If s is a nongap ≤u, then do the following. Otherwise let

M1.1:Compute the setwhereanddis the coefficient of the monomial

M1.2:Letw(s)=c∈Wwith largest

M1.3:Let

M2:LetCompute
Theorem 4.5.
The algorithm outputs w
^{(s)}
=
ω_{s} for all s
∈
S
,
s
≤
u if
where ν
(
s
) = Δ(
J
) ∪ Δ(
Rφ_{s}
) −
s for s
∈
S
.
Moreover d_{u}
≥
n
−
u
.
Proof.
By Theorem 4.3, the condition
d_{u}
> 2wt(
e
) implies that the algorithm computes
w
^{(s)}
=
ω_{s}
for each iteration for nongap s from
u
to 0. To see
d_{u}
≥
n
−
u
, notice that Δ(
J
) ∪ Δ(
Rφ_{s}
) ≥ Δ(
J
) =
n
.
5. Decoding Hermitian Codes
Let us consider the Hermitian code
C_{u}
defined on the Hermitian curves with equation
Y^{q}
+
Y
−
X
^{q+1}
= 0 over
There are
q
^{3}
rational points on the Hermitian curve, and
In Theorem 5.1, we determine the performance of the decoding algorithm for
C_{u}
. Recall that the same result was proved for the previous algorithm in Proposition 14 in
[4]
, but the proof for the present algorithm is clearer and short.
Theorem 5.1.
For nongap u
<
q
^{3}
,
let u
=
aq
+
b
, 0 ≤
b
<
q
.
Then d_{u}
=
q
^{3}
−
aq
if b
≤
a
+
q
−
q
^{2}
and d_{u}
=
q
^{3}
−
u if b
>
a
+
q
−
q
^{2}
.
Proof.
We first compute
ν
(
s
) for nongap
s
=
qs
_{1}
+
s
_{2}
<
q
^{3}
. As
we have
ν
(
s
) = {
t
∈
S

q
^{3}
+
t
−
s
∉
S
} +
q
^{3}
−
s
. Note that
q
^{3}
+
t
−
s
=
q
(
q
^{2}
+
t
_{1}
−
s
_{1}
)+
t
_{2}
−
s
_{2}
with
t
=
qt
_{1}
+
t
_{2}
. Therefore
q
^{3}
+
t
−
s
∉
S
if and only if
t
_{2}
−
s
_{2}
≥ 0,
q
^{2}
+
t
_{1}
−
s
_{1}
<
t
_{2}
−
s
_{2}
or
t
_{2}
−
s
_{2}
< 0,
q
^{2}
+
t
_{1}
−
s
_{1}
<
q
+ 1 +
t
_{2}
−
s
_{2}
. The first case is actually impossible since
s
_{1}
<
q
^{2}
. Hence
Thus
ν
(
s
) =
s
_{2}
max{
s
_{1}
−
s
_{2}
+
q
+ 1 −
q
^{2}
, 0} +
q
^{3}
−
s
for
s
=
qs
_{1}
+
s
_{2}
<
q
^{3}
. If
a
−
b
+
q
−
q
^{2}
≥ 0, then the minimum is attained at
s
=
aq
, and hence
d_{u}
=
q
^{3}
−
aq
while if
a
−
b
+
q
−
q
^{2}
< 0, then the minimum is attained at
s
=
u
, and hence
d_{u}
=
q
^{3}
−
u
.
Now we demonstrate the decoding algorithm, using the same example in
[4]
to facilitate a comparison with the previous algorithm. So we use the Hermitian curve
y
^{3}
+
y
−
x
^{4}
= 0 over
with
α
^{2}
−
α
− 1 = 0. There are 27 rational points on the affine part of the curve and a unique point
P
_{∞}
at infinity. As
δ
(
x
) = 3 and
δ
(
y
) = 4, the numerical semigroup of the coordinate ring
R
is
S
= 3ℕ + 4ℕ = {0, 3, 4, 6, 7, 8, 9, 10, . . . }. Note that
S
has three gaps 1, 2, and 5. The monomials of
R
correspond to nongaps in
S
and are displayed in the diagram
Let
u
= 16. Then the Hermitian code
C
_{16}
has dimension 14 and minimum distance 11, and the decoding algorithm can correct up to 5 errors. Suppose we received the vector
from a noisy channel. Let us follow the steps of the decoding algorithm.
The algorithm first compute the Lagrange interpolation of
v
,
The algorithm iterates the main steps for
s
from
N
=
δ
(
h_{v}
) = 32 to 0. The ideal
J
has Gröbner basis {
η
_{1}
=
x
^{9}
−
x
}. Hence the Gröbner basis of
is
Here the left diagram exhibits the monomials in
omitting the common
z
variable, while the right diagram shows the monomials in
The leading terms of the polynomials in the Gröbner basis are also shown.
For
s
≥
u
= 16 or a gap
s
, as
in the step
M1
, we will omit the tilde in the following. In the step
M2
, lm
_{31}
(
F
_{1}
) =
x
^{8}
y
^{2}
∈ Δ
_{32}
(
G
_{1}
) ∩
R
, and the lcms of lm
_{31}
(
F
_{1}
) =
x
^{8}
y
^{2}
and lm
_{32}
(
G
_{1}
) =
x
^{9}
are
x
^{9}
y
^{2}
and
x
^{12}
. Hence spoly(
F
_{1}
) = {
αxz
+
α
^{5}
x
^{8}
y
^{2}
+ · · · +
α
^{5}
x
^{2}
,
αyz
+
α
^{5}
x
^{11}
+ · · · +
α
^{2}
xy
}. Then the Gröbner basis of
is
As lm
_{s}
(
F
_{1}
), lm
_{s}
(
F
_{2}
) ∈
Rz
for
s
= 31, 30, there is no change in the Gröbner basis. So we get to the unaltered Gröbner basis of
Now since lm
_{29}
(
G
_{2}
) =
x
_{8}
y
_{2}
divides lm
_{28}
(
F
_{1}
) =
x
^{8}
y
^{2}
and lm
_{29}
(
G
_{1}
) =
x
^{9}
divides lm
_{28}
(
F
_{2}
) =
x
^{11}
, both lm
_{28}
(
F
_{1}
) and lm
_{28}
(
F
_{2}
) are in Σ
_{29}
(
G
_{1}
,
G
_{2}
) ∩
R
Thus
Hence the Gröbner basis of
is
Similar steps are iterated. Eventually, we get to the Gröbner basis of