Goppa code - AbsoluteAstronomy.com

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, an algebraic geometric code (AG-code), otherwise known as a Goppa code, is a general type of linear code

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 a hybrid of these two types. Linear codes allow for...

constructed by using an algebraic curve

Algebraic curve

In algebraic geometry, an algebraic curve is an algebraic variety of dimension one. The theory of these curves in general was quite fully developed in the nineteenth century, after many particular examples had been considered, starting with circles and other conic sections.- Plane algebraic curves...

over a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

. Such codes were introduced by Valerii Denisovich Goppa

Valerii Denisovich Goppa

Valery Denisovich Goppa is a Soviet and Russian mathematician.He discovered the relation between algebraic geometry and codes. Today these codes are called Goppa codes. In 1981 he presented his discovery at the algebra seminar of the Moscow State University...

. In particular cases, they can have interesting extremal properties. They should not be confused with binary Goppa codes that are used, for instance, in the McEliece cryptosystem

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...

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

:= {P₁, P₂, ..., P_n} ⊂ X (

) on X.

Let G be a divisor

Divisor (algebraic geometry)

In algebraic geometry, divisors are a generalization of codimension one subvarieties of algebraic varieties; two different generalizations are in common use, Cartier divisors and Weil divisors...

on X, with a support

Support (mathematics)

In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set . This concept is used very widely in mathematical analysis...

that consists of only rational points and that is disjoint from the

's.
Thus

∩ supp(G) = Ø

By the Riemann-Roch theorem, there is a unique finite-dimensional vector space,

, with respect to the divisor G. The vector space is a subspace of the function field

Function field

Function field may refer to:*Function field of an algebraic variety*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 G 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:

C(D,G) = {(f(P₁), ..., f(P_n))|f

L(G)}⊂

For a fixed basis

f₁, f₂, ..., f_k

for L(G) over

, the corresponding Goppa code in

is spanned over

by the vectors
, f_i(P₂), ..., f_i(P_n)).
Therefore

is a generator matrix for C(D,G)

Equivalently, it is defined as the image of

,

where f is defined by

.

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

Riemann–Roch theorem

The Riemann–Roch theorem is an important tool in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeroes and allowed poles...

for more). The notation l(D) means the dimension of L(D).

Proposition A The dimension of the Goppa code C(D,G) is

,

Proposition B The minimal distance between two code words is

.

Proof A

Since

we must show that

.

Suppose

. Then

, so

. Thus,

.
Conversely, suppose

.
Then

since

.

(G doesn't “fix”
the problems with the

, so f must do that instead.) It follows
that

.
Proof B

To show that

, suppose the Hamming weight

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 bits, this is the number of 1's in the string...