In mathematics, an algebraic geometric code (AG-code), otherwise known as a Goppa code, is a general type of linear code constructed by using an algebraic curve
over a finite field
. Such codes were introduced by Valerii Denisovich Goppa. In particular cases, they can have interesting extremal properties, making them useful for a variety of error detection and correction problems.[1]
They should not be confused with binary Goppa codes that are used, for instance, in the McEliece cryptosystem.
Construction
Traditionally, an AG-code is constructed from a non-singular projective curve X over a finite field
by using a number of fixed distinct
-rational points on
:
![{\displaystyle {\mathcal {P}}:=\{P_{1},\ldots ,P_{n}\}\subset \mathbf {X} (\mathbb {F} _{q}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b381f9ed7233b392a8b5c5b3bbfdbaab2e75d063)
Let
be a divisor on X, with a support that consists of only rational points and that is disjoint from the
(i.e.,
).
By the Riemann–Roch theorem, there is a unique finite-dimensional vector space,
, with respect to the divisor
. The vector space is a subspace of the function field of X.
There are two main types of AG-codes that can be constructed using the above information.
Function code
The function code (or dual code) with respect to a curve X, a divisor
and the set
is constructed as follows.
Let
, be a divisor, with the
defined as above. We usually denote a Goppa code by C(D,G). We now know all we need to define the Goppa code:
![{\displaystyle C(D,G)=\left\{\left(f(P_{1}),\ldots ,f(P_{n})\right)\ :\ f\in L(G)\right\}\subset \mathbb {F} _{q}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb5a3f1f2fceeb7f4c04474cca7244e2f5c702aa)
For a fixed basis
for L(G) over
, the corresponding Goppa code in
is spanned over
by the vectors
![{\displaystyle \left(f_{i}(P_{1}),\ldots ,f_{i}(P_{n})\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e63b5727ec116ad3597869f492a65be53a41137)
Therefore,
![{\displaystyle {\begin{bmatrix}f_{1}(P_{1})&\cdots &f_{1}(P_{n})\\\vdots &&\vdots \\f_{k}(P_{1})&\cdots &f_{k}(P_{n})\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aee5875c771c201565f3dd93f0c9ee92d2484689)
is a generator matrix for
Equivalently, it is defined as the image of
![{\displaystyle {\begin{cases}\alpha :L(G)\to \mathbb {F} ^{n}\\f\mapsto (f(P_{1}),\ldots ,f(P_{n}))\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a763735810ed7c8334ceda23c8f00baa0268092)
The following shows how the parameters of the code relate to classical parameters of linear systems of divisors D on C (cf. Riemann–Roch theorem for more). The notation ℓ(D) means the dimension of L(D).
- Proposition A. The dimension of the Goppa code
is ![{\displaystyle k=\ell (G)-\ell (G-D).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ae9c3fd8edd028f3235618c65ee4a408c516f0)
Proof. Since
we must show that
![{\displaystyle \ker(\alpha )=L(G-D).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29b906071c2376e6ea05f6b414085ed237c4bc1b)
Let
then
so
. Thus,
Conversely, suppose
then
since
![{\displaystyle P_{i}<G,\quad i=1,\ldots ,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0262c8d480a21b753474532501f7c22cad940b54)
(G doesn't “fix” the problems with the
, so f must do that instead.) It follows that
- Proposition B. The minimal distance between two code words is
![{\displaystyle d\geqslant n-\deg(G).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/391102149cc25676ebab7571a492ebc6d15d6b0f)
Proof. Suppose the Hamming weight of
is d. That means that for
indices
we have
for
Then
, and
![{\displaystyle \operatorname {div} (f)+G-P_{i_{1}}-\cdots -P_{i_{n-d}}>0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce6b554ce7fc86fed75fa8517c867753ea0f03a1)
Taking degrees on both sides and noting that
![{\displaystyle \deg(\operatorname {div} (f))=0,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbeee5b4c9f57d799b410febc9c51f7a0500840d)
we get
![{\displaystyle \deg(G)-(n-d)\geqslant 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5db131828024c8bad16a2bd802da06b0663c2729)
so
![{\displaystyle d\geq n-\deg(G).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c91f4d816ef6761d351027b66a24c3188263dd9b)
Residue code
The residue code can be defined as the dual of the function code, or as the residue of some functions at the
's.
References
- Key One Chung, Goppa Codes, December 2004, Department of Mathematics, Iowa State University.
External links