Algebraic--Geometric Codes (AG--codes) are a family of linear codes described by Goppa in [Gop81a], [Gop81b]. Let Chi be an irreducible projective plane curve of genus g, defined by a (absolutely irreducible) homogeneous polynomial H(X, Y, Z) over a finite field K=setF_q. A place of Chi is the maximal ideal of a discrete valuation subring of Bar(K)(Chi). We denote by v_P the valuation at place P. Its degree is the degree of its residue class field over K. A divisor is an element D of the free abelian group over the set of places of Chi. Namely, such an element can be written additively: D = sum_(P in Places(Chi))n_P⋅P, where all but finitely many n_P in Z are zero. The set of places with nonzero multiplicity is the support of D, denoted by Supp D. The set of divisors can be equipped with a natural partial order <= defined by:
D = sum_(P in Places(Chi)) n_P ⋅P <= D' = sum_(P in Places(Chi)) n'_P ⋅P iff n_P <= n'_P for all P.
If f in K(Chi), then one can define the principal divisor: (f) = sum_(P in Places(Chi))v_P(f)⋅P. A divisor D is said to be defined over K if it is stable under the natural action of Gal(Bar(K)/K).
If (P_1, ..., P_n) is a tuple of places of degree 1, then for a function f in K(Chi), f(P_i) can be seen as an element of K. If D is a divisor defined over K, then the Riemann--Roch space RieRoch(D) of D is the K-vector space of dimension k:
RieRoch(D) = { f in K(Chi)^ * | (f) + D >= 0 } union { 0 }.
Now provided D has support disjoint from S = { P_1, ..., P_n}, we can define the algebraic geometric code to be the [n, k]_q-code:
C = AGcode(S, D) = { (f(P_1), ..., f(P_n)), f in RieRoch(D) }.
If < f_1, ..., f_k > is a base of RieRoch_K(D) as a K-vector space, then a generator matrix for C is: G = pmatrix( f_1(P_1) & ... & f_1(P_n)cr vdots & ddots & vdots cr f_k(P_1) & ... & f_k(P_n)cr). Standard references are [Sti93] and [TV91].
There are two different implementations of the construction of AG--Codes in Magma. The first was implemented by Lancelot Pecquet and is based on the work of Hache [HLB95], [Hac96]. The second approach exploits the divisor machinery for function fields implemented by Florian Hess. In Magma V2.8, only the second implementation is exported. It is intended to rework the Pecquet version to take advantage of the new curve machinery before releasing it.
Suppose X is an irreducible plane curve. Let S be a sequence of places of X having degree 1 and let D be a divisor of X whose support is disjoint from the support of S. The function returns the (weakly) algebraic--geometric code obtained by evaluating functions of the Riemann--Roch space of D at the points of S. The degree of D need not be bounded by the cardinality of S.
Given the prime power q and a positive integer r, construct a Hermitian code C with respect to the Hermitian curve X = x^((q + 1)) + y^((q + 1)) + z^((q + 1)) defined over GF(q^2). The support of C consists of all places of degree one of X over GF(q^2), with the exception of the place over P = (1:1:0). The divisor used to define a Riemann--Roch space is r * P.
> F<w> := GF(16); > P2<x,y,z> := ProjectiveSpace(F, 2); > f := x^3+x^2*z+y^3+y^2*z+z^3; > X := Curve(P2, f); > g := Genus(X); > g; 1 > places1 := Places(X, 1); > #places1; 25
We now need to find an appropriate divisor D. Since we require a code of dimension k=9 we take the divisor corresponding to a place of degree k + g - 1 = 9 (g is the genus of the curve).
> found, place_k := Place(X, 9+g-1); > D := DivisorGroup(X) ! place_k; > C := AlgebraicGeometricCode(places1, D); > C; [25, 9] Linear Code over GF(2^4) Generator matrix: [1 0 0 0 0 0 0 0 0 w^9 w w^8 0 w^5 1 1 w^5 w^7 w^8 w^10 w^4 w^11 w^5 w^10 w^8] [0 1 0 0 0 0 0 0 0 w^4 w^5 1 w^10 w^4 w^11 w^12 0 1 w^2 w^4 w^6 w^4 w^5 w^14 w^4] [0 0 1 0 0 0 0 0 0 w^5 w^13 w^7 w^10 w^7 w^5 w^14 w^14 w 1 w^10 w^9 1 0 w^5 w] [0 0 0 1 0 0 0 0 0 w^8 w^3 w^3 w^12 w^7 w^10 w w^6 0 w^7 w^10 w^4 w^9 w^14 w^8 w^12] [0 0 0 0 1 0 0 0 0 w^8 1 w^4 w^7 w^5 w w^8 w w^5 w w^13 0 w^14 w^14 w^14 w^6] [0 0 0 0 0 1 0 0 0 1 1 w^12 w^14 w^9 w^10 w^6 w^6 w^7 w^10 w^4 w^3 w^13 w^13 w^3 w^4] [0 0 0 0 0 0 1 0 0 w w w^10 w^4 w^12 w w^13 w^4 w w^2 w^3 w^3 w^12 w^10 w^5 w^13] [0 0 0 0 0 0 0 1 0 w^13 w^6 w^12 w^2 w^3 w^7 w^3 w^4 w^14 w^4 w^11 w^4 w w^6 w^4 w^14] [0 0 0 0 0 0 0 0 1 0 w^11 w w^7 w^12 w^4 w^3 w^6 w^12 w^3 w^13 w^2 w^11 w^10 w^3 1] > MinimumDistance(C); 16
> k<w> := GF(16); > P2<x,y,z> := ProjectiveSpace(k, 2); > f := (y^2+x*y+x^2)*z^3+y^3*z^2+(x*y^3+x^2*y^2+x^3*y+x^4)*z+x^3*y^2+x^4*y+x^5; > X := Curve(P2, f); > g := Genus(X); > g; 4
We find all the places of degree 1.
> places1 := Places(X, 1); > #places1; 45
We choose as our divisor 15 * P1, where P1 is a place of degree 1. Before applying the AG-Code construction we must remove P1 from the set of places of degree 1.
> P1 := Random(places1); > Exclude( places1, P1); > #places1; 44 > D := 15 * (DivisorGroup(X) ! P1); > C := AlgebraicGeometricCode(places1, D); > C:Minimal; [44, 12] Linear Code over GF(2^4) > MinimumWeight(C); 29
Return true if and only if the code C is a weakly algebraic--geometric code, i.e. C has been constructed as an algebraic--geometric code with respect to a divisor of any degree.
Return true if and only if the code C is of algebraic--geometric construction of length n, built from a divisor D with deg(D) < n.
Return true if and only if C is an algebraic--geometric code of length n constructed from a divisor D satisfying 2g - 2 < deg(D) < n, where g is the genus of the curve.
At the time an AG--Code is constructed a number of attributes describing its construction are stored along with the code. The functions in this section give the user access to these attributes.
Given an algebraic--geometric code C, returns the curve from which C was defined.
Given an algebraic--geometric code C, return the sequence of places which forms the support for C.
Given an algebraic--geometric code C, return the divisor from which C was constructed.
Given an algebraic--geometric code C constructed from a divisor D, return the Goppa designed distance n - deg(D).[Next][Prev] [Right] [Left] [Up] [Index] [Root]