Advanced
UNIQUE DECODING OF PLANE AG CODES REVISITED†
UNIQUE DECODING OF PLANE AG CODES REVISITED†
Journal of Applied Mathematics & Informatics. 2014. Jan, 32(1_2): 83-98
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : April 30, 2013
  • Accepted : November 02, 2013
  • Published : January 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
KWANKYU LEE

Abstract
We reformulate an interpolation-based 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 interpolation-based unique decoding. Moreover the smaller Gröbner bases imply smaller space and time complexity of the algorithm. AMS Mathematics Subject Classification: 94B35, 94B27.
Keywords
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 interpolation-based 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 well-known classical unique decoders of AG codes, Berlekamp-Massey-Sakata algorithm [7] and Kötter’s algorithm [3] , the features of the new algorithm put it in a unique place in the following table.
PPT Slide
Lager Image
That is, the new algorithm corrects the evaluation code C on a plane curve X working with the Gröbner bases on
PPT Slide
Lager Image
[ 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 Miura-Kamiya curves [5] , which include Hermitian curves as prominent special cases. A Miura-Kamiya curve X is an irreducible plane curve defined by the equation
PPT Slide
Lager Image
over a field
PPT Slide
Lager Image
with gcd( a , b ) = 1 and 0 ≠ d
PPT Slide
Lager Image
. It is well known that X has a unique point P at infinity and has a unique valuation
PPT Slide
Lager Image
associated with it. Let
PPT Slide
Lager Image
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 =
PPT Slide
Lager Image
[ x , y ] =
PPT Slide
Lager Image
[ X , Y ]/⟨ E ⟩ can be written as a unique
PPT Slide
Lager Image
-linear combination of the monomials xiyj with i ≥ 0 and 0 ≤ j < a , which we call monomials of R . The numerical semigroup of R at P ,
PPT Slide
Lager Image
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 one-to-one correspondence with nongaps in S . For a nongap s , let φs denote the unique monomial with δ ( φs ) = s .
Let P 1 , P 2 , . . . , Pn be nonsingular rational points of X . The evaluation map ev from R to the Hamming space
PPT Slide
Lager Image
is the
PPT Slide
Lager Image
-linear map defined by φ ↦ ( φ ( P 1 ), φ ( P 2 ), . . . , φ ( Pn )). Let u be a fixed positive integer less than n and define Lu = { f R | δ ( f ) ≤ u } = ⟨ φs | s S , s u ⟩, where brackets denote the linear span over
PPT Slide
Lager Image
. Then the AG code Cu is defined as the image of Lu under ev. As u < n , ev is one-to-one on Lu . So the dimension of the linear code Cu equals
PPT Slide
Lager Image
Lu = |{ 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 interpolation-based 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 Cu is sent through a noisy communication channel and v
PPT Slide
Lager Image
is the vector received from the channel. Let v = c + e with the error vector e . Then c = ev( μ ) for a unique
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and for gap s u , let v (s−1) = v (s) , c (s−1) = c (s) , and μ (s−1) = μ (s) . Note that
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and can be evaluated at a point ( P , α ) with P X , α
PPT Slide
Lager Image
. Hence we can define the interpolation module
PPT Slide
Lager Image
for v and similarly for v (s) . These interpolation modules are indeed modules over R , and finite-dimensional vector space over
PPT Slide
Lager Image
. Note that
PPT Slide
Lager Image
where J = ∩ 1≤in m i and ev( hv ) = v , and m i = ⟨ x αi , y βi ⟩ is the maximal ideal of R associated with Pi = ( αi , βi ). Recall that by Lagrange interpolation, hv can be computed fast from v . We will see that the key to find ωs is the Gröbner basis of
PPT Slide
Lager Image
with respect to a monomial order > s , defined as follows.
Let s be an integer. For monomial xiyjzk R [ z ], let δs ( xiyjzk ) = δ ( xiyj ) + sk . In particular, δs ( xiyjz ) = ai + bj + s and δs ( xiyj ) = δ ( xiyj ) = 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 fU and fD R such that f = fUz + fD (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 = fUz + fD with fU , fD R . Then lm s ( f ) ∈ Rz δ ( fU ) + s δ ( fD ), 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
PPT Slide
Lager Image
where
PPT Slide
Lager Image
are some index sets, with the understanding that each Gi is a basis element such that lm s ( Gi ) ∈ R and each Fj is a basis element such that lm s ( Fj ) ∈ 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( fU ) z , and if lm s ( f ) ∈ R , then lm s ( f ) = lm( fD ). It is easy to see by the definition of Gröbner bases that
PPT Slide
Lager Image
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
PPT Slide
Lager Image
with respect to >, and
PPT Slide
Lager Image
since J is the ideal associated with the sum of n rational points on X . By (2), we see that
PPT Slide
Lager Image
( Rz R / Iv ) =
PPT Slide
Lager Image
( R / J ) = n . Let N = δ ( hv ). The set
PPT Slide
Lager Image
is then a Gröbner basis of Iv with respect to > N . Let us denote a Gröbner basis of
PPT Slide
Lager Image
with respect to > s by
PPT Slide
Lager Image
Observe that if s is a nongap ≤ u , then the set
PPT Slide
Lager Image
is still a Gröbner basis of
PPT Slide
Lager Image
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
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
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 λ = φ ts . 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
and
PPT Slide
Lager Image
the lcms of φs and φt . In the case when φs divides φt , we will call φt the lcm of φs and φt .
Let
PPT Slide
Lager Image
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 ( Gi ) = lm s ( Gi ) ∈ R for all
PPT Slide
Lager Image
, we may have either lm s−1 ( Fj ) = lm s ( Fj ) ∈ Rz or lm s−1 ( Fj ) ∈ R depending on
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
such that lm s−1 ( Fj ) = lm s ( Fj ) ∈ Rz , define spoly( Fj ) = { Fj }. If lm s−1 ( Fj ) ∈ R ∩Σ s , then there is an
PPT Slide
Lager Image
such that lm s ( Gi )|lm s−1 ( Fj ), and then, with one such i , define
PPT Slide
Lager Image
Finally, if lm s−1 ( Fj ) ∈ R ∩ Δ s , then define
PPT Slide
Lager Image
which is generally not a singleton set unlike the previous two cases.
Proposition 3.2. For every f ∈ spoly( Fj ), lm s−1 ( f ) is in Rz .
Proof. Recall that lm s ( Fj ) ∈ Rz . Suppose lm s−1 ( Fj ) ∈ R , and let ψ be an lcm of lm s−1 ( Fj ) and lm s ( Gi ) for any
PPT Slide
Lager Image
. Then by Lemma 2.1,
PPT Slide
Lager Image
Therefore
PPT Slide
Lager Image
On the other hand,
PPT Slide
Lager Image
As the monic terms cancel each other,
PPT Slide
Lager Image
Therefore
PPT Slide
Lager Image
and hence by Lemma 2.1,
PPT Slide
Lager Image
For the case when lm s−1 ( Fj ) ∈ R ∩ Σ s , notice that lm s−1 ( Fj ) is the lcm.
Proposition 3.3. A monomial φ is in R ∩ Σ s−1 if and only if there exists an
PPT Slide
Lager Image
such that lm s−1 ( Gi )| φ or there exists a
PPT Slide
Lager Image
such that lm s−1 ( Fj ) ∈ R ∩Δ s and lm s−1 ( Fj )| φ .
Proof. Both lm s−1 ( Gi )| φ and lm s−1 ( Fj )| φ imply φ R ∩ Σ s−1 . Let us show the converse. If φ R ∩ Σ s , then lm s ( Gi )| φ for some
PPT Slide
Lager Image
, and therefore lm s−1 ( Gi )| φ . 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, δ ( fU )+ s = δ ( fD ) = δ ( φ ). Then lm s ( Fj )|lm s ( f ) for
PPT Slide
Lager Image
. As lm s ( Fj ) ∈ Rz , we have
PPT Slide
Lager Image
where actually equality holds as we will show now. Assume the contrary, that is,
PPT Slide
Lager Image
Then
PPT Slide
Lager Image
These imply
PPT Slide
Lager Image
contradictory to the assumption φ R ∩ Σ s . Hence
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Therefore lm s−1 ( Fj )| φ , and lm s−1 ( Fj ) ∈ R ∩ Δ s .
roposition 3.4. A monomial φ is in Rz ∩ Σ s−1 if and only if there exists a
PPT Slide
Lager Image
such that lm s−1 ( f )| φ for some f ∈ spoly( Fj ).
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
PPT Slide
Lager Image
such that lm s ( Fj )| φ . If lm s−1 ( Fj ) ∈ Rz , then Fj ∈ spoly( Fj ) and lm s−1 ( Fj ) = lm s ( Fj )| φ .
Suppose lm s−1 ( Fj ) ∈ R ∩Σ s . Then there is an
PPT Slide
Lager Image
such that lm s ( Gi )|lm s−1 ( Fj ) and
PPT Slide
Lager Image
and by (3),
PPT Slide
Lager Image
Suppose lm s−1 ( Fj ) ∈ R ∩Δ s . Note that δ ( fU )+ s > δ ( fD ),
PPT Slide
Lager Image
and hence
PPT Slide
Lager Image
Thus we see that
PPT Slide
Lager Image
and hence there is an
PPT Slide
Lager Image
such that
PPT Slide
Lager Image
Now there is an lcm ψ of lm s−1 ( Fj ) and lm s ( Gi ) such that
PPT Slide
Lager Image
and
PPT Slide
Lager Image
By (3),
PPT Slide
Lager Image
and finally from (4),
PPT Slide
Lager Image
Combining the above results, we obtain
Theorem 3.5. Suppose that
PPT Slide
Lager Image
is a Gröbner basis of M with respect to > s . Then
PPT Slide
Lager Image
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
PPT Slide
Lager Image
4. Message Selection
The ideal of the error vector e defined by
PPT Slide
Lager Image
has a Gröbner basis { ϵi | i Ɛ } with respect to >, and
PPT Slide
Lager Image
Recall that
PPT Slide
Lager Image
is a Gröbner basis of
PPT Slide
Lager Image
with respect to > s . Observe that
PPT Slide
Lager Image
which results in
PPT Slide
Lager Image
and hence
PPT Slide
Lager Image
Therefore
PPT Slide
Lager Image
Now let s be a nongap ≤ u . Let us consider the module
PPT Slide
Lager Image
for w
PPT Slide
Lager Image
. Note that
PPT Slide
Lager Image
is a Gröbner basis of
PPT Slide
Lager Image
with respect to > s since lm s ( f ( z + s )) = lm s ( f ) for all
PPT Slide
Lager Image
. For the same reason,
PPT Slide
Lager Image
Observe that
PPT Slide
Lager Image
Hence
PPT Slide
Lager Image
In Theorem 4.3 below, we will characterize ωs as such a w that makes the value
PPT Slide
Lager Image
smallest, provided that wt( e ) is not too large. Recall that
PPT Slide
Lager Image
in the following arguments.
Lemma 4.1. For
PPT Slide
Lager Image
Proof. Observe that
PPT Slide
Lager Image
Therefore
PPT Slide
Lager Image
Hence
PPT Slide
Lager Image
equivalent to the second equality.
Lemma 4.2. |Δ( Jeφs )| = wt( e ) + s .
Proof. Note that
PPT Slide
Lager Image
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
PPT Slide
Lager Image
is smallest for w = ωs , provided that |Δ( J ) ∪ Δ( s )| − s > 2wt( e ).
Proof. We need to show that for
PPT Slide
Lager Image
By (7) and the previous lemmas, a sufficient condition for the above is
PPT Slide
Lager Image
since |Δ( J )| = n . Finally note that |Δ( J ) ∪ Δ( Jeφs )| ≥ |Δ( J ) ∪ Δ( s )|.
  • Note thatis smallest when so is
PPT Slide
Lager Image
since
PPT Slide
Lager Image
is independent of w . The value
PPT Slide
Lager Image
can be computed using the Gröbner bases of
PPT Slide
Lager Image
with respect to > s and > s−1 . As we saw in Section 3, the Gröbner basis of
PPT Slide
Lager Image
with respect to > s−1 is determined from
PPT Slide
Lager Image
the Gröbner bases of
PPT Slide
Lager Image
with respect to > s . Precisely, according to Proposition 3.3, the set
PPT Slide
Lager Image
is determined by the monomials
PPT Slide
Lager Image
that lies in
PPT Slide
Lager Image
We note that for each
PPT Slide
Lager Image
there is a unique wj
PPT Slide
Lager Image
such that lm s−1 ( Fj ( z + wjφs )) ∈ Rz , and
PPT Slide
Lager Image
if and only if w wj . In fact,
PPT Slide
Lager Image
where d is the coefficient of the monomial
PPT Slide
Lager Image
Proposition 4.4. Let denote disjoint union . We have
PPT Slide
Lager Image
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
PPT Slide
Lager Image
with c 1 c 2 , there is a monomial φ R such that φ is in the intersection of
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
and monomials ψ , χ. Then we will show that
PPT Slide
Lager Image
contradicting the assumption that
PPT Slide
Lager Image
Indeed notice that
PPT Slide
Lager Image
Hence the coefficient of the monomial φ in the first term of the polynomial in (8) is
PPT Slide
Lager Image
where d 1 is the coefficient of the monomial
PPT Slide
Lager Image
In the same way, the coefficient of the monomial φ in the second term after the minus in (8) is
PPT Slide
Lager Image
where d 2 is the coefficient of the monomial
PPT Slide
Lager Image
These two coefficients are different because we assumed
PPT Slide
Lager Image
Hence (8) follows.
We observe that for c , w
PPT Slide
Lager Image
with w c ,
PPT Slide
Lager Image
Therefore this set is independent of w , and is determined by B (s) . Let
PPT Slide
Lager Image
Then Proposition 4.4 implies
PPT Slide
Lager Image
is smallest when w = c with dc 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
PPT Slide
Lager Image
Theorem 4.5. The algorithm outputs w (s) = ωs for all s S , s u if
PPT Slide
Lager Image
where ν ( s ) = |Δ( J ) ∪ Δ( s )| − s for s S . Moreover du n u .
Proof. By Theorem 4.3, the condition du > 2wt( e ) implies that the algorithm computes w (s) = ωs for each iteration for nongap s from u to 0. To see du n u , notice that |Δ( J ) ∪ Δ( s )| ≥ |Δ( J )| = n .
5. Decoding Hermitian Codes
Let us consider the Hermitian code Cu defined on the Hermitian curves with equation Yq + Y X q+1 = 0 over
PPT Slide
Lager Image
There are q 3 rational points on the Hermitian curve, and
PPT Slide
Lager Image
In Theorem 5.1, we determine the performance of the decoding algorithm for Cu . 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 du = q 3 aq if b a + q q 2 and du = q 3 u if b > a + q q 2 .
Proof. We first compute ν ( s ) for nongap s = qs 1 + s 2 < q 3 . As
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 du = q 3 aq while if a b + q q 2 < 0, then the minimum is attained at s = u , and hence du = 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
from a noisy channel. Let us follow the steps of the decoding algorithm.
The algorithm first compute the Lagrange interpolation of v ,
PPT Slide
Lager Image
The algorithm iterates the main steps for s from N = δ ( hv ) = 32 to 0. The ideal J has Gröbner basis { η 1 = x 9 x }. Hence the Gröbner basis of
PPT Slide
Lager Image
is
PPT Slide
Lager Image
PPT Slide
Lager Image
Here the left diagram exhibits the monomials in
PPT Slide
Lager Image
omitting the common z variable, while the right diagram shows the monomials in
PPT Slide
Lager Image
The leading terms of the polynomials in the Gröbner basis are also shown.
For s u = 16 or a gap s , as
PPT Slide
Lager Image
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
PPT Slide
Lager Image
is
PPT Slide
Lager Image
PPT Slide
Lager Image
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
PPT Slide
Lager Image
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Hence the Gröbner basis of
PPT Slide
Lager Image
is
PPT Slide
Lager Image
Similar steps are iterated. Eventually, we get to the Gröbner basis of
PPT Slide
Lager Image