Goppa code

In mathematics, 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 property.

In detail, assume that X is non-singular, that a number of points

: P 1, P 2, ..., P n

are fixed among the points of X defined over mathbb{F}_q, and that G is a divisor (algebraic geometry) on X , also defined over F . There is a finite-dimensional subspace L ( G ) of the function field of X , consisting of the rational functions f on X with zeroes and poles subject to G . This means that G , which is a formal sum of points of X over the algebraic closure of mathbb{F}_q, bounds the divisor made up of the zeroes and poles of f , counted with appropriate multiplicity.

Then, 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 ).

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 deg(G).

Proof. C(D,G) cong L(G)/ker(alpha) , so 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 in L(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 follows that f(P_i)=0, i=1, dots ,n.

To show that d geq n - deg(G), suppose the Hamming weight of alpha(f) is d . That means that f(P_i)=0 for n-d P_is, say P_{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.

=Application=

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