HOME

TheInfoList



OR:

In 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 ...
X 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, sub ...
\mathbb_q. 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 codes that are used, for instance, in the McEliece cryptosystem.


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 c ...
projective curve X over a finite field \mathbb_q by using a number of fixed distinct \mathbb_q-
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 \mathbf: :\mathcal:= \ \subset \mathbf (\mathbb_q). Let G 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 P_i (i.e., \mathcal \cap \operatorname(G) = \varnothing). 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 re ...
, there is a unique finite-dimensional vector space, L(G), with respect to the divisor G. 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 G and the set \mathcal is constructed as follows. Let D = P_1 + \cdots + P_n, be a divisor, with the P_i defined as above. We usually denote a Goppa code by C(D,G). We now know all we need to define the Goppa code: :C(D, G) = \left \ \subset \mathbb_q^n For a fixed basis f_1, \ldots, f_k for ''L''(''G'') over \mathbb_q, the corresponding Goppa code in \mathbb_q^n is spanned over \mathbb_q by the vectors :\left (f_i(P_1), \ldots, f_i(P_n) \right ) Therefore, : \begin f_1(P_1) & \cdots & f_1(P_n) \\ \vdots & & \vdots \\ f_k(P_1) & \cdots & f_k(P_n) \end is a generator matrix for C(D, G). Equivalently, it is defined as the image of :\begin \alpha : L(G) \to \mathbb^n \\ f \mapsto (f(P_1), \ldots ,f(P_n)) \end 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 f ...
''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 re ...
for more). The notation ''ℓ''(''D'') means the dimension of ''L''(''D''). :Proposition A. The dimension of the Goppa code C(D, G) is k = \ell(G) - \ell(G-D). Proof. Since C(D,G) \cong L(G)/\ker(\alpha), we must show that :\ker(\alpha)=L(G-D). Let f \in \ker(\alpha) then f(P_1)=\cdots=f(P_n) =0 so \operatorname(f) > D . Thus, f \in L(G-D). Conversely, suppose f \in L(G-D), then \operatorname(f)> D since :P_i < G, \quad i=1, \ldots ,n. (''G'' doesn't “fix” the problems with the -D, so ''f'' must do that instead.) It follows that f(P_1)=\cdots = f(P_n) = 0. :Proposition B. The minimal distance between two code words is d \geqslant n - \deg(G). 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 of ...
of \alpha(f) is ''d''. That means that for n-d indices i_1, \ldots, i_ we havef(P_)=0 for k \in \. Then f \in L(G-P_ - \cdots - P_), and :\operatorname(f)+G-P_ - \cdots - P_> 0. Taking degrees on both sides and noting that :\deg(\operatorname(f))=0, we get :\deg(G)-(n-d) \geqslant 0. so :d \geq n - \deg(G).


Residue code

The residue code can be defined as the dual of the function code, or as the residue of some functions at the P_i'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 Theory

Goppa Codes by Key One Chung
Coding theory Algebraic curves Finite fields Articles containing proofs