Extended Algebraic-Geometric Codes
In [1], Goppa proposes the following construction for linear codes based on global function fields:
Let F denote a global function field with full constant field Fb and genus g = g(F/Fb). Furthermore let P1,…, Ps denote s rational places of F and let G denote a divisor of F with suppG∩{P1,…, Ps} = ∅ and deg G < s. The algebraic-geometric code AG(F, G) is defined as
where L(G) denotes the Riemann-Roch space of the divisor G. It is a linear [s, n, d]-code over Fb with n = dim G and d ≥ s – deg G.
The Dimension of Algebraic-Geometric Codes
It follows from the definition of the genus that dim G ≥ deg G−g + 1, i.e., the code contains a subcode with dimension n ≥ deg G−g + 1. If deg G ≥ 2g, this bound is sharp. For deg G < 2g it is possible that dim G > deg G−g + 1. If G is of the form rP, with P denoting a place of F, the exact value of dim G = dim rP is determined by the Weierstrass semigroup of P. For some function fields these numbers are known and MinT uses this information.
In addition to that, the dimension of the zero-divisor is always 1 because L(0) is the space of constant functions. Therefore AG(F, 0) is the [s, 1, s]-repetition code for every function field F.
The Minimum Distance of Algebraic-Geometric Codes
If the minimum distance d of AG(F, G) were less than s – deg G, there would exist a non-zero code word with u := s – d > deg G zeros, hence an f ∈ L(G) with u distinct zeros Pi1,…, Piu and therefore f ∈ L(Gʹ) with Gʹ = G – (Pi1 + … + Piu). Since f would be non-zero, deg Gʹ would be non-negative. However, deg Gʹ = deg G – u < deg G – deg G = 0, which is a contradiction.
Construction of the Divisor G
If the number of rational places N(F) is larger than s, one can choose one of these places P and use G = rP. Obviously, deg G = deg rP = r. Thus AG(F, rP) is an [s, max{1, r – g + 1}, s−r]-code with s = N(F) − 1 for all r = 0,…, s−1.
If a code of length s = N(F) is to be obtained, places of larger degree have to be used for the construction of G. MinT uses divisors G of the form G = Q + rP, where P is some non-rational place and Q is the sum of zero or more other non-rational places.
Subcode Structure
If G ≤ Gʹ, then AG(F, G) is a subcode of AG(F, Gʹ) and construction X can be applied to this pair of codes. In particular this situation arises for AG(F, Q + rP) ⊆ AG(F, Q + rʹP) with Q denoting an arbitrary divisor (but usually the zero-divisor), P denoting a place, and integers r, rʹ with r < rʹ.
If P is one of the rational places, one can apply construction X to AG(F,(r – 1)P) ⊆ AG(F, rP) with the [1, 1, 1]-code without redundancy. The result is an [s, max{1, r – g + 1}, s−r]-code with s = N(F), namely the so-called extended algebraic-geometric code AGe(F, rP).
Special Cases
If F is the rational function field over Fb, P1,…, Pb are the b places corresponding to the zeros of the linear functions, and G = rP∞, Reed-Solomon codes RS(r + 1, b) are obtained.
See also
Generalization for arbitrary OOAs
[2, Chapter II], [3, Chapter 6], [4], and [5, Section 18.2]
Goppa code at
References
| [1] | V. D. Goppa. Codes on algebraic curves. Soviet Mathematics. Doklady, 24(1):170–172, 1981. |
| [2] | Henning Stichtenoth. Algebraic Function Fields and Codes. Springer-Verlag, 1993. |
| [3] | Harald Niederreiter and Chaoping Xing. Rational Points on Curves over Finite Fields: Theory and Applications, volume 285 of Lect. Note Series of the London Math. Soc. Cambridge University Press, 2001. MR1837382 (2002h:11055) |
| [4] | Tom Høholdt, Jacobus H. van Lint, and Ruud Pellikaan. Algebraic geometry codes. In Vera S. Pless and W. Cary Huffman, editors, Handbook of Coding Theory, volume 1, pages 871–961. Elsevier Science, 1998. |
| [5] | Jürgen Bierbrauer. Introduction to Coding Theory. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004. MR2079734 (2005f:94001) |
Copyright
Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Extended Algebraic-Geometric Codes.”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2024-09-05.
http://mint.sbg.ac.at/desc_CGoppa.html