Hermitian codes?

Hi,

Does anyone know of a good introduction to Hermitian codes?  I would
like to learn more about this class of codes, but I struggle to get
good information on it.  Any pointers to books, papers and websites
will be greatly appreciated. (I did search on Google, but I must have
searched for the wrong keywords...)

Kind regards,
Jaco Versfeld

One point Hermitian codes? A class of Algebraic Geometry Codes? I did
some reading on them a while ago. Check www.lrz-muenchen.de/~prasanna/
and see if the articles you find there on Algebraic Geometry Codes are
useful (better, check the references in them).

I did have some good papers on them, but don't remember their names
now. I will search my machine on any good references I might have. If I
can locate something I will let you know.

jaco.versfeld@gmail.com wrote:
> Hi,
> 
> Does anyone know of a good introduction to Hermitian codes?  I would
> like to learn more about this class of codes, but I struggle to get
> good information on it.  Any pointers to books, papers and websites
> will be greatly appreciated. (I did search on Google, but I must have
> searched for the wrong keywords...)
> 
> Kind regards,
> Jaco Versfeld
> 

The 50th anniversary commemorative issue of IEEE Transactions
on Information Theory has a nice semi-tutorial survey article
(by Blake et al) on Algebraic-Geometry codes. I warmly recommend
that (and references therein).

Tom H�holdt has also written a chapter (was it for the Handbook???)
titled "Algebraic-Geometry Codes without Algebraic Geometry", where
they base there approach to the Feng-Rao syndrome voting mechanism.
IOW their goal was to "prove" Riemann-Roch Theorem by demonstrating that
the decoding algorithm works.

During a project I once implemented K�tter's decoding algorithm
for Hermitian codes in ANSI C. You are welcome to have the source,
if you are desperate, but the documentation is kinda terse (should
I say it doesn't exist). Actually I used a suitably shortened (or
was it punctured?) version of the Hermitian codes so that I could
try my hand on "quasi-cyclic" encoding as suggested in an article
by Heegard et al (don't remember the exact title, it appeared in IT
in late 90s and had "Gr�bner Bases" as a buzzword). Therefore my
testbench encoding is non-systematic. I also made the shortcut
of solving for the error values by Gaussian elimination rather than
the more efficient DFT. I simply didn't have the time to learn the
theory to do that. You may want to ask Rasmus Nielsen for a better
documented implementation of (a slightly different version of)
Feng-Rao decoding algorithm.

Cheers,

Jyrki

Some good articles that came in searching through my computer:

S. J. Kim, "Introduction to Coding Theory and Algebraic Geometry
Codes", Proceedings of Workshops in Pure Mathematics. Vol. 18, part 1,
1988.

T. Hoholdt, J. H. van Lint, and R. Pellikaan, "Algebraic Geometry
Codes" in Handbook of Coding Theory.

Massimo Giulietti, "NOTES ON ALGEBRAIC-GEOMETRIC CODES", try Google.

Madhu Sudan, "Coding Theory: Tutorial & Survey", try Google.

Madhu Sudan, "Decoding of Reed Solomon Codes beyond the Error
Correcting Bound", try his website at MIT.

Stephanie Fitchett, "Bezouts Theorem: a taste of algebraic geometry",
try Google.

T. Hoholdt, R. Pellikaan, "On decoding of algebraic geometry codes", in
IEEE transactions on Info Theory.

"Efficient Decoding Methods in Goppa Codes based on Klein Curves" , try
Google.

And always keep a copy of Mc Williams and Sloane. :o)

Jyrki Lahtonen wrote:
> jaco.versfeld@gmail.com wrote:
> > Hi,
> >
> > Does anyone know of a good introduction to Hermitian codes?  I would
> > like to learn more about this class of codes, but I struggle to get
> > good information on it.  Any pointers to books, papers and websites
> > will be greatly appreciated. (I did search on Google, but I must have
> > searched for the wrong keywords...)
> >
> > Kind regards,
> > Jaco Versfeld
> >
>
> The 50th anniversary commemorative issue of IEEE Transactions
> on Information Theory has a nice semi-tutorial survey article
> (by Blake et al) on Algebraic-Geometry codes. I warmly recommend
> that (and references therein).

This is indeed an excellent article. But terse. I found it difficult to
start with this one.

> Tom H=F6holdt has also written a chapter (was it for the Handbook???)
> titled "Algebraic-Geometry Codes without Algebraic Geometry", where
> they base there approach to the Feng-Rao syndrome voting mechanism.
> IOW their goal was to "prove" Riemann-Roch Theorem by demonstrating that
> the decoding algorithm works.
>
> During a project I once implemented K=F6tter's decoding algorithm
> for Hermitian codes in ANSI C. You are welcome to have the source,
> if you are desperate, but the documentation is kinda terse (should
> I say it doesn't exist). Actually I used a suitably shortened (or
> was it punctured?) version of the Hermitian codes so that I could
> try my hand on "quasi-cyclic" encoding as suggested in an article
> by Heegard et al (don't remember the exact title, it appeared in IT
> in late 90s and had "Gr=F6bner Bases" as a buzzword). Therefore my
> testbench encoding is non-systematic. I also made the shortcut
> of solving for the error values by Gaussian elimination rather than
> the more efficient DFT. I simply didn't have the time to learn the
> theory to do that. You may want to ask Rasmus Nielsen for a better
> documented implementation of (a slightly different version of)
> Feng-Rao decoding algorithm.

Groebner bases... I gave up trying to understand that one after some
time. May be if you have time, can you please provide a brief overview
of what exactly Groebner bases are, and what they are for, Jyrki?

Regards,=20
Prasanna.

In article <1142438839.123466.92080@i40g2000cwc.googlegroups.com>,
 <prasan8181@gmail.com> wrote:

> Groebner bases... I gave up trying to understand that one after some
> time. May be if you have time, can you please provide a brief overview
> of what exactly Groebner bases are, and what they are for, Jyrki?

When you look at an (algebraic) curve or surface, you know it can
be defined by a set of polynomials which vanish there. For example,
the x-axis in  R^3  is the set of points where  y = z = 0.

But the defining set of polynomials is not unique. You could also
define the x-axis by the equations
   y+z = 0,  y-2z = 0
or even, more perversely, by the equations
   y+z = 0,  (y-2z)^2 = 0.

Mathematically the observation is that the set of all polynomials
which vanish on the x-axis (or any other curve or surface or whatever)
is an _ideal_ in the polynomial ring -- it includes not only the
few that you write down, but also any multiples of those (i.e., those
times any polynomial whatsoever) and any sums of _those_. All you
accomplish by writing down a few polynomials is to provide something
to get started with to describe the whole ideal. Those few form a
_basis_ for the ideal. The examples above just show that  {y, z}
and {y+z, y-2z}  are different bases for the same ideal.

(The other example is a little different -- those two polynomials form
a basis of a slightly smaller ideal but the two ideals have the same 
_radical_. That's a more complicated algebraic construction, but 
geometrically it just means they describe the same set of points.)

OK, well once you know that different bases exist for the same ideal,
then the question is, which bases are better for computational purposes?
One idea we can borrow from Gaussian elimination: it's better to have
an "upper-triangular" set of polynomials like  y+z = z^2 = 0 : the last
equation can be solved for  z,  then we plug into the next-to-last
and solve for  y, etc. Another idea we can borrow from the
Euclidean algorithm for finding the gcd's of two polynomials; if
your list of polynomials includes  x^3+x^2  and  x^2-2x, then in
order for both these polynomials to vanish, their gcd (which is just  x)
must also vanish.

This is what Groebner Bases do for you. They are just bases for ideals
in polynomial rings, but they are chosen to be somehow minimal in the
sense that those two principles have been applied to some terminal state.
There's a little bit of choice involved (which variables will be
considered "last" when you try Gaussian elimination?) so you see
references to "term order". But in practice they are just a means to
enable one to carry out commutative-algebra computations in these ideals.
Many of the more subtle concepts in commutative algebra can be 
made very concrete once ideals are represented with respect to
a Groebner basis.

They're very useful, but a tad over-rated. That is, they provide a
methodical and _often_ rapid way to do computations. But the method
is not _always_ fast, and it has a tendency to consume huge amounts
of computer memory in the process -- sometimes even when the final
answer itself is very compact. So people have been looking at
alternative ways to carry out some important computations like
counting points in 0-dimensional varieties. Research continues.

dave

Thanks Dave. That was a good introduction.

Dave Rusin wrote:
> In article <1142438839.123466.92080@i40g2000cwc.googlegroups.com>,
>  <prasan8181@gmail.com> wrote:
>
> > Groebner bases... I gave up trying to understand that one after some
> > time. May be if you have time, can you please provide a brief overview
> > of what exactly Groebner bases are, and what they are for, Jyrki?
>
> When you look at an (algebraic) curve or surface, you know it can
> be defined by a set of polynomials which vanish there. For example,
> the x-axis in  R^3  is the set of points where  y = z = 0.
>
> But the defining set of polynomials is not unique. You could also
> define the x-axis by the equations
>    y+z = 0,  y-2z = 0
> or even, more perversely, by the equations
>    y+z = 0,  (y-2z)^2 = 0.
>
> Mathematically the observation is that the set of all polynomials
> which vanish on the x-axis (or any other curve or surface or whatever)
> is an _ideal_ in the polynomial ring -- it includes not only the
> few that you write down, but also any multiples of those (i.e., those
> times any polynomial whatsoever) and any sums of _those_. All you
> accomplish by writing down a few polynomials is to provide something
> to get started with to describe the whole ideal. Those few form a
> _basis_ for the ideal. The examples above just show that  {y, z}
> and {y+z, y-2z}  are different bases for the same ideal.
>
> (The other example is a little different -- those two polynomials form
> a basis of a slightly smaller ideal but the two ideals have the same
> _radical_. That's a more complicated algebraic construction, but
> geometrically it just means they describe the same set of points.)
>
> OK, well once you know that different bases exist for the same ideal,
> then the question is, which bases are better for computational purposes?
> One idea we can borrow from Gaussian elimination: it's better to have
> an "upper-triangular" set of polynomials like  y+z = z^2 = 0 : the last
> equation can be solved for  z,  then we plug into the next-to-last
> and solve for  y, etc. Another idea we can borrow from the
> Euclidean algorithm for finding the gcd's of two polynomials; if
> your list of polynomials includes  x^3+x^2  and  x^2-2x, then in
> order for both these polynomials to vanish, their gcd (which is just  x)
> must also vanish.
>
> This is what Groebner Bases do for you. They are just bases for ideals
> in polynomial rings, but they are chosen to be somehow minimal in the
> sense that those two principles have been applied to some terminal state.
> There's a little bit of choice involved (which variables will be
> considered "last" when you try Gaussian elimination?) so you see
> references to "term order". But in practice they are just a means to
> enable one to carry out commutative-algebra computations in these ideals.
> Many of the more subtle concepts in commutative algebra can be
> made very concrete once ideals are represented with respect to
> a Groebner basis.
>
> They're very useful, but a tad over-rated. That is, they provide a
> methodical and _often_ rapid way to do computations. But the method
> is not _always_ fast, and it has a tendency to consume huge amounts
> of computer memory in the process -- sometimes even when the final
> answer itself is very compact. So people have been looking at
> alternative ways to carry out some important computations like
> counting points in 0-dimensional varieties. Research continues.
> 
> dave

Dave Rusin wrote:
[snipped introduction to Gr�bner bases]

> They're very useful, but a tad over-rated. That is, they provide a
> methodical and _often_ rapid way to do computations. But the method
> is not _always_ fast, and it has a tendency to consume huge amounts
> of computer memory in the process -- sometimes even when the final
> answer itself is very compact. So people have been looking at
> alternative ways to carry out some important computations like
> counting points in 0-dimensional varieties. Research continues.
> 
> dave
> 

Indeed. I agree with you that they are somewhat overrated.
It simply became a popular buzzword in coding theory circles
at one point. E.g. if I correctly understood the upshot of the
paper by Heegard et al (the one I referred to earlier in this thread),
they really only need basic structure theory of modules over
a SINGLE variable polynomial ring over a field.

The Gr�bner basis have their uses, though. Once I was working on
an algebraic decoding algorithm and was running out of things to
try. I then decided to attempt to find a useful criteria for
a quintic polynomial (unknown coefficients) to have 5 distinct
roots in GF(32). I ended up with this horrid looking system of
equations in 5 unknowns. I played around with them (using Mathematica
functions like PolynomialMod) and at the end of the day stumbled
upon a really nice condition that turned looked useful.
Except that I couldn't repeat the process to convince my coauthors!
Ok, since this was about a finite field, I could do (and did) a complete
computer check, but that's ugly. The coauthors suggested that I
should try Gr�bner basis techniques. Mathematica couldn't do it -
it ran for a few hours and then exited with an out of memory message
(my fault, should have foreseen the trouble it will have, because
its approach apparently was to run the algorithms in characteristic
zero, and only at the end reduce the result modulo 2). Another
colleague told me to try a program called MacCaulay (spelling?).
After I finally managed to feed in my equations (that version had
a relatively clumsy user interface) it computed the desired Gr�bner
basis in under two seconds - with my mystery condition on top of
the list! This was something my coauthors could easily reproduce
(they were using Maple)

Cheers,

Jyrki

jaco.versfeld@gmail.com wrote:
> Hi,
> 
> Does anyone know of a good introduction to Hermitian codes?  I would
> like to learn more about this class of codes, but I struggle to get
> good information on it.  Any pointers to books, papers and websites
> will be greatly appreciated. (I did search on Google, but I must have
> searched for the wrong keywords...)
> 
> Kind regards,
> Jaco Versfeld
> 
A quick-n-dirty intro to the Hermitian codes:

You know that the Reed-Solomon codes can be viewed as consisting
of vectors gotten by evaluating a single variable polynomial at
(often only at non-zero) elements of a finite field. The Hermitian
codes use the same idea except that we have polynomials in two
variables x and y. We don't evaluate them at all the points, but
only at those points (x,y) whose coordinates satisfy the equation

y^q+y=x^(q+1),            (*)

and here we assume that the chosen finite field is F=GF(q^2).
I also assume that q is a power of two (the most interesting case
for the applications). It is not difficult to show that for any
fixed x in F there are exactly q solutions y of (*) in the field F.
So altogether there are q^3 solutions (x,y) to the equation (*).

So we get a code of length q^3 with alpabet F of size q^2. Remember
that for RS codes the length of the code is always limited to
the size of the alphabet, so this gives us some elbow room.

To get a Reed-Solomon code of dimension k, you evaluate monomials
1, x, x^2,..., x^(k-1). Here we do the same thing: to get a basis
(or a generator matrix) for a Hermitian code we evaluate monomials
like 1, x, y, x^2, xy, y^2,...

There are a couple of catches. First observe that the equation (*)
tells us to avoid those monomials, where the exponent of y is
at least q. Evaluating a monomial y^q gives the same result
as evaluating the polynomial x^(q+1)+y, so in order to get
linearly independent rows to the generator matrix we only use
x^(q+1), but won't use y^q (or any higher degree monomials that
have y^q as a factor). The second catch is the way we sort the
monomials. In the case of a single variable it was natural and
efficient to use them in the order of increasing exponents. Here
we use a function called "pole-order" (the name comes from
algebraic geometry, let's not worry about that here). It turns
out that x has pole-order equal to q, and y has a pole order
equal to q+1. Then a monomial x^i*y^j naturally will have pole
order i*q+j*(q+1), and the pole order of a polynomial is the
maximum pole order of its terms (just like in the case of
single variable polynomials). So for example both sides of
the equation (*) have pole orders equal to q^2+q.

You may have guessed by now that we add monomials in the
order of increasing pole order. For the sake of having a definite
example, let's try the case where q=4, so F is the field of
16 elements and there are 64 solutions to (*), so we get
codes of length 64. Here the pole order of x is 4 and the
pole order of y is 5. The monomials in the list

1,x,y,x^2,xy,y^2,x^3,x^2*y,x*y^2,y^3,...

then have pole orders 0,4,5,8,9,10,12,13,14,15,...
[You may have noticed that the numbers 1,2,3,6,7 and 11 are
missing from this list. These are the so called 'gaps', but
let's not worry about them yet. They are a necessary evil
and will hurt the code in the way of minimum distance. But
without gaps we are stuck with the short RS-codes, so it's
a price worth paying in some applications! You decide, whether
yours is in that category.]

Ok, so to get for example a 5-dimensional Hermitian code
you evaluate the monomials 1,x,y,x^2 and xy at all the
64 points (x,y) of the Hermitian curve (*). How do we compute
the minimum distance of this code? Recall that you get the
minimum distance of an RS code as follows. When we use a
k-dimensional code of length n, we use polynomials of degree
k-1. These have at most k-1 zeros, so any codeword has
at least n-(k-1)=n-k+1 non-zero components. IOW the minimum
distance of the code is at least n-k+1. Here a very similar
argument works, once we have shown that the pole order of a
polynomial gives an upper bound to its number of zeros ON
THE CURVE (*). So if we return to the 5-dimensional code
above, we see that the highest pole order we use there is
equal to 9, which is the pole order of x*y. So any polynomial
of pole order 9 has at most 9 zeros among the 64 points,
and the minimum distance of our code is therefore at least
64-9=55. By adding monomials from the list we get

1) a 6-dimensional code with minimum distance
64 - pole order of y^2 =64-10=54,
2) a 7-dimensional code with minimum distance
64 - pole order of x^3 = 64-12=52,
etc.

Observe that unlike in the case of RS-codes the minimum distance 
sometimes goes down by more than one, when you increase the
dimension by one. This is due to the gaps and cannot be
helped. The maximum price you pay in the minimum distance is
the total number of gaps that is also called the genus (denoted
'g' universally). In this example case the genus was 6, as I listed all 
the gaps, and for large enough codes the parameters n=length,
k=dimension, and d=minimum distance satisfy the equation

n+1=k+d+g

instead of the Singleton bound

n+1=k+d

that holds for the RS-codes (IOW the single variable polynomials
have no gaps). The trouble with RS-codes is that they are shorter.

This is a crude beginning, but hopefully will give you an idea,
whether the hermitian codes might be useful in your application.

Cheers,

Jyrki

Jyrki Lahtonen wrote:
> jaco.versfeld@gmail.com wrote:
> > Hi,
> >
> > Does anyone know of a good introduction to Hermitian codes?  I would
> > like to learn more about this class of codes, but I struggle to get
> > good information on it.  Any pointers to books, papers and websites
> > will be greatly appreciated. (I did search on Google, but I must have
> > searched for the wrong keywords...)
> >
> > Kind regards,
> > Jaco Versfeld
> >
> A quick-n-dirty intro to the Hermitian codes:
>
> You know that the Reed-Solomon codes can be viewed as consisting
> of vectors gotten by evaluating a single variable polynomial at
> (often only at non-zero) elements of a finite field. The Hermitian
> codes use the same idea except that we have polynomials in two
> variables x and y. We don't evaluate them at all the points, but
> only at those points (x,y) whose coordinates satisfy the equation
>
> y^q+y=x^(q+1),            (*)
>
> and here we assume that the chosen finite field is F=GF(q^2).
> I also assume that q is a power of two (the most interesting case
> for the applications). It is not difficult to show that for any
> fixed x in F there are exactly q solutions y of (*) in the field F.
> So altogether there are q^3 solutions (x,y) to the equation (*).

Is there any specific reason behing choosing the composite field
GF(2^2m) instead of GF(2^p)?

> So we get a code of length q^3 with alpabet F of size q^2. Remember
> that for RS codes the length of the code is always limited to
> the size of the alphabet, so this gives us some elbow room.
>
> To get a Reed-Solomon code of dimension k, you evaluate monomials
> 1, x, x^2,..., x^(k-1). Here we do the same thing: to get a basis
> (or a generator matrix) for a Hermitian code we evaluate monomials
> like 1, x, y, x^2, xy, y^2,...
>
> There are a couple of catches. First observe that the equation (*)
> tells us to avoid those monomials, where the exponent of y is
> at least q. Evaluating a monomial y^q gives the same result
> as evaluating the polynomial x^(q+1)+y, so in order to get
> linearly independent rows to the generator matrix we only use
> x^(q+1), but won't use y^q (or any higher degree monomials that
> have y^q as a factor). The second catch is the way we sort the
> monomials. In the case of a single variable it was natural and
> efficient to use them in the order of increasing exponents. Here
> we use a function called "pole-order" (the name comes from
> algebraic geometry, let's not worry about that here). It turns
> out that x has pole-order equal to q, and y has a pole order
> equal to q+1. Then a monomial x^i*y^j naturally will have pole
> order i*q+j*(q+1), and the pole order of a polynomial is the
> maximum pole order of its terms (just like in the case of
> single variable polynomials). So for example both sides of
> the equation (*) have pole orders equal to q^2+q.

This pole order actually comes from rational points on the curves and
divisors, right? If possible, can you also give an example that
connects these with the pole order?

> You may have guessed by now that we add monomials in the
> order of increasing pole order. For the sake of having a definite
> example, let's try the case where q=4, so F is the field of
> 16 elements and there are 64 solutions to (*), so we get
> codes of length 64. Here the pole order of x is 4 and the
> pole order of y is 5. The monomials in the list
>
> 1,x,y,x^2,xy,y^2,x^3,x^2*y,x*y^2,y^3,...
>
> then have pole orders 0,4,5,8,9,10,12,13,14,15,...
> [You may have noticed that the numbers 1,2,3,6,7 and 11 are
> missing from this list. These are the so called 'gaps', but
> let's not worry about them yet. They are a necessary evil
> and will hurt the code in the way of minimum distance. But
> without gaps we are stuck with the short RS-codes, so it's
> a price worth paying in some applications! You decide, whether
> yours is in that category.]
>
> Ok, so to get for example a 5-dimensional Hermitian code
> you evaluate the monomials 1,x,y,x^2 and xy at all the
> 64 points (x,y) of the Hermitian curve (*). How do we compute
> the minimum distance of this code? Recall that you get the
> minimum distance of an RS code as follows. When we use a
> k-dimensional code of length n, we use polynomials of degree
> k-1. These have at most k-1 zeros, so any codeword has
> at least n-(k-1)=n-k+1 non-zero components. IOW the minimum
> distance of the code is at least n-k+1. Here a very similar
> argument works, once we have shown that the pole order of a
> polynomial gives an upper bound to its number of zeros ON
> THE CURVE (*). So if we return to the 5-dimensional code

How can I connect this with Bezout's theorem? Atleast for simple cases,
we can use Bezout's theorem to determine the minimum distance of the
code, right? Like in the case of the five dimensional code here, the
message polynomials are of degree atmost 2, and the Hermitian curve is
of degree 5, so the two curves can intersect at atmost 10 points. With
a code length of 64, any codeword can only have 10 zero elements => has
54 non-zero elements. The minimum distance is 54...

> above, we see that the highest pole order we use there is
> equal to 9, which is the pole order of x*y. So any polynomial
> of pole order 9 has at most 9 zeros among the 64 points,
> and the minimum distance of our code is therefore at least
> 64-9=55. By adding monomials from the list we get

I got 54. Close. :o)

> 1) a 6-dimensional code with minimum distance
> 64 - pole order of y^2 =64-10=54,
> 2) a 7-dimensional code with minimum distance
> 64 - pole order of x^3 = 64-12=52,
> etc.
>
> Observe that unlike in the case of RS-codes the minimum distance
> sometimes goes down by more than one, when you increase the
> dimension by one. This is due to the gaps and cannot be
> helped. The maximum price you pay in the minimum distance is
> the total number of gaps that is also called the genus (denoted
> 'g' universally). In this example case the genus was 6, as I listed all
> the gaps, and for large enough codes the parameters n=length,
> k=dimension, and d=minimum distance satisfy the equation

How can I visualize this genus? It should translate into the number of
holes in a surface, right? Now, given the curve, and taking my base
field as complex numbers, how can I plot this curve in a tool like
Mathematica so that I can look at how many zeros it has?

> n+1=k+d+g
>
> instead of the Singleton bound
>
> n+1=k+d
>
> that holds for the RS-codes (IOW the single variable polynomials
> have no gaps). The trouble with RS-codes is that they are shorter.
>
> This is a crude beginning, but hopefully will give you an idea,
> whether the hermitian codes might be useful in your application.

Thanks a lot for the highly readable intro!

Regards, 
Prasanna.

> Cheers,
> 
> Jyrki