Automorphisms and Encoding of AG and Order Domain Codes

John B. Little Department of Mathematics and Computer Science College of the Holy Cross Worcester, MA 01610 USA

             little@mathcs.holycross.edu

March 31, 2007

Abstract

If a linear code C over 𝔽_{q} has a finite abelian group H as a group of automorphisms, then C has the structure of a module over a polynomial ring P. This structure can be used to develop systematic encoding algorithms using Gröbner bases for modules. We illustrate these observations with several examples including geometric Goppa codes and codes from order domains.

1 Introduction

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, [HLS], which shows how to use module Gröbner 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öbner basis here is that it furnishes an analog of the generator polynomial of a cyclic code (see Theorem 2). This particular connection between encoding and Gröbner bases was well-established previously in the case of abelian (m-dimensional cyclic) codes. See, for instance, [PH], section 6.1.6, or Chapter 9 of [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 §4). Some results on implementation of this approach in hardware for the case of codes from the Hermitian curves considered in §5 have been reported by Chen and Lu, [CL].

More recent work on encoding methods for AG Goppa codes includes Matsumoto, Oishi, and Sakaniwa, [MOS]. This article proposes a fast nonsystematic encoding method for the one-point residue codes C_{Ω}(D, mQ) based on the structure of a special basis for the vector space of differentials Ω(mQ − D). In addition, Matsui and Mita, [MM], have described a method combining discrete Fourier transforms and Gröbner bases for the ideal of polynomials with a given collection of zeroes that yields a systematic encoder for C_{Ω}(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 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, [C], has considered this decoding method from the point of view of Gröbner bases in the case of abelian codes, and [L1] gives an example for a Hermitian code.

2 Automorphisms and module structures

The symmetric group S_{n} acts on 𝔽_{q}^{n} by permuting the entries of vectors. A permutation automorphism of a linear code C ⊂ 𝔽_{q}^{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 = ⟨σ⟩ 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 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, …, r be the orbits of the components of the codewords c under the action of H. Pick any component c_{i,0} in the ith orbit and label the components in that orbit as c_{i,j} where j = 0, …, |O_{i}| − 1. With the convention that the second index is an integer modulo |O_{i}|, the action of σ can be written as σ(c_{i,j}) = c_{i,j+1} for all i = 1, …, r, and j = 0, …, |O_{i}| − 1.

For the remainder of this chapter, P will denote the polynomial ring in one variable 𝔽_{q}[t]. As usual, let e_{i} be the ith standard basis vector in the free module P^{r}. Then the orbit structure of the components of the codewords of C determines the submodule ⟨(t^{|O_{i}|} − 1)e_{i} : i = 1, …, r⟩ of P^{r}. We can view the code C as subset of the quotient module

N = P^{r}/⟨(t^{|O_{i}|} − 1)e_{i} : i = 1, …, r⟩,  (1)

via the mapping

ϕ : C → N
(c_{i,j}) ↦ ∑_{i=1}^{r} ( ∑_{j=0}^{|O_{i}|−1} c_{i,j}t^{j}) e_{i} mod ⟨(t^{|O_{i}|} − 1)e_{i} : i = 1, …, r⟩.

We have the following theorem describing the structure of the image ϕ(C).

Theorem 1 Let C linear block code over 𝔽_{q} with a cyclic group H of automorphisms and ϕ, N be as above. Then ϕ(C) has the structure of a Psubmodule of N.

Proof: First ϕ is linear, so ϕ(C) is an 𝔽_{q}-vector subspace of N. By the definition of ϕ, if c ∈ C is any codeword, multiplication of ϕ(c) by t yields

t · ϕ(c) = ∑_{i=1}^{r} ( ∑_{j=0}^{|O_{i}|−1} c_{i,j}t^{j+1}) e_{i}

≡ ∑_{i=1}^{r} ( ∑_{j=0}^{|O_{i}|−1} c_{i,j−1}t^{j}) e_{i} mod N

= ϕ(σ^{−1}(c)).

By hypothesis, this is another element of ϕ(C). Hence ϕ(C) is closed under multiplication by t, hence under multiplication by all polynomials in P. It follows that ϕ(C) is a P-submodule of N. □

Note that if the theorem applies to a code C, it applies to the dual code C^{⊥} as well.

In [HLS], [LSH], and [L1], this essentially straightforward generalization of the usual construction showing that a cyclic code of length n over 𝔽_{q} is an ideal in P/⟨t^{n} − 1⟩ was applied to some AG Goppa codes. We will present several explicit examples in §5. The article [LF] applies the module structures described here to study quasicyclic codes. Theorem 1 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.

3 A systematic encoding algorithm

We will now show how the theory of Gröbner bases for modules can be applied to work with these codes. Let M(C) be the submodule of P^{r} corresponding to ϕ(C) ⊂ N under the mapping

π : P^{r} → N,

where N is the quotient module from (1). The key observation here is that the canonical form algorithm with respect to a Gröbner basis G for M(C) with respect to any term ordering ≺ on P^{r} can be used to produce a systematic encoder for C.

One potential advantage of exploiting the module structures described in Theorem 1 is that, as is true for the generator polynomial of a cyclic code, a Gröbner basis for 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 M(C). In what follows, the terms t^{j}e_{i} in the Gröbner éscalier N_{≺}(M(C)) will be called the standard terms. The nonstandard terms are the t^{j}e_{i} with j ≤ |O_{i}| − 1 contained in the monomial module T_{≺}(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.

Theorem 2 Let G be a Gröbner basis for the module M(C) with respect to a term ordering ≺ on P^{r}. The algorithm below produces a codeword c in all cases and gives a systematic encoder for the code C.

Input: G, the nonstandard terms m_{i}, information symbols c_{i} Output: c, a codeword

f = ∑ c_{i}m_{i} ;

c := f − CanonicalForm(f, G);

Proof: Since

CanonicalForm(c) = CanonicalForm(f−CanonicalForm(f, G), G) = 0,

it follows that c ∈ M(C), which means that c represents a codeword of C. The information symbols appear as coefficients of the nonstandard terms in f, but 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. □

Some important examples of the term orderings that can be used here are obtained as follows. First order the e_{j} themselves; we will use

e_{1} > e_{2} > ⋯ > e_{r},

but the opposite order is also possible and is used too. The position over term (or P OT) ordering on P^{r} is defined by

t^{i}e_{j} ≺_{P OT} t^{k}e_{ℓ}

if j > ℓ, or j = ℓ and i < k. Reversing the way the comparison is made, we obtain the term over position (or T OP) ordering on P^{r}:

t^{i}e_{j} ≺_{T OP} t^{k}e_{ℓ}

if i < k, or i = k and j > ℓ.

4 Automorphisms of curves and AG Goppa codes

In [HLS], it was pointed out that many examples of AG Goppa codes have the module structures described in Theorem 1, hence systematic encoders as described in Theorem 2, because of the presence of automorphisms of the underlying curves. Indeed, many interesting curves with large numbers of 𝔽_{q}-rational points also tend to have large automorphism groups.

Let X be a smooth projective algebraic curve defined over 𝔽_{q}. An automorphism of X is a regular mapping from X to itself with a regular inverse. An automorphism σ of X defined over 𝔽_{q} induces an 𝔽_{q}-automorphism of the function field K = 𝔽_{q}(X) (an isomorphism of fields from K to itself that is the identity on 𝔽_{q}) via f ↦ f ∘σ^{−1}. The set of all automorphisms of X forms a group Aut(X) under function composition and Aut(X) acts on divisors on X in the obvious way: σ(∑ n_{P} P) = ∑ n_{P} σ(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 𝔽_{q^{2}}. The Hermitian curve may be defined as the variety

V(x_{0}^{q+1} + x_{1}^{q+1} + x_{2}^{q+1}) ⊂ ℙ^{2},

where (x_{0} : x_{1} : x_{2}) is the homogeneous coordinate vector of a point in ℙ^{2}. In section VI.3 of [S], it is shown that (in geometric language) the tangent line to this curve at an 𝔽_{q^{2}}-rational point can be taken to the line at infinity by a linear change of coordinates in ℙ^{2}. When that is done, the defining equation is taken to the form given in the following

HC_{q} = V(x^{q+1} − y^{q}z − yz^{q}) = {(x : y : z) ∈ ℙ^{2} : x^{q+1} − y^{q}z − yz^{q} = 0}. (2)

We will use this form of the equations of the Hermitian curves. Let α be a primitive element of 𝔽_{q^{2}}. The mapping

σ : ℙ^{2} → ℙ^{2}
(x : y : z) ↦ (αx : α^{q+1}y : z)  (3)

induces an automorphism of the curve HC_{q} because it is easy to check that if the point (x : y : z) satisfies the equation in (2), the same is true of σ(x : y : z).

In the construction of an AG Goppa evaluation code on a curve X, recall that one begins by selecting 𝔽_{q}-rational divisors D = ∑_{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 ≥ 0} ∪ {0}

at the points in D:

ev : L(E) → 𝔽_{q}^{n}
f ↦ (f(P_{1}), …, f(P_{n})).

The image of the evaluation mapping is the AG Goppa evaluation code C_{L}(D, E).

Theorem 3 In this situation, let σ be an automorphism of the curve X and assume the divisors D and E are fixed by σ. Then σ induces an automorphism of the code C_{L}(D, E).

Proof: Since σ fixes the divisor E, it follows that f ↦ f ∘ σ^{−1} takes L(E) to itself. Hence we can define an action of σ on the codewords of C_{L}(D, E) by

(f(P_{1}), …, f(P_{n})) ↦ (f(σ^{−1}(P_{1})), …, f(σ^{−1}(P_{n}))).

Since the divisor D is also assumed to be fixed by σ, this means that the points {σ^{−1}(P_{i})} are a permutation of the {P_{i}}. Hence σ induces a permutation automorphism of the code C_{L}(D, E). □

By Proposition VII.3.3 of [S], the subgroup ⟨σ⟩ of Aut(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, [JK], have given conditions under which the permutation automorphism group of C_{L}(D, E) is isomorphic to the subgroup of Aut(X) fixing D and E.

Because of these observations, Theorems 1 and 2 from §2 apply to any C_{L}(D, E) code from a curve X with an automorphism σ fixing D and E, provided n = deg D is sufficiently large. In the case of maximal length onepoint codes (E = aQ for some point Q, a ≥ 0, and D the sum of the other 𝔽_{q}-rational points), it suffices to find a σ defined over 𝔽_{q} fixing Q. One usually takes σ with maximal order to make the number of orbits as small as possible.

5 Examples

Example 1. As shown in section VII.4 of [S], the Hermitian curve HC_{q} is a smooth plane curve of degree q + 1, hence has genus q(q − 1)/2. In addition, HC_{q} has q^{3} + 1 𝔽_{q^{2}}-rational points. There are q^{3} affine points. In the coordinates used in (2), 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 𝔽_{q^{2}} by the Hasse-Weil bound. If g = g(X) = q(q − 1)/2, then

|X (𝔽_{q^{2}})| ≤ 1 + q^{2} + 2gq = 1 + q^{2} + q(q − 1)q = q^{3} + 1.

With q = 2, we get the picture of the 𝔽_{4}-rational points on the Hermitian curve V(x^{3} + y^{2}z + yz^{2}) given below in Figure 1.

The mapping σ from (3) is an automorphism of of the Hermitian curve fixing Q and permuting the q^{3} affine 𝔽_{q^{2}}-rational points. The subgroup of the full automorphism group generated by σ has order q^{2} − 1. Theorem 3 and the construction from §2 apply if we take the divisor E = aQ for any a ≥ 0, and let D be the sum of the q^{3} affine 𝔽_{q^{2}}-rational points, each with coefficient 1.

In the case q = 2, the automorphism σ is given by

σ(x : y : z) = (αx : y : z)

(since α^{3} = 1). This permutes the eight affine 𝔽_{4}-rational points in four orbits, two of length three, and two of length one:

O_{1} = {(1 : α : 1), (α : α : 1), (α^{2} : α : 1)}
O_{2} = {(1 : α^{2} : 1), (α : α^{2} : 1), (α^{2} : α^{2} : 1)}
O_{3} = {(0 : 0 : 1)}
O_{4} = {(0 : α : 1)}.

There are similar patterns for the orbits of G = ⟨σ⟩ on the 𝔽_{q^{2}}-rational points in D for any q.

[figure: 0; 1; α; α^{2}; x; 0; 1; α; α^{2}; y]

Figure 1. The 𝔽_{4}-rational points of the Hermitian curve with q = 2.

Under σ there are q orbits of length q^{2} − 1 (all coordinates nonzero), one orbit of length q − 1 (the points with x = 0, y ≠ 0), and one orbit of length 1 (a fixed point – {(0 : 0 : 1)}). See [HLS] and [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 𝔽_{4} and a Gröbner 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 𝔽_{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

M = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & α & α^{2} & 1 & α & α^{2} & 0 & 0 \\ α & α & α & α^{2} & α^{2} & α^{2} & 0 & 1 \end{matrix} ) .

and parameters [n, k, d] = [8, 3, 5] over 𝔽_{4} (incidentally, the best possible d for this n, k over 𝔽_{4}).

Under the mapping ϕ from §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 ≺_{P OT} term ordering, the reduced Gröbner basis G for the submodule of P^{4} corresponding to ϕ(C) is:

g_{1} = (α + t, α + t, α^{2}, α^{2})
g_{2} = (0, 1 + t + t^{2}, α, α^{2})
g_{3} = (0, 0, 1 + t, 0)
g_{4} = (0, 0, 0, 1 + t).

The element g_{1}, for instance, equals the linear combination

α^{2}(1 + t + t^{2}, 1 + t + t^{2}, 1, 1) + (1 + αt + α^{2}t^{2}, 1 + αt + α^{2}t^{2}, 0, 0)

of the module elements from rows 1 and 2 of M which would be computed in the course of Buchberger’s algorithm. (Recall that α^{2} + α + 1 = 0 in 𝔽_{4}.)

In the systematic encoding presented in Theorem 2, we have

• Information positions: coefficients of t^{2}e_{1}, te_{1}, t^{2}e_{2}.

• Parity checks: coefficients of e_{1}, te_{2}, e_{2}, e_{3}, e_{4}.

Then, to do encoding in this example, it suffices to compute remainders on division by G. For the ≺_{P OT} term ordering, this amounts to ordinary polynomial divisions in each component. For example, if we want to encode

f = (t + αt^{2}, α^{2}t^{2}, 0, 0),

it is easy to check that dividing first by g_{1}, then g_{2} yields

CanonicalForm(f, G) = (α^{2}, α, α, α^{2}).

The corresponding codeword is

c = f − CanonicalForm(f, G) = (α^{2} + t + αt^{2}, α + α^{2}t^{2}, α, α^{2}).

As indicated in the proof of Theorem 2, 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 σ above. Indeed, for some q, there are σ of order larger than q^{2}−1 fixing Q and D (see [HLS]). Moreover, by [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

τ_{λ,δ,μ}(x : y : z) = (λx + δz : λ^{q+1}y + λδ^{q}x + μz : z),

where λ ∈ 𝔽_{q^{2}}^{∗}, and (δ : μ : 1) is any affine 𝔽_{q^{2}}-rational point on the curve. Note that

τ_{λ,δ,μ}(0 : 0 : 1) = (δ : μ : 1).

This implies that \overline{H} acts transitively on the affine 𝔽_{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 ideals in the group algebra 𝔽_{q^{2}}[\overline{H}]. Since \overline{H} is not abelian, however, the analogs of Gröbner bases in the group algebra do not seem to be as convenient for encoding. ♢

AG Goppa codes from several other classes of curves with the maximal number of rational points for their genus over the given field 𝔽_{q} can be treated in a very similar fashion.

Example 2. Let q = 2^{2n+1}, q_{0} = 2^{n} and let Y_{n} be the curve over 𝔽_{q} defined by the affine equation

x^{q} + x = y^{q_{0}}(y^{q} + y).

These curves were studied by Hansen and Stichtenoth in [HS], and by a number of other authors. With n = 1, for example, the curve Y_{1} over 𝔽_{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 Q̃ that lies over Q on the normalization (smooth model) Ỹ_{n} → Y_{n}.

From the point of view of coding theory, the curves Y_{n} are interesting because they have as many 𝔽_{q}-rational points as possible for a curve of their genus (however, the Hasse-Weil bound is not sharp in these cases). Indeed, Y_{n} passes through every point of the affine plane over 𝔽_{q}. For constructing AG Goppa evaluation codes from Y_{n}, one can use G = aQ̃ and D the sum of the q^{2} 𝔽_{q}-rational affine points, each with coefficient 1.

Letting α denote a primitive element of 𝔽_{q}, the mapping

σ(x, y) = (α^{q_{0}+1}x, αy)  (4)

restricts to an automorphism of Y_{n}. Since σ fixes the divisors D and G = aQ̃, σ induces an automorphism of each of the codes C_{L}(D, aQ̃) constructed from Y_{n}, by Theorem 3. The automorphism σ has order q − 1 in Aut(Y_{n}). The following explicit example of the module structure of one of these codes comes from [L1].

The code C = C_{L}(D, 57Q̃) on the Hansen-Stichtenoth curve Y_{1} has parameters n = 64, k = 44, d = 8 by [CD]. The automorphism σ from (4) permutes the points of D in 10 orbits, 9 of length 7 and one of length 1. The semigroup of pole orders at Q̃ of rational functions on the curve Y_{1} is generated by the natural numbers 8, 10, 12, 13. Moreover y ∈ L(8Q̃), x ∈ L(10Q̃), f = y^{5}+ x^{4} ∈ L(12Q̃), and g = yx^{4}+y^{20}+x^{16} ∈ L(13Q̃) (see [HS]). We use these functions to generate a basis for L(57Q̃), the normalization 𝔽_{8} = 𝔽_{2}[α]/⟨α^{3} + α + 1⟩, and the orbit representatives (1, α^{6}), …, (1, α), (1, 1), (0, 1), (1, 0), (0, 0) (in that order). The reduced ≺_{P OT} Gröbner basis G of the module M(C) has the form

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} + (α^{2} + α)t + α + 1, ∗, ∗, ∗, ∗)
g_{7} = (0, 0, 0, 0, 0, 0, t^{4} + (α + 1)t^{3} + (α^{2} + 1)t^{2} + α^{2} + α + 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).

(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 Y_{1} has many automorphisms besides those in the subgroup generated by the σ from (4) we have used. There is a (non-abelian) subgroup \overline{H} of Aut(Y_{1}), of order 448 that fixes both aQ̃ and D, hence induces automorphisms of each C_{L}(D, aQ̃) code. The elements of this subgroup can be written as

τ_{λ,δ,μ}(x, y) = (λ^{3}x + λδ^{2}y + μ, λy + δ),

where λ ∈ 𝔽_{8}^{∗}, and (μ, δ) is any affine 𝔽_{8}-rational point on Y_{1}. Once again, \overline{H} acts transitively on the points of D, and the codes C_{L}(D, aQ̃) are ideals in the group algebra 𝔽_{8}[\overline{H}]. ♢

Codes from both the Hermitian and Hansen-Stichtenoth curves can be studied with the language of order domains introduced in [HLP]. Higherdimensional varieties can also be used to construct examples of order domains and generalized Goppa-type evaluation codes. See, for instance, [GP] and [L2] for a general discussion of order domains, how they arise, and how the theory of Gröbner bases yields key insights about their structure and their special relevance for coding theory.

Example 3. For instance let

HS_{q} = V(x_{0}^{q+1} + x_{1}^{q+1} + x_{2}^{q+1} + x_{3}^{q+1})

be the Hermitian surface in ℙ^{3}. The variety HS_{q} has

(q^{2} + 1)(q^{3} + 1)

𝔽_{q^{2}}-rational points. Changing coordinates to put a tangent plane to the surface as the plane at infinity gives the affine surface

HS′_{q} = V(x^{q+1} + y^{q+1} − z^{q} − z)

(whose affine coordinate ring has an order domain structure). HS′_{q} has q^{5} 𝔽_{q^{2}}-rational points. HS′_{q} also has many automorphisms, for instance

σ(x, y, z) = (αx, αy, α^{q+1}z)

(of order = q^{2} − 1). This σ fixes the plane at infinity and permutes the q^{5} 𝔽_{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 1 applies to all evaluation codes constructed from H′ and subspaces L ⊂ 𝔽_{q^{2}}[x, y, z]. For instance, the code from the Hermitian surface over 𝔽_{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 𝔽_{4}-rational points on the surface. The minimum distance d = 22 equals the best possible for a code with n = 32, k = 4 over 𝔽_{4} by Brouwer’s online tables. But these codes also have Gröbner basis encoding, and good decoding algorithms because of the extra order domain structure. ♢

Ironically, when order domains were introduced by Høholdt, van Lint, and Pellikaan in [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öbner bases has been a key tool here.

References

[C] Chabanne, H. “Permutation decoding of abelian codes,” IEEE Trans. on Inform Theory 38 (1992), 1826–1829.

[CD] Chen, C.-Y. and Duursma, I. “Geometric Reed-Solomon codes of length 64 and 65 over F8,” IEEE Trans. on Inform. Theory 49 (2003), 1351-1353.

[CL] Chen, J.-P. and Lu, C.-C. “A serial-in-serial-out hardware architecture for systematic encoding of Hermitian codes via Groebner bases,” IEEE Trans. on Communications, 52, no. 8 (2004), 1322–1332.

[CLO] Cox, D., Little, J., and O’Shea, D. Using Algebraic Geometry, 2nd ed., New York: Springer Verlag, 2005.

[GP] Geil, O. and Pellikaan, R. “On the Structure of Order Domains,” Finite Fields Appl. 8 (2002), 369-396.

[HS] Hansen, J. and Stichtenoth, H. “Group Codes on Certain Algebraic Curves with Many Rational Points,” Applicable Algebra in Eng. Comm. Comp. 1 (1990), 67-77.

[HLS] Heegard, C., Little, J., and Saints, K. “Systematic encoding via Gröbner bases for a class of algebraic-geometric Goppa codes,” IEEE Trans. Inform. Theory 41 (1995), 1752-1761.

[HLP] Høholdt, T., van Lint, J., and Pellikaan, R. “Algebraic Geometry Codes,” in Handbook of Coding Theory (Huffman, W. and Pless, V. eds.), Amsterdam: Elsevier, 1998, 871-962.

[JK] Joyner, D. and Ksir, A. “Automorphism groups of some AG codes.” IEEE Trans. Inform. Theory 52 (2006), 3325–3329.

[LF] Lally, K. and Fitzpatrick, P. “Algebraic structure of quasicyclic codes,” Discrete Appl. Math. 111 (2001), 157–175.

[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.

[L2] Little, J. “The Ubiquity of Order Domains for the Construction of Error Control Codes,” Advances in Mathematics of Communications 1 (2007), 151-171.

[LSH] Little, J., Saints, K., and Heegard, C. “On the structure of Hermitian codes,” J. Pure Appl. Algebra 121 (1997), 293–314.

[MM] Matsui, H. and Mita, S. “Efficient encoding via Gröbner bases and discrete Fourier transforms for several kinds of algebraic codes,” accepted for proceedings of ISIT 2007, preprint: ArXiv:cs.IT/0703104.

[MOS] Matsumoto, R., Oishi, M., Sakaniwa, K. “Fast Encoding of Algebraic Geometry Codes,” IEICE Trans. Fundamentals, E84-A (2001), 2514– 2517.

[PH] Poli, A., and Huguet, L. Error Correcting Codes: Theory and Applications, Hemel Hempstead: Prentice Hall International, 1992.

[S] Stichtenoth, H. Algebraic Function Fields and Codes, Berlin: Springer Verlag, 1993.