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 [math]\displaystyle{ X }[/math] over a finite field [math]\displaystyle{ \mathbb{F}_q }[/math]. Such codes were introduced by Valerii Denisovich Goppa. In particular cases, they can have interesting extremal properties, making them useful for a variety of error detection and correction problems.[1]
They should not be confused with binary Goppa codes that are used, for instance, in the McEliece cryptosystem.
Construction
Traditionally, an AG-code is constructed from a non-singular projective curve X over a finite field [math]\displaystyle{ \mathbb{F}_q }[/math] by using a number of fixed distinct [math]\displaystyle{ \mathbb{F}_q }[/math]-rational points on [math]\displaystyle{ \mathbf{X} }[/math]:
- [math]\displaystyle{ \mathcal{P}:= \{P_1, \ldots, P_n \} \subset \mathbf{X} (\mathbb{F}_q). }[/math]
Let [math]\displaystyle{ G }[/math] be a divisor on X, with a support that consists of only rational points and that is disjoint from the [math]\displaystyle{ P_i }[/math] (i.e., [math]\displaystyle{ \mathcal{P} \cap \operatorname{supp}(G) = \varnothing }[/math]).
By the Riemann–Roch theorem, there is a unique finite-dimensional vector space, [math]\displaystyle{ L(G) }[/math], with respect to the divisor [math]\displaystyle{ G }[/math]. 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 [math]\displaystyle{ G }[/math] and the set [math]\displaystyle{ \mathcal{P} }[/math] is constructed as follows.
Let [math]\displaystyle{ D = P_1 + \cdots + P_n }[/math], be a divisor, with the [math]\displaystyle{ P_i }[/math] defined as above. We usually denote a Goppa code by C(D,G). We now know all we need to define the Goppa code:
- [math]\displaystyle{ C(D, G) = \left \{ \left (f(P_1), \ldots, f(P_n) \right ) \ : \ f \in L(G) \right \} \subset \mathbb{F}_q^n }[/math]
For a fixed basis [math]\displaystyle{ f_1, \ldots, f_k }[/math] for L(G) over [math]\displaystyle{ \mathbb{F}_q }[/math], the corresponding Goppa code in [math]\displaystyle{ \mathbb{F}_q^n }[/math] is spanned over [math]\displaystyle{ \mathbb{F}_q }[/math] by the vectors
- [math]\displaystyle{ \left (f_i(P_1), \ldots, f_i(P_n) \right ) }[/math]
Therefore,
- [math]\displaystyle{ \begin{bmatrix} f_1(P_1) & \cdots & f_1(P_n) \\ \vdots & & \vdots \\ f_k(P_1) & \cdots & f_k(P_n) \end{bmatrix} }[/math]
is a generator matrix for [math]\displaystyle{ C(D, G). }[/math]
Equivalently, it is defined as the image of
- [math]\displaystyle{ \begin{cases} \alpha : L(G) \to \mathbb{F}^n \\ f \mapsto (f(P_1), \ldots ,f(P_n)) \end{cases} }[/math]
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 ℓ(D) means the dimension of L(D).
- Proposition A. The dimension of the Goppa code [math]\displaystyle{ C(D, G) }[/math] is [math]\displaystyle{ k = \ell(G) - \ell(G-D). }[/math]
Proof. Since [math]\displaystyle{ C(D,G) \cong L(G)/\ker(\alpha), }[/math] we must show that
- [math]\displaystyle{ \ker(\alpha)=L(G-D). }[/math]
Let [math]\displaystyle{ f \in \ker(\alpha) }[/math] then [math]\displaystyle{ f(P_1)=\cdots=f(P_n) =0 }[/math] so [math]\displaystyle{ \operatorname{div}(f) \gt D }[/math]. Thus, [math]\displaystyle{ f \in L(G-D). }[/math] Conversely, suppose [math]\displaystyle{ f \in L(G-D), }[/math] then [math]\displaystyle{ \operatorname{div}(f)\gt D }[/math] since
- [math]\displaystyle{ P_i \lt G, \quad i=1, \ldots ,n. }[/math]
(G doesn't “fix” the problems with the [math]\displaystyle{ -D }[/math], so f must do that instead.) It follows that [math]\displaystyle{ f(P_1)=\cdots = f(P_n) = 0. }[/math]
- Proposition B. The minimal distance between two code words is [math]\displaystyle{ d \geqslant n - \deg(G). }[/math]
Proof. Suppose the Hamming weight of [math]\displaystyle{ \alpha(f) }[/math] is d. That means that for [math]\displaystyle{ n-d }[/math] indices [math]\displaystyle{ i_1, \ldots, i_{n-d} }[/math] we have[math]\displaystyle{ f(P_{i_k})=0 }[/math] for [math]\displaystyle{ k \in \{1, \ldots, n-d\}. }[/math] Then [math]\displaystyle{ f \in L(G-P_{i_1} - \cdots - P_{i_{n-d}}) }[/math], and
- [math]\displaystyle{ \operatorname{div}(f)+G-P_{i_1} - \cdots - P_{i_{n-d}}\gt 0. }[/math]
Taking degrees on both sides and noting that
- [math]\displaystyle{ \deg(\operatorname{div}(f))=0, }[/math]
we get
- [math]\displaystyle{ \deg(G)-(n-d) \geqslant 0. }[/math]
so
- [math]\displaystyle{ d \geq n - \deg(G). }[/math]
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]\displaystyle{ P_i }[/math]'s.
References
- Key One Chung, Goppa Codes, December 2004, Department of Mathematics, Iowa State University.
External links
 |
