In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an algebraic geometric code (AG-code), otherwise known as a Goppa code, is a general type of
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
constructed by using an
algebraic curve
In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane c ...
over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
. 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
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...
problems.
They should not be confused with
binary Goppa code In mathematics and computer science, the binary Goppa code is an error-correcting code that belongs to the class of general Goppa codes originally described by Valerii Denisovich Goppa, but the binary structure gives it several mathematical advan ...
s that are used, for instance, in the
McEliece cryptosystem
In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in ...
.
Construction
Traditionally, an AG-code is constructed from a
non-singular
In the mathematical field of algebraic geometry, a singular point of an algebraic variety is a point that is 'special' (so, singular), in the geometric sense that at this point the tangent space at the variety may not be regularly defined. In cas ...
projective curve
In algebraic geometry, a projective variety over an algebraically closed field ''k'' is a subset of some projective ''n''-space \mathbb^n over ''k'' that is the zero-locus of some finite family of homogeneous polynomials of ''n'' + 1 variables ...
X over a finite field
by using a number of fixed distinct
-
rational points
In number theory and algebraic geometry, a rational point of an algebraic variety is a point whose coordinates belong to a given field. If the field is not mentioned, the field of rational numbers is generally understood. If the field is the fiel ...
on
:
:
Let
be a
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
on X, with a
support
Support may refer to:
Arts, entertainment, and media
* Supporting character
Business and finance
* Support (technical analysis)
* Child support
* Customer support
* Income Support
Construction
* Support (structure), or lateral support, a ...
that consists of only rational points and that is disjoint from the
(i.e.,
).
By the
Riemann–Roch theorem
The Riemann–Roch theorem is an important theorem in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeros and allowed poles. It rel ...
, 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
In coding theory, the dual code of a linear code
:C\subset\mathbb_q^n
is the linear code defined by
:C^\perp = \
where
:\langle x, c \rangle = \sum_^n x_i c_i
is a scalar product. In linear algebra terms, the dual code is the annihilator ...
) 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:
:
For a fixed basis
for ''L''(''G'') over
, the corresponding Goppa code in
is spanned over
by the vectors
:
Therefore,
:
is a generator matrix for
Equivalently, it is defined as the image of
:
The following shows how the parameters of the code relate to classical parameters of
linear systems of divisors
In algebraic geometry, a linear system of divisors is an algebraic generalization of the geometric notion of a family of curves; the dimension of the linear system corresponds to the number of parameters of the family.
These arose first in the fo ...
''D'' on ''C'' (cf.
Riemann–Roch theorem
The Riemann–Roch theorem is an important theorem in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeros and allowed poles. It rel ...
for more). The notation ''ℓ''(''D'') means the dimension of ''L''(''D'').
:Proposition A. The dimension of the Goppa code
is
Proof. Since
we must show that
:
Let
then
so
. Thus,
Conversely, suppose
then
since
:
(''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
Proof. Suppose the
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
of
is ''d''. That means that for
indices
we have
for
Then
, and
:
Taking degrees on both sides and noting that
:
we get
:
so
:
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
{{Reflist
* Key One Chung, ''Goppa Codes'', December 2004, Department of Mathematics, Iowa State University.
External links
An undergraduate thesis on Algebraic Geometric Coding TheoryGoppa Codes by Key One Chung
Coding theory
Algebraic curves
Finite fields
Articles containing proofs