Francais | English | Espanõl

From Wikipedia, the free encyclopedia

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 X over a finite field <math>\mathbb{F}_q</math>. Such codes were introduced by V. D. Goppa. In particular cases, they can have interesting extremal properties.

Traditionally, an AG-code can be constructed from a non-singular projective curve X by using a number of fixed rational points

P₁, P₂, ..., P_n

of X defined over <math>\mathbb{F}_q</math>, and let G be a divisor on X with a support that consists of only rational points and that is disjoint from the <math>P_i</math>'s. By the Riemann-Roch theorem, there is a unique finite-dimensional vector space, <math>L(G)</math>, with respect to the divisor G. The vector space is a subspace of the function field of <math>X</math>.

There are two main types of AG-codes that can be constructed using the above information

Contents 1 Function Code 2 Residue Code 3 Applications 4 Links

[edit] Function Code

The function code (or dual code) with respect to a curve X, a divisor G and the <math>P_i</math>'s is constructed as follows.

For a fixed basis

f₁, f₂, ..., f_k

for L(G) over <math>\mathbb{F}_q</math>, the corresponding Goppa code in <math>\mathbb{F}_q^n</math> is spanned over <math>\mathbb{F}_q</math> by the vectors

(f_i(P₁), f_i(P₂), ..., f_i(P_n)).

Equivalently, it is defined as the image of

<math>\alpha : L(G) \longrightarrow \mathbb{F}^n</math>,

where f is defined by <math>f \longmapsto (f(P_1), \dots ,f(P_n))</math>.

Let <math>D = P_1 + P_2 + \cdots + P_n</math> be a divisor, with the <math> P_i </math> defined as above. We usually denote a Goppa code by C(D,G).

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 l(D) means the dimension of L(D).

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

<math>k = l(G) - l(G-D)</math>,

and the minimal distance between two code words is

<math>d \geq n - \deg(G)</math>.

Proof

Since

<math>C(D,G) \cong L(G)/\ker(\alpha), </math>

we must show that

<math>\ker(\alpha)=L(G-D) </math>.

Suppose <math>f \in \ker(\alpha)</math>. Then <math>f(P_i)=0, i=1, \dots ,n</math>, so <math>\mathrm{div}(f) > D </math>. Thus, <math>f \in L(G-D)</math>. Conversely, suppose <math>f \in L(G-D)</math>. Then

<math>\mathrm{div}(f)> D</math>

since

<math>P_i < G, i=1, \dots ,n</math>.

(G doesn't “fix” the problems with the <math>-D</math>, so f must do that instead.) It follows that

<math>f(P_i)=0, i=1, \dots ,n</math>.

To show that <math>d \geq n - \deg(G)</math>, suppose the Hamming weight of <math>\alpha(f)</math> is d. That means that <math>f(P_i)=0</math> for <math>n-d</math> <math>P_i</math>s, say <math>P_{i_1}, \dots ,P_{i_{n-d}}</math>. Then <math>f \in L(G-P_{i_1} - \dots - P_{i_{n-d}})</math>, and

<math>\mathrm{div}(f)+G-P_{i_1} - \dots - P_{i_{n-d}}> 0</math>.

Taking degrees on both sides and noting that

<math>\deg(\mathrm{div}(f))=0</math>,

we get

<math>\deg(G)-(n-d) \geq 0</math>,

so

<math>d \geq n - \deg(G)</math>. Q.E.D.

[edit] Residue Code

The residue code can be defined as the dual of the function code, or as the residue of some functions at the <math>P_i</math>'s.

[edit] Applications

In cryptography, Goppa codes are used in the McEliece cryptosystem.

In general, Goppa codes are considered 'good' linear codes, in that they permit the correction of

<math> {n^k} \choose {\log_2 n}</math>

errors. Also their decoding is easy, using the Euclidean algorithm and Berlekamp-Massey algorithm, in particular.

[edit] Links

An undergraduate thesis on Algebraic Geometric Coding Theoryfr:Code de Goppa no:Goppa-kode