Reed–Solomon codes

Algebraic geometry codes are a generalization of Reed–Solomon codes. Constructed by Irving Reed and Gustave Solomon in 1960, Reed–Solomon codes use univariate polynomials to form codewords, by evaluating polynomials of sufficiently small degree at the points in a finite field ${\displaystyle \mathbb {F} _{q}}$.^[8]

Formally, Reed–Solomon codes are defined in the following way. Let ${\displaystyle \mathbb {F} _{q}=\{\alpha _{1},\dots ,\alpha _{q}\}}$. Set positive integers ${\displaystyle k\leq n\leq q}$. Let

$${\displaystyle \mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}}$$

The Reed–Solomon code ${\displaystyle RS(q,n,k)}$ is the evaluation code

$${\displaystyle RS(q,n,k)=\left\{\left(f(\alpha _{1}),f(\alpha _{2}),\dots ,f(\alpha _{n})\right):f\in \mathbb {F} _{q}[x]_{<k}\right\}\subseteq \mathbb {F} _{q}^{n}.}$$

Codes from algebraic curves

Goppa observed that ${\displaystyle \mathbb {F} _{q}}$ can be considered as an affine line, with corresponding projective line ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$. Then, the polynomials in ${\displaystyle \mathbb {F} _{q}[x]_{<k}}$ (i.e. the polynomials of degree less than ${\displaystyle k}$ over ${\displaystyle \mathbb {F} _{q}}$) can be thought of as polynomials with pole allowance no more than ${\displaystyle k}$ at the point at infinity in ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$.^[6]

With this idea in mind, Goppa looked toward the Riemann–Roch theorem. The elements of a Riemann–Roch space are exactly those functions with pole order restricted below a given threshold,^[9] with the restriction being encoded in the coefficients of a corresponding divisor. Evaluating those functions at the rational points on an algebraic curve ${\displaystyle X}$ over ${\displaystyle \mathbb {F} _{q}}$ (that is, the points in ${\displaystyle \mathbb {F} _{q}^{2}}$ on the curve ${\displaystyle X}$) gives a code in the same sense as the Reed-Solomon construction.

However, because the parameters of algebraic geometry codes are connected to algebraic function fields, the definitions of the codes are often given in the language of algebraic function fields over finite fields.^[10] Nevertheless, it is important to remember the connection to algebraic curves, as this provides a more geometrically intuitive method of thinking about AG codes as extensions of Reed-Solomon codes.^[9]

Formally, algebraic geometry codes are defined in the following way.^[10] Let ${\displaystyle F/\mathbb {F} _{q}}$ be an algebraic function field, ${\displaystyle D=P_{1}+\dots +P_{n}}$ be the sum of ${\displaystyle n}$ distinct places of ${\displaystyle F/\mathbb {F} _{q}}$ of degree one, and ${\displaystyle G}$ be a divisor with disjoint support from ${\displaystyle D}$. The algebraic geometry code ${\displaystyle C_{\mathcal {L}}(D,G)}$ associated with divisors ${\displaystyle D}$ and ${\displaystyle G}$ is defined as

$${\displaystyle C_{\mathcal {L}}(D,G):=\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(G)\rbrace \subseteq \mathbb {F} _{q}^{n}.}$$

More information on these codes may be found in both introductory texts^[6] as well as advanced texts on coding theory.^[10][11]

Reed-Solomon codes

One can see that

${\displaystyle RS(q,n,k)={\mathcal {C}}_{\mathcal {L}}(D,(k-1)P_{\infty })}$

where ${\displaystyle P_{\infty }}$ is the point at infinity on the projective line ${\displaystyle \mathbb {P} _{\mathbb {F} _{q}}^{1}}$ and ${\displaystyle D=P_{1}+\dots +P_{q}}$ is the sum of the other ${\displaystyle \mathbb {F} _{q}}$-rational points.

One-point Hermitian codes

The Hermitian curve is given by the equation

$${\displaystyle x^{q+1}=y^{q}+y}$$

considered over the field ${\displaystyle \mathbb {F} _{q^{2}}}$.^[2] This curve is of particular importance because it meets the Hasse–Weil bound with equality, and thus has the maximal number of affine points over ${\displaystyle \mathbb {F} _{q^{2}}}$.^[12] With respect to algebraic geometry codes, this means that Hermitian codes are long relative to the alphabet they are defined over.^[13] The Riemann–Roch space of the Hermitian function field is given in the following statement.^[2] For the Hermitian function field ${\displaystyle \mathbb {F} _{q^{2}}(x,y)}$ given by ${\displaystyle x^{q+1}=y^{q}+y}$ and for ${\displaystyle m\in \mathbb {Z} ^{+}}$, the Riemann–Roch space ${\displaystyle {\mathcal {L}}(mP_{\infty })}$ is

$${\displaystyle {\mathcal {L}}(mP_{\infty })=\left\langle x^{a}y^{b}:0\leq b\leq q-1,aq+b(q+1)\leq m\right\rangle ,}$$

where ${\displaystyle P_{\infty }}$ is the point at infinity on ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$.

With that, the one-point Hermitian code can be defined in the following way. Let ${\displaystyle {\mathcal {H}}_{q}}$ be the Hermitian curve defined over ${\displaystyle \mathbb {F} _{q^{2}}}$.

Let ${\displaystyle P_{\infty }}$ be the point at infinity on ${\displaystyle {\mathcal {H}}_{q}(\mathbb {F} _{q^{2}})}$, and

$${\displaystyle D=P_{1}+\cdots +P_{n}}$$

be a divisor supported by the ${\displaystyle n:=q^{3}}$ distinct ${\displaystyle \mathbb {F} _{q^{2}}}$-rational points on ${\displaystyle {\mathcal {H}}_{q}}$ other than ${\displaystyle P_{\infty }}$.

The one-point Hermitian code ${\displaystyle C(D,mP_{\infty })}$ is

${\displaystyle C(D,mP_{\infty }):=\left\lbrace (f(P_{1}),\dots ,f(P_{n})):f\in {\mathcal {L}}(mP_{\infty })\right\rbrace \subseteq \mathbb {F} _{q^{2}}^{n}.}$