%
%  Paper from Linz ``D1'' workshop, May 2006
%
\documentclass[12pt]{article}

\def\bFq{{\mathbb F}_q}
\def\P{{\mathbb P}}
\def\X{{\cal X}}
\newtheorem{prop}{Proposition}
\newtheorem{theo}{Theorem}
\newtheorem{lemma}{Lemma}
\usepackage{amssymb,epsfig,amscd}
\begin{document}
\title{Automorphisms and Encoding of AG and Order Domain Codes}
\author{John B. Little\\
Department of Mathematics and Computer Science\\
College of the Holy Cross\\
Worcester, MA 01610 USA\\ 
{\tt little@mathcs.holycross.edu}}
\maketitle

\begin{abstract}
If a linear code $C$ over $\bFq$ has a finite abelian group 
$H$ as a group of automorphisms, then $C$ has 
the structure of a module over a polynomial ring ${\cal P}$.  
This structure can be used to develop systematic encoding algorithms using Gr\"obner 
bases for modules.  We illustrate these observations with several 
examples including geometric Goppa codes and codes from order domains.
\end{abstract}

\section{Introduction}
\label{review}

In order for a code to be useful in practice, it should admit efficient encoding and 
efficient decoding.  Although most of the research effort
on algebraic geometric (AG) Goppa codes from curves has focused on the decoding
side, several approaches have been considered for encoding as well.

In this article we will concentrate on a systematic
encoding method based on the fact that codes possessing permutation 
automorphisms have the structure of modules over polynomial rings.
We will follow Heegard, Little, and Saints, \cite{kn:HLS}, which shows
how to use module Gr\"obner bases for such codes to construct encoders.   This 
approach is a direct generalization of the 
commonly-used polynomial division encoding method for cyclic codes 
that appears in most textbook treatments of coding theory.  
The role of the module Gr\"obner basis here is that it furnishes an 
analog of the generator polynomial of a cyclic code (see 
Theorem~\ref{encoding}).  This particular connection between encoding 
and Gr\"obner bases was well-established previously in the case of 
abelian ($m$-dimensional cyclic) codes.  See, for instance, \cite{kn:PH}, 
section 6.1.6, or Chapter 9 of \cite{kn:CLO}.  Since it relies only on 
the presence of suitable groups of code automorphisms, 
it applies to many classes of codes, including cyclic, quasi-cyclic,
abelian, and many Goppa-type evaluation codes from curves,
higher-dimensional varieties, and order domains.  In the last three
cases, interesting code automorphisms often arise from automorphisms
of the underlying algebraic variety (see \S\ref{AG}).  
Some results on implementation of this approach in hardware for the case of 
codes from the Hermitian curves considered in \S \ref{ex} 
have been reported by Chen and Lu, \cite{kn:CL}.  

More recent work on encoding methods for AG Goppa codes
includes Matsumoto, Oishi, and Sakaniwa, \cite{kn:MOS}.  This article proposes
a fast non-systematic encoding method for the one-point residue codes 
$C_\Omega(D,mQ)$ based on the structure of a special basis for the vector space
of differentials $\Omega(mQ - D)$.  In addition, Matsui and Mita, 
\cite{kn:MM}, have described a method combining discrete Fourier 
transforms and Gr\"obner bases for the ideal of polynomials with a given
collection of zeroes that yields a systematic encoder
for $C_\Omega(D,mQ)$ codes from any $C_{a,b}$ curve,
considered as the duals of the one-point evaluation 
codes $C_L(D,mQ)$. 

To conclude this introduction, we note that codes with sufficiently 
large automorphism groups may also be amenable to {\it permutation decoding}.
In this decoding method, a fixed collection of code automorphisms is 
applied to the received word.  If the error weight is sufficiently 
small, at least one of the automorphisms will move the errors
out of the information positions.  Then the correct information
symbols can be re-encoded
to accomplish the decoding.  Chabanne, \cite{kn:C}, has considered
this decoding method from the point of view of Gr\"obner bases
in the case of abelian codes, and [L1] gives an example for a 
Hermitian code.

\section{Automorphisms and module structures}
\label{modstruct}

The symmetric group $S_n$ acts on $\bFq^n$ by permuting the
entries of vectors.   A permutation {\it automorphism} of a linear 
code $C \subset \bFq^n$ is an element of $S_n$ that maps the set 
of codewords to itself.  We will only consider code automorphisms 
of this type in the following.

Let $C$ be a code that has a nontrivial
abelian group $H$ of automorphisms.  For instance, the ordinary 
cyclic codes and $m$-dimensional cyclic codes (also known as abelian 
codes) are well-studied examples.
For simplicity of notation, we will usually restrict 
to the case that $H = \langle \sigma\rangle$ is cyclic.  The generalization 
to the product of several cyclic groups is essentially immediate.  
With the restriction to cyclic groups $H$, cyclic codes are the most 
basic examples.  But note that we do not assume that $H$ acts transitively 
on the set of codeword components.  Hence, for instance, the 
{\it quasicyclic} codes of length $n$ also have this sort of structure
(by definition, $C$ is quasicyclic if its automorphism group contains an 
$m$-fold cyclic shift for some $m$ dividing $n$) .  

Let $O_i$, $i = 1, \ldots, r$  be the {\it orbits} of the 
components of the codewords $c$ under the action of $H$.  Pick any 
component $c_{i,0}$ in the $i$th orbit and label the components in 
that orbit as $c_{i,j}$ where $j = 0,\ldots, |O_i| - 1$.  With 
the convention that the second index is an integer modulo
$|O_i|$, the action of $\sigma$ can be written as
$\sigma(c_{i,j}) = c_{i,j+1}$ for all $i = 1, \ldots, r$, and
$j = 0, \ldots, |O_i| - 1$.

For the remainder of this chapter, ${\cal P}$ will denote
the polynomial ring in one variable $\bFq[t]$.
As usual, let ${\bf e}_i$ be the $i$th standard basis vector in 
the free module ${\cal P}^r$.  Then the orbit structure of the components of 
the codewords of $C$ determines the submodule 
$\langle (t^{|O_i|} - 1){\bf e}_i : i = 1, \ldots, r \rangle$
of ${\cal P}^r$.  We can view the code $C$ as subset of the
quotient module
\begin{equation}
\label{quot}
N = {\cal P}^r/\langle (t^{|O_i|} - 1){\bf e}_i : i = 1,\ldots,r \rangle,
\end{equation}
via the mapping 
\begin{eqnarray*}
\phi: C &\to& N\\
(c_{i,j}) &\mapsto& \sum_{i=1}^r\left(\sum_{j=0}^{|O_i|-1} c_{i,j} t^j\right){\bf e}_i
\bmod \langle (t^{|O_i|} - 1){\bf e}_i : i = 1,\ldots,r \rangle.
\end{eqnarray*}

We have the following theorem describing the structure of the 
image $\phi(C)$.  

\begin{theo} 
\label{autmod}
Let $C$ linear block code over $\bFq$ with a 
cyclic group $H$ of automorphisms and $\phi, N$ be as above.  
Then $\phi(C)$ has the structure of a ${\cal P}$-submodule of $N$.
\end{theo}

\noindent
{\it Proof:}  First $\phi$ is linear, so $\phi(C)$ is an $\bFq$-vector 
subspace of $N$.  By the definition of $\phi$, if $c \in C$ is any codeword,
multiplication of $\phi(c)$ by $t$ yields 
\begin{eqnarray*}
t\cdot \phi(c) & = & 
\sum_{i=1}^r\left(\sum_{j=0}^{|O_i|-1} c_{i,j} t^{j+1}\right){\bf e}_i \\
               & & \\
              & \equiv & 
\sum_{i=1}^r\left(\sum_{j=0}^{|O_i|-1} c_{i,j-1} t^j\right){\bf e}_i 
                  \bmod N\\
               & & \\
               & = & \phi(\sigma^{-1}(c)).
\end{eqnarray*}
By hypothesis, this is another element of $\phi(C)$.  Hence $\phi(C)$
is closed under multiplication by $t$, hence under multiplication by
all polynomials in ${\cal P}$.  It follows that $\phi(C)$ is a ${\cal P}$-submodule of $N$. $\Box$

\bigskip
Note that if the theorem applies to a code $C$, 
it applies to the dual code $C^\perp$ as well.  

In \cite{kn:HLS}, \cite{kn:LSH}, and \cite{kn:L1},
this essentially straightforward generalization
of the usual construction showing that a cyclic code of length $n$
over $\bFq$ is an ideal in ${\cal P}/\langle t^n - 1\rangle$ was 
applied to some AG Goppa codes.  We will 
present several explicit examples in \S \ref{ex}. 
The article \cite{kn:LF} applies the module structures described 
here to study quasicyclic codes.    Theorem \ref{autmod}
can also be generalized to more general finite
abelian automorphism groups.  In those cases, we obtain module 
structures over the polynomial ring in $s$ variables if a minimal generating
set for $H$ has $s$ elements. 

\section{A systematic encoding algorithm}
\label{sysenc}

We will now show how the theory of Gr\"obner bases for
modules can be applied to work with these codes.  
Let ${\sf M}(C)$ be the submodule of ${\cal P}^r$ corresponding to $\phi(C) \subset N$
under the mapping 
$$\pi: {\cal P}^r \to N,$$
where $N$ is the quotient module from (\ref{quot}). 
The key observation here is that the canonical form algorithm 
with respect to a Gr\"obner basis 
$G$ for ${\sf M}(C)$ with respect to any term ordering $\prec$ on ${\cal P}^r$
can be used to produce a systematic encoder for $C$.  

One potential advantage of exploiting the module structures 
described in Theorem \ref{autmod} is that, as is true for the generator
polynomial of a cyclic code, a Gr\"obner basis for ${\sf M}(C)$
is typically much smaller than a full systematic
generator matrix.  Moreover, the encoding algorithm can be described succinctly 
using the standard and nonstandard terms for ${\sf M}(C)$.
In what follows, the terms $t^j {\bf e}_i$ in the {\it Gr\"obner \'escalier}
${\bf N}_\prec({\sf M}(C))$ will be called the {\it standard terms}.
The {\it nonstandard terms} are the $t^j {\bf e}_i$ with $j \le |O_i| - 1$ 
contained in the monomial module ${\bf T}_\prec({\sf M}(C))$.

In this method, the coefficients of the nonstandard terms give the information 
positions in the codewords, and the coefficients of the standard terms
are the parity checks.  The precise statement of the encoding method
is given in the following theorem.

\begin{theo}  
\label{encoding}
Let $G$ be a Gr\"obner basis for the module
${\sf M}(C)$ with respect to a term ordering $\prec$ on ${\cal P}^r$.  
The algorithm below produces a codeword $c$ in all cases
and gives a systematic encoder for the code $C$.  
\end{theo}
\bigskip
\leftline{$\qquad$ Input: $G$, the nonstandard terms $m_i$, information symbols $c_i$}
\leftline{$\qquad$ Output: $c$, a codeword}
\bigskip
\leftline{$\qquad\qquad f = \sum c_i m_i$ ; }
\leftline{$\qquad\qquad c := f - {\bf CanonicalForm}(f,G)$;}
\bigskip
\noindent
{\it Proof:}  Since 
$${\bf CanonicalForm}(c) = {\bf CanonicalForm}(f - {\bf CanonicalForm}(f,G),G) = 0,$$
it follows that $c \in {\sf M}(C)$, 
which means that $c$ represents a codeword of $C$.  The
information symbols appear as coefficients of the nonstandard terms in $f$,
but ${\bf CanonicalForm}(f,G)$ is a linear combination of standard
terms.  The sets of nonstandard and standard terms are
disjoint, hence this encoder is systematic, in the sense that the 
information symbols appear unchanged in a subset of the codeword entries.  $\Box$

\bigskip
Some important examples of the term orderings that
can be used here are obtained as
follows.  First order the ${\bf e}_j$ themselves; we will use
$${\bf e}_1 > {\bf e}_2 > \cdots > {\bf e}_r,$$
but the opposite order is also possible and is used too.
The {\it position over term\/} (or $POT$) ordering on ${\cal P}^r$
is defined by
$$ t^i {\bf e}_j \prec_{POT} t^k {\bf e}_\ell$$
if $j > \ell$, or $j = \ell$ and $i < k$. 
Reversing the way the comparison is made, 
we obtain the {\it term over position\/} (or $TOP$)
ordering on ${\cal P}^r$:
$$t^i {\bf e}_j \prec_{TOP} t^k {\bf e}_\ell$$
if $i < k$, or $i = k$ and $j > \ell$.

\section{Automorphisms of curves and AG Goppa codes}
\label{AG}

In \cite{kn:HLS}, it was pointed out that many examples
of AG Goppa codes have the module
structures described in Theorem \ref{autmod}, hence
systematic encoders as described in Theorem \ref{encoding},
because of the presence of automorphisms of the underlying curves.  
Indeed, many interesting curves with large numbers of $\bFq$-rational 
points also tend to have large automorphism groups.  

Let $\X$ be a smooth projective algebraic curve defined
over $\bFq$.  An automorphism of $\X$ is a regular mapping
from $\X$ to itself with a regular inverse.  An automorphism
$\sigma$ of $\X$ defined over $\bFq$ induces an
$\bFq$-automorphism of the function field $K = \bFq(\X)$
(an isomorphism of fields from $K$ to itself that
is the identity on $\bFq$) via $f \mapsto f\circ \sigma^{-1}$.  
The set of all automorphisms of $\X$ forms a group ${\rm Aut}(\X)$
under function composition and ${\rm Aut}(\X)$ acts on divisors
on $\X$ in the obvious way:  $\sigma(\sum n_P P) = \sum n_P \sigma(P)$.

In fact, all of the examples of automorphisms we 
will consider will be induced by invertible linear mappings on 
the ambient projective space of $\X$.  If such a mapping takes the 
curve $\X$ to itself, then it induces an automorphism of $\X$.  

For instance, consider the Hermitian function fields and 
curves over ${\mathbb F}_{q^2}$.  The  
Hermitian curve may be defined as the variety
$${\cal V}(x_0^{q+1} + x_1^{q+1} + x_2^{q+1}) \subset \P^2,$$
where $(x_0 : x_1 : x_2)$ is the homogeneous coordinate vector of 
a point in $\P^2$.
In section VI.3 of \cite{kn:S}, it is shown that (in geometric language)
the tangent line to this curve at an ${\mathbb F}_{q^2}$-rational point 
can be taken to the line at infinity by a linear change of coordinates in $\P^2$.
When that is done, the defining equation is taken to the form given in
the following
\begin{equation}
\label{eq:altHerm}
{\cal HC}_q = {\cal V}(x^{q+1} - y^qz - yz^q) = \{(x:y:z) \in \P^2 : x^{q+1} - y^qz - yz^q = 0\}.
\end{equation}
We will use this form of the equations of the Hermitian curves.
Let $\alpha$ be a primitive element of ${\mathbb F}_{q^2}$.
The mapping 
\begin{eqnarray}
\label{eq:Hermaut}
\sigma : \P^2 &\to& \P^2\nonumber\\ 
(x : y : z) &\mapsto& (\alpha x :\alpha^{q+1} y : z)
\end{eqnarray}
induces an automorphism of the curve ${\cal HC}_q$ because
it is easy to check that if the point $(x : y : z)$
satisfies the equation in (\ref{eq:altHerm}), the same is true of 
$\sigma(x : y : z)$.  

In the construction of an AG Goppa evaluation code on a curve
$\X$, recall that one begins by selecting $\bFq$-rational divisors 
$D = \sum_{i=1}^n P_i$ and $E$ with disjoint supports on $\X$.  
The codewords are obtained by evaluating the rational functions 
$f$ in the vector space
$$L(E) = \{ f : (f) + E \ge 0\} \cup \{0\}$$
at the points in $D$:
\begin{eqnarray*}
ev : L(E) & \to & \bFq^n\\
       f  & \mapsto & (f(P_1),\ldots,f(P_n)).
\end{eqnarray*}
The image of the evaluation mapping is the AG Goppa evaluation
code $C_L(D,E)$.  

\begin{theo}
\label{curveaut}
In this situation, let $\sigma$ be an automorphism of the curve 
$\X$ and assume the divisors $D$ and $E$ are fixed by
$\sigma$.  Then $\sigma$ induces an automorphism of the code 
$C_L(D,E)$.
\end{theo}

\noindent
{\it Proof:}  Since $\sigma$ fixes the divisor $E$, 
it follows that $f \mapsto f\circ \sigma^{-1}$ takes
$L(E)$ to itself.  Hence we can define an action of
$\sigma$ on the codewords
of $C_L(D,E)$ by
$$(f(P_1), \ldots, f(P_n)) \mapsto (f(\sigma^{-1}(P_1)),\ldots, f(\sigma^{-1}(P_n))).$$
Since the divisor $D$ is also assumed to be fixed by $\sigma$, this
means that the points $\{\sigma^{-1}(P_i)\}$ are a permutation
of the $\{P_i\}$.  Hence $\sigma$ induces a permutation automorphism
of the code $C_L(D,E)$.  $\Box$

\bigskip 
By Proposition VII.3.3 of \cite{kn:S}, the subgroup
$\langle \sigma \rangle$ of ${\rm Aut}({\cal X})$
can be viewed as a subgroup of the permutation automorphism
group of $C_L(D,E)$ whenever $n > 2g + 2$, where $g$ is 
the genus of $\X$.  Furthermore, Joyner and Ksir, \cite{kn:JK},
have given conditions under which the permutation automorphism group 
of $C_L(D,E)$ is isomorphic to the subgroup of ${\rm Aut}(\X)$ 
fixing $D$ and $E$.

Because of these observations, Theorems \ref{autmod} and \ref{encoding} from 
\S \ref{modstruct} apply
to any $C_L(D,E)$ code from a curve $\X$ with an
automorphism $\sigma$ fixing $D$ and $E$, provided $n = \deg D$ is sufficiently 
large.  In the case of maximal length one-point codes ($E = aQ$ for some point $Q$,
$a \ge 0$, and $D$ the sum of the other $\bFq$-rational points), 
it suffices to find a $\sigma$ defined over $\bFq$ fixing $Q$.  One usually
takes $\sigma$ with maximal order to make the number of orbits as
small as possible.

\section{Examples} 
\label{ex}

\bigskip
\noindent
{\bf Example 1.} 
As shown in section VII.4 of \cite{kn:S}, the Hermitian curve 
${\cal HC}_q$ is a smooth
plane curve of degree $q+1$, hence has genus $q(q-1)/2$.  In addition, 
${\cal HC}_q$ has $q^3 + 1$ ${\mathbb F}_{q^2}$-rational points.  There
are $q^3$ affine points.  In the coordinates used in 
(\ref{eq:altHerm}), there are $q$ points on each line $x = c$ and 
$Q = (0:1:0)$ at infinity.
As is well-known, this is the maximum number possible for a curve of 
genus $g = q(q-1)/2$ over ${\mathbb F}_{q^2}$ by the Hasse-Weil bound.
If $g = g(\X) = q(q-1)/2$, then 
$$|\X(\mathbb{F}_{q^2})| \le 1 + q^2 + 2g q = 1 + q^2 + q(q-1)q = q^3 + 1.$$

With $q = 2$, we get the picture of the ${\mathbb F}_4$-rational
points on the Hermitian curve ${\cal V}(x^3 + y^2z + yz^2)$ given below in Figure 1.

The mapping $\sigma$ from (\ref{eq:Hermaut}) 
is an automorphism of of the Hermitian curve fixing $Q$ and 
permuting the $q^3$ affine ${\mathbb F}_{q^2}$-rational points.
The subgroup of the full automorphism group generated by $\sigma$ has
order $q^2 - 1$.  Theorem \ref{curveaut} and the construction from \S \ref{modstruct} apply 
if we take the divisor $E = aQ$ for any $a\ge 0$, and let $D$ be 
the sum of the $q^3$ affine ${\mathbb F}_{q^2}$-rational points, 
each with coefficient 1.  

In the case $q = 2$, the automorphism $\sigma$ is given by
$$\sigma(x: y: z) = (\alpha x: y: z)$$
(since $\alpha^3 = 1$).  This 
permutes the eight affine ${\mathbb F}_4$-rational points in four orbits,
two of length three, and two of length one:

\begin{eqnarray*}
O_1 &=& \{(1:\alpha:1), (\alpha:\alpha:1), (\alpha^2:\alpha:1)\}\\
O_2 &=& \{(1:\alpha^2:1), (\alpha:\alpha^2:1), (\alpha^2:\alpha^2:1)\}\\
O_3 &=& \{(0:0:1)\}\\
O_4 &=& \{(0:\alpha:1)\}.
\end{eqnarray*}

There are similar patterns for the orbits of $G = \langle \sigma \rangle$
on the ${\mathbb F}_{q^2}$-rational points in $D$ for any $q$.

\bigskip
\begin{center}
\begin{picture}(160,160)(0,0)
\put(20,20){\vector(1,0){140}}
\put(20,20){\vector(0,1){140}}
\put(20,20){\circle*{8}}
\put(20,60){\circle*{8}}
\put(60,100){\circle*{8}}
\put(60,140){\circle*{8}}
\put(100,100){\circle*{8}}
\put(100,140){\circle*{8}}
\put(140,100){\circle*{8}}
\put(140,140){\circle*{8}}
\put(20,6){$0$}
\put(60,8){$1$}
\put(100,8){$\alpha$}
\put(140,8){$\alpha^2$}
\put(156,8){$x$}
\put(8,20){$0$}
\put(8,60){$1$}
\put(8,100){$\alpha$}
\put(8,140){$\alpha^2$}
\put(8,156){$y$}
\end{picture}\\
Figure 1.  The ${\mathbb F}_4$-rational points of the Hermitian curve with $q = 2$.
\end{center}

\bigskip
Under $\sigma$ there are $q$ orbits of length $q^2 - 1$ (all coordinates 
nonzero), one orbit of length $q - 1$ (the points with $x = 0$, $y \ne 0$), and 
one orbit of length 1 (a fixed point -- $\{(0:0:1)\}$).  
See \cite{kn:HLS} and \cite{kn:LSH}
for more detail on these Hermitian examples. 

We next show the module structure for the code $C = C_L(D,3Q)$
from the Hermitian curve over ${\mathbb F}_4$ and a Gr\"obner basis
in detail.  The affine coordinate functions $x/z$ and $y/z$ are
elements of $L(3Q)$, as is $1 = z/z$.
Hence, if we order the ${\mathbb F}_4$-rational points 
on $H$ according to the orbit structure above (listing 
the points in $O_1$, then $O_2$, then $O_3$, and finally $O_4$), 
the code $C_L(D,3Q)$ has 
generator matrix
$${\cal M} = \pmatrix{1&1&1&1&1&1&1&1\cr
           1&\alpha&\alpha^2&1&\alpha&\alpha^2&0&0\cr
           \alpha&\alpha&\alpha&\alpha^2&\alpha^2&\alpha^2&0&1\cr}.$$
and parameters $[n,k,d] = [8,3,5]$ over 
${\mathbb F}_4$ (incidentally, the best possible $d$ for this $n,k$
over ${\mathbb F}_4$).

Under the mapping $\phi$ from \S 1, the first row
corresponds, for instance, to the module element
$$(1 + t + t^2, 1 + t + t^2, 1, 1).$$
With respect to the $\prec_{POT}$ term ordering, the reduced Gr\"obner basis 
$G$ for the submodule of ${\cal P}^4$ corresponding
to $\phi(C)$ is:
\begin{eqnarray*}
g_1 &=& (\alpha + t, \alpha + t, \alpha^2, \alpha^2)\\
g_2 &=& (0, 1 + t + t^2, \alpha, \alpha^2)\\
g_3 &=& (0,0,1 + t,0)\\
g_4 &=& (0,0,0,1 + t).
\end{eqnarray*}
The element $g_1$, for instance, equals the linear combination
$$\alpha^2(1 + t + t^2, 1 + t + t^2, 1, 1) + (1 + \alpha t + \alpha^2 t^2, 
1 + \alpha t + \alpha^2 t^2, 0, 0)$$
of the module elements from rows 1 and 2 of ${\cal M}$ which would be
computed in the course of Buchberger's algorithm.  
(Recall that $\alpha^2 + \alpha + 1 = 0$ in ${\mathbb F}_4$.)

In the systematic encoding presented in Theorem \ref{encoding}, we have
\begin{itemize}
\item Information positions: coefficients of $t^2 e_1$, $t e_1$, $t^2 e_2$.
\item Parity checks: coefficients of $e_1$, $t e_2$, $e_2$, $e_3$, $e_4$.
\end{itemize}
Then, to do encoding in this example, it suffices to compute remainders 
on division by $G$.  For the $\prec_{POT}$ term ordering, this amounts
to ordinary polynomial divisions in each component. 
For example, if we want to encode
$$f = (t + \alpha t^2, \alpha^2 t^2,0,0),$$
it is easy to check that dividing first by $g_1$, then $g_2$ yields
$${\bf CanonicalForm}(f,G) = (\alpha^2, \alpha, \alpha, \alpha^2).$$
The corresponding codeword is 
$$c = f - {\bf CanonicalForm}(f,G) 
= (\alpha^2 + t + \alpha t^2, \alpha + \alpha^2 t^2, \alpha,\alpha^2).$$
As indicated in the proof of Theorem \ref{encoding}, the information from the coefficients of $f$
is visible immediately in the codeword $c$, so this is a systematic encoding method.

We note that Hermitian curves have many  
automorphisms besides those in the subgroup generated by $\sigma$
above.  Indeed, for some $q$, there are $\sigma$ of order larger than
$q^2 - 1$ fixing $Q$ and $D$ (see \cite{kn:HLS}).
Moreover, by \cite{kn:S}, VII.4.6, there is also a nonabelian
subgroup $\overline{H}$ of order $|\overline{H}| = (q^2-1)q^3$ in the full automorphism
group of the Hermitian curve that fixes both the point 
at infinity $Q$, and the divisor $D$, hence induces automorphisms of
$C_L(D,aQ)$ for all $a$.  The elements of this subgroup can be written as the mappings
$$\tau_{\lambda,\delta,\mu}(x : y : z) = 
(\lambda x + \delta z : \lambda^{q+1} y + \lambda\delta^q x + \mu z : z),$$
where $\lambda \in {\mathbb F}_{q^2}^{\,*}$, and $(\delta : \mu : 1)$ is any affine
${\mathbb F}_{q^2}$-rational point on the curve.  Note that 
$$\tau_{\lambda,\delta,\mu}(0 : 0 : 1) = (\delta : \mu : 1).$$
This implies that $\overline{H}$ acts {\it transitively\/} on the affine
${\mathbb F}_{q^2}$-rational points, or equivalently, that
there is only one orbit of points under $\overline{H}$.  Consequently, 
the codes $C_L(D,aQ)$ can also be studied as {\it ideals} in the group 
algebra ${\mathbb F}_{q^2}[\overline{H}]$.  Since $\overline{H}$ is not abelian, however, the analogs of Gr\"obner bases in the group algebra
do not seem to be as convenient for encoding. 
$\Diamond$

\bigskip
AG Goppa codes from several other classes of 
curves with the maximal number of rational
points for their genus over the given field $\bFq$ 
can be treated in a very similar fashion.  

\bigskip
\noindent
{\bf Example 2.} Let $q = 2^{2n+1}$, $q_0 = 2^n$ and let 
${\cal Y}_n$ be the curve over $\bFq$ defined by the affine equation
$$x^q + x = y^{q_0}(y^q + y).$$
These curves were studied by Hansen and Stichtenoth in \cite{kn:HS},
and by a number of other authors.
With $n = 1$, for example, the curve ${\cal Y}_1$ over ${\mathbb F}_8$
in this family has affine equation
$$x^8 + x = y^2(y^8 + y).$$
This defines a curve of degree 10, genus 14, with a single (singular) point 
$Q$ at infinity.  The singularity at $Q$ is a cuspidal (unibranch) singularity -- 
more precisely, there is only one point $\widetilde{Q}$ that lies over $Q$
on the normalization (smooth model) $\widetilde{{\cal Y}_n} \to {\cal Y}_n$.  

From the point of view of coding theory, the curves ${\cal Y}_n$ are interesting because 
they have as many $\bFq$-rational points as possible for a curve of 
their genus (however, the Hasse-Weil bound is not sharp in these cases).  
Indeed, ${\cal Y}_n$ passes through {\it every point\/} of the affine plane over
${\mathbb F}_q$.  For constructing AG Goppa evaluation codes from ${\cal Y}_n$, 
one can use $G = a\widetilde{Q}$ and $D$ the sum of the 
$q^2$ ${\mathbb F}_q$-rational affine points, each with 
coefficient 1. 

Letting $\alpha$ denote a primitive element of $\bFq$, the mapping
\begin{equation}
\label{eq:HSaut}
\sigma(x,y) = (\alpha^{q_0+1} x,\alpha y)
\end{equation}
restricts to an automorphism of ${\cal Y}_n$.  
Since $\sigma$ fixes the divisors $D$ and $G = a\widetilde{Q}$, 
$\sigma$ induces an automorphism of each of the codes 
$C_L(D,a\widetilde{Q})$ constructed from ${\cal Y}_n$, by Theorem \ref{curveaut}. 
The automorphism $\sigma$ has
order $q - 1$ in ${\rm Aut}({\cal Y}_n)$.  The following explicit example of 
the module structure of one of these codes comes
from \cite{kn:L1}. 

The code $C = C_L(D, 57 \widetilde{Q})$ on the 
Hansen-Stichtenoth curve ${\cal Y}_1$ has parameters
$n = 64$, $k = 44$, $d = 8$ by \cite{kn:CD}.  The automorphism $\sigma$ from (\ref{eq:HSaut})
permutes the points of $D$ in 10 orbits, 9 of length 7 and one
of length 1.  The semigroup of pole orders at $\widetilde{Q}$ 
of rational functions on the curve ${\cal Y}_1$ is 
generated by the natural numbers $8,10,12,13$.  Moreover 
$y \in L(8\widetilde{Q})$, 
$x \in L(10\widetilde{Q})$, $f = y^5 + x^4 \in L(12\widetilde{Q})$,   
and $g = yx^4 + y^{20} + x^{16} \in L(13 \widetilde{Q})$ (see 
\cite{kn:HS}).
We use these functions to generate a basis for $L(57\widetilde{Q})$,
the normalization 
${\mathbb F}_8 = {\mathbb F}_2[\alpha]/\langle \alpha^3 + \alpha + 1 \rangle$, 
and the orbit representatives $(1,\alpha^6), \ldots, (1,\alpha), (1, 1),
(0,1), (1,0), (0,0)$ (in that order).  The reduced $\prec_{POT}$ Gr\"obner basis
$G$ of the module ${\sf M}(C)$ has the form
\begin{eqnarray*}
g_1 & = & (1,0,0,0,0,*,*,*,*,*)\\
g_2 & = & (0,1,0,0,0,*,*,*,*,*)\\
g_3 & = & (0,0,1,0,0,*,*,*,*,*)\\
g_4 & = & (0,0,0,1,0,*,*,*,*,*)\\
g_5 & = & (0,0,0,0,1,*,*,*,*,*)\\
g_6 & = & (0,0,0,0,0,t^2+(\alpha^2+\alpha)t+\alpha+1,*,*,*,*)\\
g_7 & = & (0,0,0,0,0,0,t^4+(\alpha+1)t^3+(\alpha^2+1)t^2+\alpha^2+\alpha+1,*,*,*)\\
g_8 & = & (0,0,0,0,0,0,0,t^6+t^5+t^4+t^3+t^2+t+1,0,0)\\
g_9 & = & (0,0,0,0,0,0,0,0,t^7+1,0)\\
g_{10} & = & (0,0,0,0,0,0,0,0,0,t+1).
\end{eqnarray*}
(To save space, the coefficients in the non-maximal terms are omitted. 
Also, it is only the maximal terms that determine the information positions
and parity check positions for the code.)

Like the Hermitian curves, the Hansen-Stichtenoth curve ${\cal Y}_1$ has many 
automorphisms besides those in the subgroup generated by the $\sigma$ from
(\ref{eq:HSaut}) we have
used.  There is a (non-abelian) subgroup $\overline{H}$ of $Aut({\cal Y}_1)$, of order $448$ that fixes both $a\widetilde{Q}$ and $D$, hence induces
automorphisms of each $C_L(D,a\widetilde{Q})$ code.  The elements of this subgroup 
can be written as
$$\tau_{\lambda,\delta,\mu}(x,y) = (\lambda^3 x + \lambda\delta^2 y + \mu,\lambda y + \delta),$$
where $\lambda \in {\mathbb F}_8^{\,*}$, and $(\mu,\delta)$ is any affine
${\mathbb F}_8$-rational point on ${\cal Y}_1$.  Once again, 
$\overline{H}$ acts transitively on the points of $D$, 
and the codes $C_L(D,a\widetilde{Q})$ are {\it ideals} in the group 
algebra ${\mathbb F}_8[\overline{H}]$.  $\Diamond$

\bigskip
Codes from both the Hermitian and Hansen-Stichtenoth curves can be
studied with the language of order domains introduced in 
\cite{kn:HLP}.  Higher-dimensional varieties can also be used 
to construct examples of order domains and generalized Goppa-type
evaluation codes.  See, for instance, \cite{kn:GP} and 
\cite{kn:L2} for a general discussion of order domains, how
they arise, and how the theory of Gr\"obner bases yields
key insights about their structure and their special 
relevance for coding theory. 

\bigskip
\noindent
{\bf Example 3.}
For instance let 
$${\cal HS}_q = {\cal V}(x_0^{q+1} + x_1^{q+1} + x_2^{q+1} + x_3^{q+1})$$
be the Hermitian surface in ${\mathbb P}^3$.  The variety ${\cal HS}_q$ has 
$$(q^2 + 1)(q^3 + 1)$$
$\mathbb{F}_{q^2}$-rational
points.  Changing coordinates to put a 
tangent plane to the surface as the plane at infinity gives the
affine surface 
$${\cal HS'}_q = {\cal V}(x^{q+1} + y^{q+1} - z^q - z)$$
(whose affine coordinate ring has an order domain structure).
${\cal HS'}_q$ has $q^5$ $\mathbb{F}_{q^2}$-rational points.
${\cal HS'}_q$ also has many automorphisms, for instance
$$\sigma(x,y,z) = (\alpha x, \alpha y, \alpha^{q+1}z)$$ 
(of order = $q^2 - 1$).
This $\sigma$ fixes the plane at infinity and permutes the
$q^5$ ${\mathbb F}_{q^2}$-rational points in $q^3 + q$ orbits 
of size $q^2 - 1$, one of size $q-1$, and one of size 1.  So 
Theorem \ref{autmod} applies to all evaluation codes constructed from 
${\cal H}'$ and subspaces $L \subset {\mathbb F}_{q^2}[x,y,z]$.
For instance, the code from the Hermitian surface over
${\mathbb F}_4$ constructed by evaluating $1,x,y,z$
has $[n,k,d] = [32,4,22]$.
The minimum weight codewords come by evaluating linear
polynomials that define the tangent plane at one of the 
$\mathbb{F}_4$-rational points on the surface.
The minimum distance $d = 22$ equals the best possible
for a code with $n = 32$, $k = 4$ over $\mathbb{F}_4$ by Brouwer's 
online tables.  But these codes also have Gr\"obner basis encoding, 
and good decoding algorithms because of the extra order
domain structure. $\Diamond$

\bigskip
Ironically, when order domains were introduced
by H\o holdt, van Lint, and Pellikaan in \cite{kn:HLP}, 
their goal was in large part to ``take the (hard) algebraic 
geometry out of the theory of AG Goppa codes.'' 
As it turns out, their synthesis of that 
theory has made it possible
to use even more commutative algebra and algebraic geometry
to construct new examples of error control codes, and to
generalize the existing encoding and decoding algorithms.
The theory of Gr\"obner bases has been a key tool here. 

\begin{thebibliography}{CLO} 


\bibitem[C]{kn:C} Chabanne, H. ``Permutation decoding of 
abelian codes,'' {\sl IEEE Trans. on Inform Theory} {\bf 38} (1992),
1826--1829.  

\bibitem[CD]{kn:CD} Chen, C.-Y. and Duursma, I. ``Geometric Reed-Solomon 
codes of length 64 and 65 over F8,''  {\sl IEEE Trans. on Inform. Theory}
{\bf 49} (2003), 1351-1353.

\bibitem[CL]{kn:CL} Chen, J.-P. and Lu, C.-C. ``A serial-in-serial-out hardware architecture for systematic encoding of Hermitian codes via Groebner bases,'' 
{\sl IEEE Trans. on Communications}, {\bf 52}, no. 8 (2004), 1322--1332.

\bibitem[CLO]{kn:CLO} Cox, D., Little, J., and O'Shea, D.
{\sl Using Algebraic Geometry, 2nd ed.}, New York: Springer Verlag, 2005.

\bibitem[GP]{kn:GP}
Geil, O. and Pellikaan, R.
``On the Structure of Order Domains,''
{\sl Finite Fields Appl.} {\bf 8} (2002), 369-396.

\bibitem[HS]{kn:HS}  Hansen, J. and Stichtenoth, H.  
``Group Codes on Certain Algebraic Curves with Many Rational Points,''
{\sl Applicable Algebra in Eng. Comm. Comp.}  {\bf 1} (1990), 67-77.
     
\bibitem[HLS]{kn:HLS} Heegard, C., Little, J., and Saints, K.
``Systematic encoding via Gr\"obner bases for a class of algebraic-geometric 
Goppa codes,'' {\it IEEE Trans. Inform. Theory} {\bf 41} (1995), 1752-1761.

\bibitem[HLP]{kn:HLP} H\o holdt, T., van Lint, J., and Pellikaan, R.
``Algebraic Geometry Codes,'' in {\sl Handbook of Coding Theory}
(Huffman, W. and Pless, V. eds.), Amsterdam: Elsevier, 1998, 871-962.

\bibitem[JK]{kn:JK} Joyner, D. and Ksir, A. ``Automorphism groups of some 
AG codes.''  {\sl IEEE Trans. Inform. Theory} {\bf 52}  (2006),  3325--3329.

\bibitem[LF]{kn:LF} Lally, K. and Fitzpatrick, P. 
``Algebraic structure of quasicyclic codes,''
{\it Discrete Appl. Math.} {\bf 111} (2001), 157--175.

\bibitem[L1]{kn:L1} Little, J. ``The Algebraic Structure of Some AG Goppa 
Codes,'' Proceedings of 33rd Annual Allerton Conference on Communication, 
Control, and Computing (1995), University of Illinois, 492-500.

\bibitem[L2]{kn:L2} Little, J.  ``The Ubiquity of Order Domains
for the Construction of Error Control Codes,'' {\it Advances in Mathematics of 
Communications} {\bf 1} (2007), 151-171.

\bibitem[LSH]{kn:LSH} Little, J., Saints, K., and Heegard, C. ``On the structure of 
Hermitian codes,''  {\it J. Pure Appl. Algebra} {\bf 121}  (1997), 293--314.

\bibitem[MM]{kn:MM} Matsui, H. and Mita, S. ``Efficient encoding via 
Gr\"obner bases and discrete Fourier transforms for several kinds of
algebraic codes,'' accepted for proceedings of ISIT 2007, 
{\it preprint:} ArXiv:cs.IT/0703104.

\bibitem[MOS]{kn:MOS} Matsumoto, R., Oishi, M., Sakaniwa, K. ``Fast 
Encoding of Algebraic Geometry Codes,'' {\sl IEICE Trans. Fundamentals}, 
{\bf E84-A} (2001), 2514--2517.

\bibitem[PH]{kn:PH} Poli, A., and Huguet, L.  {\sl Error Correcting Codes: Theory
and Applications}, Hemel Hempstead: Prentice Hall International, 1992.
 
\bibitem[S]{kn:S} Stichtenoth, H.  {\sl Algebraic Function Fields and Codes},
Berlin: Springer Verlag, 1993.
\end{thebibliography}

\end{document}
