Goppa code


Goppa code

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 mathbb{F}_q. 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"1, "P"2, ..., "P"n

of X defined over mathbb{F}_q, and let "G" be a divisor on "X" with a support that consists of only rational points and that is disjoint from the P_i's. By the Riemann-Roch theorem, 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) with respect to a curve X, a divisor G and the P_i's is constructed as follows.

For a fixed basis

:"f"1, "f"2, ..., "f"k

for "L"("G") over mathbb{F}_q, the corresponding Goppa code in mathbb{F}_q^n is spanned over mathbb{F}_q by the vectors

:("f""i"("P"1), "f""i"("P"2), ..., "f""i"("P"n)).

Equivalently, it is defined as the image of

:alpha : L(G) longrightarrow mathbb{F}^n,

where "f" is defined by f longmapsto (f(P_1), dots ,f(P_n)).

Let D = P_1 + P_2 + cdots + P_n be a divisor, with the P_i 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

:k = l(G) - l(G-D),

and the minimal distance between two code words is

:d geq n - deg(G).

Proof

Since

:C(D,G) cong L(G)/ker(alpha),

we must show that

:ker(alpha)=L(G-D) .

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

:mathrm{div}(f)> D

since

:P_i < G, i=1, dots ,n.

("G" doesn't “fix”the problems with the -D, so "f" must do that instead.) It followsthat

:f(P_i)=0, i=1, dots ,n.

To show that d geq n - deg(G), suppose the Hamming weight ofalpha(f) is "d". That means that f(P_i)=0 for n-d P_is, sayP_{i_1}, dots ,P_{i_{n-d. Then f in L(G-P_{i_1} - dots- P_{i_{n-d), and

:mathrm{div}(f)+G-P_{i_1} - dots - P_{i_{n-d> 0.

Taking degrees on both sides and noting that

:deg(mathrm{div}(f))=0,

we get

:deg(G)-(n-d) geq 0,

so

:d geq n - deg(G). Q.E.D.

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.

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

: {n^k} choose {log_2 n}

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

External links

* [http://upload.wikimedia.org/wikibooks/en/7/71/Algebraic_Geometric_Coding_Theory.pdf An undergraduate thesis on Algebraic Geometric Coding Theory]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Code De Goppa — En mathématiques et en théorie des codes correcteurs d erreur, les codes de Goppa, aussi appelé codes de géométrie algébrique, sont une généralisation des codes de Reed Solomon. Les codes de Goppa sont construits à partir d une courbe algébrique… …   Wikipédia en Français

  • Code de goppa — En mathématiques et en théorie des codes correcteurs d erreur, les codes de Goppa, aussi appelé codes de géométrie algébrique, sont une généralisation des codes de Reed Solomon. Les codes de Goppa sont construits à partir d une courbe algébrique… …   Wikipédia en Français

  • Code de géométrie algébrique — Code de Goppa En mathématiques et en théorie des codes correcteurs d erreur, les codes de Goppa, aussi appelé codes de géométrie algébrique, sont une généralisation des codes de Reed Solomon. Les codes de Goppa sont construits à partir d une… …   Wikipédia en Français

  • Code Correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Code — redirects here. CODE may also refer to Cultural Olympiad Digital Edition. Decoded redirects here. For the television show, see Brad Meltzer s Decoded. For code (computer programming), see source code. For other uses, see Code (disambiguation).… …   Wikipedia

  • Code de Goppa — En mathématiques et en théorie des codes correcteurs d erreur, les codes de Goppa, aussi appelé codes de géométrie algébrique, sont une généralisation des codes de Reed Solomon. Les codes de Goppa sont construits à partir d une courbe algébrique… …   Wikipédia en Français

  • Code correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Linear code — In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome… …   Wikipedia

  • Alternant code — In coding theory, alternant codes form a class of parameterised error correcting codes which generalise the BCH codes.DefinitionAn alternant code over GF( q ) of length n is defined by a parity check matrix H of alternant form H i , j = αji y i …   Wikipedia

  • Error correction code — Code correcteur Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie …   Wikipédia en Français