English Wikipedia @ Freddythechick

Algebraic geometry code

Mathematical linear code

Algebraic geometry codes, often abbreviated AG codes, are a type of linear code that generalize Reed–Solomon codes. The Russian mathematician V. D. Goppa constructed these codes for the first time in 1982.[1]

History

The name of these codes has evolved since the publication of Goppa's paper describing them. Historically these codes have also been referred to as geometric Goppa codes;[2] however, this is no longer the standard term used in coding theory literature. This is due to the fact that Goppa codes are a distinct class of codes which were also constructed by Goppa in the early 1970s.[3][4][5]

These codes attracted interest in the coding theory community because they have the ability to surpass the Gilbert–Varshamov bound; at the time this was discovered, the Gilbert–Varshamov bound had not been broken in the 30 years since its discovery.[6] This was demonstrated by Tfasman, Vladut, and Zink in the same year as the code construction was published, in their paper "Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound".[7] The name of this paper may be one source of confusion affecting references to algebraic geometry codes throughout 1980s and 1990s coding theory literature.

Construction

In this section the construction of algebraic geometry codes is described. The section starts with the ideas behind Reed–Solomon codes, which are used to motivate the construction of algebraic geometry codes.

Reed–Solomon codes

Algebraic geometry codes are a generalization of Reed–Solomon codes. Constructed by Irving Reed and Gustave Solomon in 1960, Reed–Solomon codes use univariate polynomials to form codewords, by evaluating polynomials of sufficiently small degree at the points in a finite field Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} .[8]

Formally, Reed–Solomon codes are defined in the following way. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q=\{\alpha_1, \dots, \alpha_q\}} . Set positive integers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \leq n \leq q} . Let

 
The Reed–Solomon code   is the evaluation code
 

Codes from algebraic curves

Goppa observed that   can be considered as an affine line, with corresponding projective line  . Then, the polynomials in   (i.e. the polynomials of degree less than   over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} ) can be thought of as polynomials with pole allowance no more than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} at the point at infinity in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{P}^1_{\mathbb{F}_q}} .[6]

With this idea in mind, Goppa looked toward the Riemann–Roch theorem. The elements of a Riemann–Roch space are exactly those functions with pole order restricted below a given threshold,[9] with the restriction being encoded in the coefficients of a corresponding divisor. Evaluating those functions at the rational points on an algebraic curve Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} (that is, the points in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q^2} on the curve Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} ) gives a code in the same sense as the Reed-Solomon construction.

However, because the parameters of algebraic geometry codes are connected to algebraic function fields, the definitions of the codes are often given in the language of algebraic function fields over finite fields.[10] Nevertheless, it is important to remember the connection to algebraic curves, as this provides a more geometrically intuitive method of thinking about AG codes as extensions of Reed-Solomon codes.[9]

Formally, algebraic geometry codes are defined in the following way.[10] Let   be an algebraic function field, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = P_1 + \dots + P_n} be the sum of   distinct places of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F / \mathbb{F}_q} of degree one, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} be a divisor with disjoint support from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} . The algebraic geometry code Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{\mathcal{L}}(D,G)} associated with divisors Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is defined as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_{\mathcal{L}}(D,G) := \lbrace (f(P_1),\dots,f(P_n)) : f \in \mathcal{L}(G) \rbrace \subseteq \mathbb{F}_q^n.} More information on these codes may be found in both introductory texts[6] as well as advanced texts on coding theory.[10][11]

Examples

Reed-Solomon codes

One can see that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle RS(q,n,k) = \mathcal{C}_\mathcal{L}(D,(k-1)P_\infty)}

where   is the point at infinity on the projective line Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{P}^1_{\mathbb{F}_q}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = P_1 + \dots + P_q} is the sum of the other Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} -rational points.

One-point Hermitian codes

The Hermitian curve is given by the equationFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{q+1} = y^q + y} considered over the field Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{q^2}} .[2] This curve is of particular importance because it meets the Hasse–Weil bound with equality, and thus has the maximal number of affine points over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{q^2}} .[12] With respect to algebraic geometry codes, this means that Hermitian codes are long relative to the alphabet they are defined over.[13]

The Riemann–Roch space of the Hermitian function field is given in the following statement.[2] For the Hermitian function field Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{q^2}(x,y)} given by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^{q+1} = y^q + y} and for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \in \mathbb{Z}^+} , the Riemann–Roch space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}(mP_\infty)} isFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}(mP_\infty) = \left\langle x^a y^b : 0 \leq b \leq q-1, aq + b(q+1) \leq m \right\rangle ,} where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_\infty} is the point at infinity on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{H}_q(\mathbb{F}_{q^2})} .

With that, the one-point Hermitian code can be defined in the following way. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{H}_q} be the Hermitian curve defined over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{q^2}} .

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_\infty} be the point at infinity on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{H}_q(\mathbb{F}_{q^2})} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D = P_1 + \cdots + P_n} be a divisor supported by the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n := q^3} distinct Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_{q^2}} -rational points on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{H}_q} other than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_\infty} .

The one-point Hermitian code Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(D,mP_\infty)} is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(D,mP_\infty) := \left\lbrace (f(P_1),\dots,f(P_n)) : f \in \mathcal{L}(mP_\infty) \right\rbrace \subseteq \mathbb{F}_{q^2}^n.}

References

  1. ^ Goppa, Valerii Denisovich (1982). "Algebraico-geometric codes". Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya. 46 (4): 726–781 – via Russian Academy of Sciences, Steklov Mathematical Institute of Russian.
  2. ^ 2.0 2.1 2.2 Stichtenoth, Henning (1988). "A note on Hermitian codes over GF(q^2)". IEEE Transactions on Information Theory. 34 (5): 1345–1348 – via IEEE.
  3. ^ Goppa, Valery Denisovich (1970). "A new class of linear error-correcting codes". Probl. Inf. Transm. 6: 300–304.
  4. ^ Goppa, Valerii Denisovich (1972). "Codes Constructed on the Base of (L,g)-Codes". Problemy Peredachi Informatsii. 8 (2): 107–109 – via Russian Academy of Sciences, Branch of Informatics, Computer Equipment and.
  5. ^ Berlekamp, Elwyn (1973). "Goppa codes". IEEE Transactions on Information Theory. 19 (5): 590–592 – via IEEE.
  6. ^ 6.0 6.1 6.2 Walker, Judy L. (2000). Codes and Curves. American Mathematical Society. p. 15. ISBN 0-8218-2628-X.
  7. ^ Tsfasman, Michael; Vladut, Serge; Zink, Thomas (1982). "Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound". Mathematische Nachrichten.
  8. ^ Reed, Irving; Solomon, Gustave (1960). "Polynomial codes over certain finite fields". Journal of the Society for Industrial and Applied Mathematics. 8 (2): 300–304 – via SIAM.
  9. ^ 9.0 9.1 Hoholdt, Tom; van Lint, Jacobus; Pellikaan, Ruud (1998). "Algebraic geometry codes" (PDF). Handbook of coding theory. 1 (Part 1): 871–961 – via Elsevier Amsterdam.
  10. ^ 10.0 10.1 10.2 Stichtenoth, Henning (2009). Algebraic function fields and codes (2nd ed.). Springer Science & Business Media. pp. 45–65. ISBN 978-3-540-76878-4.
  11. ^ van Lint, Jacobus (1999). Introduction to coding theory (3rd ed.). Springer. pp. 148–166. ISBN 978-3-642-63653-0.
  12. ^ Garcia, Arnoldo; Viana, Paulo (1986). "Weierstrass points on certain non-classical curves". Archiv der Mathematik. 46: 315–322 – via Springer.
  13. ^ Tiersma, H.J. (1987). "Remarks on codes from Hermitian curves". IEEE Transactions on Information Theory. 33 (4): 605–609 – via IEEE.
Retrieved from "https://enwiki.freddythechick.net/index.php?title=Algebraic_geometry_code&oldid=1189556"