Affine Variety Codes

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 17, March 14 Scribe: Jennifer van der Horst

Let q be a power of a prime number. Denote by ${\mathbb F}_{q}$ be the finite field of q elements and $\overline{\mathbb F}_q$ the algebraic closure of ${\mathbb F}_{q}$. We know that, for $a \in \overline{\mathbb F}_q$, $a \in {\mathbb F}_{q}$ iff a^q - a = 0.

Let I be a radical ideal in ${\mathbb F}_{q}[x_1, \dots, x_s]$ with $x_i^{q}-x_i \in {\mathbf I}$ for $1 \leq i \leq s$. Then any common solution $P =(a_1, \cdots, a_s)$ of I in $\overline{\mathbb F}_q^s$must have coordinates in ${\mathbb F}_{q}$, as $x_i^{q}-x_i \in {\mathbf I}$ implies that a_i^q -a_i=0, $1 \leq i \leq s$. Hence $V({\mathbf I}) \subseteq {\mathbb F}_{q}^s$, say

$$V({\mathbf I}) = \{P_1, \dots, P_n\} \subseteq {\mathbb F}_{q}^s.$$

Let B =B(I) be the monomial basis of I under some monomial order. Then

|V(I)| = |B(I)|.

Let

$$R = {\mathbb F}_{q}[x_1,\dots,x_s]/{\mathbf I}.$$

We know from Lemma 11.5 that the congruence classes in R are represented by polynomials in $\mbox{Span}(B)$, so we identify R with $\mbox{Span}(B)$. The Fourier transform gives the ring isomorphism

$$\begin{eqnarray*}& & R \rightarrow {\mathbb F}_{q}^n\\ & & f \mapsto (f(P_1), \cdots, f(P_n)). \end{eqnarray*}$$

This follows from Theorem 13.4 (note that this theorem holds for an algebraically closed field ${\mathbb F}$, but its proof needs only the fact that all the common solutions of I have coordinates in ${\mathbb F}$).

Let L be a linear subspace of R over ${\mathbb F}_{q}$ of dimension k. Define a linear code in ${\mathbb F}_{q}^n$ as follows:

$$C({\mathbf I},L) = \{(f(P_1),\dots,f(P_n)): f\in L\},$$

that is, C(I,L) is the image of L under the Fourier transform. Then C(I,L) is an [n,k,d] linear code over ${\mathbb F}_{q}$ for some d, and is called an affine variety code.

Special Codes.

(1) Reed-Solomon Codes. Let ${\mathbf I}= \left<x^{q}-x\right> \subseteq {\mathbb F}_{q}[x]$. Then

$$\begin{eqnarray*}B & = & \{0,1,\dots,q-1\}\\ V({\mathbf I}) & = & {\mathbb F}_{q}= \{ 0, 1,\alpha, \alpha^2, \dots, \alpha^{q - 2}\}, \end{eqnarray*}$$

where $\alpha$ is a primitive element in ${\mathbb F}_{q}$, and

$$R = {\mathbb F}_{q}[x]/{\mathbf I}= \mbox{Span}(B) = \left\{\sum_{i=0}^{q-1}a_ix^i: a_i \in {\mathbb F}_{q}\right\}.$$

For $1\leq{k}\leq{n}$, let

$$L_k = \mbox{Span}(0,1,\dots,k-1) = \left\{\sum_{i=0}^{k-1}a_ix^i:a_i \in {\mathbb F}_{q}\right\}.$$

Then the code C(I,L_k) is a Reed-Solomon code with length n=q, dimension k, and distance d=n-k+1. That is,

$$C(I,L_k) = \{(f(0), f(1),f(\alpha),\dots,f(\alpha^{q-2})): f \in {\mathbb F}_{q}[x], \deg(f) \leq {k-1}\}$$

is a [q, k, q -k+1] linear code over ${\mathbb F}_{q}$.

(2) Reed-Muller Codes. let

$${\mathbf I}= \left<x_1^{q}-x_1,\dots,x_s^{q} -x_s\right> \subseteq {\mathbb F}_{q}[x_1,\dots,x_s].$$

Then

$$\begin{eqnarray*}B & = & \{(i_1,\dots,i_s): 0\leq i_j \leq q-1, 1 \leq j \leq s\... ... \{ (a_1,\dots,a_s): a_j \in {\mathbb F}_{q}, 1 \leq j \leq s\}. \end{eqnarray*}$$

Hence n = |V(I)| = q^s. For $1\leq r\leq s(q-1)$, define

$$L_r = \{f \in \mbox{Span}(B):\deg(f)\leq r\}.$$

Then C(I,L_r) is a (generalized) Reed-Muller code of order r over ${\mathbb F}_{q}$with

$$\begin{eqnarray*}n & = & q^s,\\ k & = &\sum_{i=0}^{r} \sum_{j=0}^{s} (-1)^j {s... ...oose j} {i-jq+s-1 \choose i-jq},\\ d & = & (q-r_0) q^{s-r_1-1} \end{eqnarray*}$$

where r= r₁ (q-1) + r₀ with $0 \leq r_0 < q-1$.

(3) Hermitian Codes. Suppose q is a square, say q = v². Let

$${\mathbf I}= \left<x^q-x, y^q-y, y^v+y-x^{v+1}\right> \subseteq {\mathbb F}_{q}[x,y].$$

Then V(I) consists of all points $(\alpha,\beta)\in{\mathbb F}_{q}^2$ such that

$$\alpha^{v+1} = \beta^v+\beta.$$ (24)

The above equation defines a Hermitian curve. Note that for $\alpha, \beta \in {\mathbb F}_{v^2}$,

$$\begin{eqnarray*}\alpha^{v+1} & = & \mbox{Norm}_{{\mathbb F}_{v^2}\mid {\mathbb ... ... {{\mathbb F}_{v^2} \mid {\mathbb F}_v}(\beta)\in {\mathbb F}_v. \end{eqnarray*}$$

The trace map is a surjective linear map from ${\mathbb F}_{v^2}$ to ${\mathbb F}_v$, so for every $\alpha \in {\mathbb F}_{q}$ there are exactly v elements $\beta \in {\mathbb F}_{q}$ satisfying (25). Hence $n=\vert V({\mathbf I})\vert = v^2\cdot v = v^3$.

We define the weighted degree of a monomial xⁱy^j to be vi+(v+1)j and the weighted degree of a polynomial $f \in {\mathbb F}_{q}[x,y]$ the greatest weighted degree among the nonzero monomials in f. For $1 \leq r \leq v^3 + v^2 -v -2$, define a linear subspace in $R = {\mathbb F}_{q}[x,y]/{\mathbf I}$ as follows

$$L_r = \{f \in {\mathbb F}_{q}[x,y]:\ \mbox{ the weighted degree of } f \leq r\}.$$

The code C(I,L_r) is a Hermitian code with

$$n=v^3, \ \ \ k=r-\frac{v(v-1)}{2}+1, \ \ \ d\geq n-r.$$

The next theorem says that affine variety codes include all linear codes.

Theorem 17.1   Every linear code over ${\mathbb F}_{q}$ can be represented as an affine variety code.

Proof. Let C be an [n,k,d] linear code over ${\mathbb F}_{q}$ with a generator matrix G=(c_ij) where $c_{ij} \in {\mathbb F}_{q}$, $1 \leq i \leq k$, $1 \leq j \leq n$. Choose an integer s such that $q^s \geq n$. Take n distinct points $P_1, \cdots, P_n$ in ${\mathbb F}_{q}^s$ and let I denote the ideal

$${\mathbf I}= \{f \in {\mathbb F}_{q}[x_1,\cdots, x_s]: f(P_i) =0, 1 \leq i \leq n\}.$$

We know there are polynomials $f_1, \cdots, f_n \in {\mathbb F}_{q}[x_1,\cdots, x_s]$such that

$$f_i(P_j) = \left\{ \begin{array}{ll} 1 & \mbox{if $i=j$,}\\ 0 & \mbox{if $i\ne j$.} \end{array} \right.$$

Define k new functions $g_1, \cdots, g_k \in {\mathbb F}_{q}[x_1,\cdots, x_s]$ as follows

$$g_i = \sum_{j=1}^{n} c_{ij} g_j, \ \ \ 1 \leq i \leq k.$$

Let L be the linear subspace of $R= {\mathbb F}_{q}[x_1,\cdots, x_s]/{\mathbf I}$ spanned by $g_1, \cdots, g_k$ over ${\mathbb F}_{q}$.

We claim that the affine variety code C(I,L) is equal to the code C we started with. To see this, note that

$$g_i(P_j) = c_{ij}, \ \ \ 1 \leq i \leq k, \ \ 1 \leq j \leq n.$$

The Fourier transform sends g_i to the vector $(c_{i1}, \cdots, c_{in})$, which is the i-th row of G. An arbitrary element in L is a linear combination of $g_1, \cdots, g_k$ over ${\mathbb F}_{q}$, so its Fourier transform is a linear combination of the rows of G, that is, a code word in C. Conversely, a code word in Cis a linear combination of the rows of G, so can be obtained via the Fourier transform from the corresponding combination of $g_1, \cdots, g_k$. This proves that C= C(I,L). $\Box$