Goppa code

Encyclopedia : G : GO : GOP : 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_q]. Such codes were introduced by V. D. Goppa. In particular cases, they can have interesting extremal properties.

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

P₁, P₂, ..., P_n

are fixed among the points of X defined over [\mathbb_q], and that G is a divisor 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_q], bounds the divisor made up of the zeroes and poles of f, counted with appropriate multiplicity.

Then, for a fixed basis

f₁, f₂, ..., f_k

for L(G) over [\mathbb_q], the corresponding Goppa code in [\mathbb_q^n] is spanned over [\mathbb_q] by the vectors

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

Equivalently, it is defined as the image of

[\alpha : L(G) \longrightarrow \mathbb^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(f) > D ]. Thus, [f \inL(G-D)]. Conversely, suppose [f \in L(G-D)]. Then

[\mathrm(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_i]s, say [P_, \dots ,P_}]. Then [f \in L(G-P_ - \dots- P_})], and

[\mathrm(f)+G-P_ - \dots - P_}> 0].

Taking degrees on both sides and noting that

[\deg(\mathrm(f))=0],

we get

[\deg(G)-(n-d) \geq 0],

[d \geq n - \deg(G)]. Q.E.D.

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

[ \choose ]

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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.