Community Hub0 Subscribers
Community hub
Wikipedia
Algebraic geometry code
View on Wikipediafrom Wikipedia
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
[edit]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
[edit]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
[edit]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 .[8]
Formally, Reed–Solomon codes are defined in the following way. Let . Set positive integers . Let The Reed–Solomon code is the evaluation code
![{\displaystyle \mathbb {F} _{q}[x]_{<k}:=\left\{f\in \mathbb {F} _{q}[x]:\deg f<k\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5bfb18b219329b5475ed4a254fd1a78e009016b)
![{\displaystyle RS(q,n,k)=\left\{\left(f(\alpha _{1}),f(\alpha _{2}),\dots ,f(\alpha _{n})\right):f\in \mathbb {F} _{q}[x]_{<k}\right\}\subseteq \mathbb {F} _{q}^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f519272f706d6d3f7a58d6586738ff6121b27f2d)
Codes from algebraic curves
[edit]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 ) can be thought of as polynomials with pole allowance no more than at the point at infinity in .[6]
![{\displaystyle \mathbb {F} _{q}[x]_{<k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52ce5d010b875652e08543464484d1b328905866)
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 over (that is, the points in on the curve ) 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, be the sum of distinct places of of degree one, and be a divisor with disjoint support from . The algebraic geometry code associated with divisors and is defined as More information on these codes may be found in both introductory texts[6] as well as advanced texts on coding theory.[10][11]
Examples
[edit]Reed-Solomon codes
[edit]One can see that
where is the point at infinity on the projective line and is the sum of the other -rational points.
One-point Hermitian codes
[edit]The Hermitian curve is given by the equationconsidered over the field .[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 .[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 given by and for , the Riemann–Roch space iswhere is the point at infinity on .
With that, the one-point Hermitian code can be defined in the following way. Let be the Hermitian curve defined over .
Let be the point at infinity on , and be a divisor supported by the distinct -rational points on other than .
The one-point Hermitian code is
References
[edit]- ^ 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.
- ^ a b c Stichtenoth, Henning (1988). "A note on Hermitian codes over GF(q^2)". IEEE Transactions on Information Theory. 34 (5): 1345–1348 – via IEEE.
- ^ Goppa, Valery Denisovich (1970). "A new class of linear error-correcting codes". Probl. Inf. Transm. 6: 300–304.
- ^ 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.
- ^ Berlekamp, Elwyn (1973). "Goppa codes". IEEE Transactions on Information Theory. 19 (5): 590–592 – via IEEE.
- ^ a b c Walker, Judy L. (2000). Codes and Curves. American Mathematical Society. p. 15. ISBN 0-8218-2628-X.
- ^ Tsfasman, Michael; Vladut, Serge; Zink, Thomas (1982). "Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound". Mathematische Nachrichten.
- ^ 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.
- ^ a b Hoholdt, Tom; van Lint, Jacobus; Pellikaan, Ruud (1998). "Algebraic geometry codes" (PDF). Handbook of coding theory. 1 (Part 1): 871–961 – via Elsevier Amsterdam.
- ^ a b c Stichtenoth, Henning (2009). Algebraic function fields and codes (2nd ed.). Springer Science & Business Media. pp. 45–65. ISBN 978-3-540-76878-4.
- ^ van Lint, Jacobus (1999). Introduction to coding theory (3rd ed.). Springer. pp. 148–166. ISBN 978-3-642-63653-0.
- ^ Garcia, Arnoldo; Viana, Paulo (1986). "Weierstrass points on certain non-classical curves". Archiv der Mathematik. 46: 315–322 – via Springer.
- ^ Tiersma, H.J. (1987). "Remarks on codes from Hermitian curves". IEEE Transactions on Information Theory. 33 (4): 605–609 – via IEEE.
Grokipedia
Algebraic geometry code
View on Grokipediafrom Grokipedia
Introduction and Fundamentals
Definition and basic concepts
Algebraic geometry codes, often abbreviated as AG codes, are linear error-correcting codes over a finite field constructed as evaluation codes using points and functions on algebraic varieties, particularly nonsingular projective curves, thereby generalizing classical codes like Reed–Solomon codes.[5] These codes leverage the structure of the function field of the variety to achieve parameters that surpass certain bounds for random linear codes, especially for large lengths.[5] Consider a nonsingular projective curve of genus defined over , with rational points on .[5] Let be an effective divisor of degree , representing the evaluation points, and let be another divisor of degree with support disjoint from that of .[5] The Riemann–Roch space is the -vector space of all rational functions in the function field of (including the zero function) such that the principal divisor satisfies , meaning the poles of are controlled by .[5] By the Riemann–Roch theorem, the dimension equals when .[5] The AG code is the image of the -linear evaluation map
so the codewords are precisely these evaluations of basis functions from at the points in the support of .[5] Thus, forms a linear code, where the generator matrix has rows given by the evaluations of a basis of at .[5] The minimum distance satisfies the designed distance bound , derived from the fact that any nonzero vanishes at at most points.[5]
Reed–Solomon codes correspond to the special case where is the projective line (of genus ) over .[5] For higher-dimensional varieties, the construction extends analogously by evaluating sections of line bundles (or sheaves) at rational points, using higher-codimension divisors and appropriate cohomology spaces in place of .[5]
Mathematical prerequisites
Algebraic geometry codes build upon foundational concepts from coding theory. A linear code over the finite field is defined as a -dimensional subspace of the vector space .[6] Such codes are characterized by the parameters , where denotes the length (dimension of the ambient space), the dimension of the code (number of information symbols), and the minimum Hamming distance between any two distinct codewords.[6] The generator matrix is a matrix whose rows form a basis for , while the parity-check matrix is an matrix satisfying for all codewords .[7] A fundamental limitation is given by the Singleton bound, which asserts that for any block code.[6] Key elements from algebraic geometry are also essential. Projective varieties over are the common zero loci of homogeneous polynomials in projective space .[8] Algebraic curves are irreducible projective varieties of dimension one, each associated with a genus , an invariant that quantifies the curve's topological complexity; for example, the projective line has genus 0, while elliptic curves have genus 1.[9] The function field of a curve consists of all rational functions on , which are quotients of polynomials regular away from finitely many poles.[9] Divisors on are formal -linear combinations of points on the curve, with the degree of a divisor defined as .[9] The Riemann-Roch theorem relates the geometry of the curve to the dimensions of spaces of functions with controlled poles. For a divisor on a curve of genus with ,
where is the vector space of rational functions such that (the Riemann-Roch space) and is the index of specialty.[9] The theorem holds in a more general form as
where is a canonical divisor, for any divisor , and the difference captures the adjustment from the naive degree-genus relation.[9] This result will later help bound the dimensions of spaces used in code constructions.
A crucial quantity is the number of -rational points on a curve of genus , denoted , which counts the solutions to the defining equations over . The Weil bound provides an estimate:
This inequality limits how many points a curve can have over , influencing the potential length of associated codes.[10]
Historical Development
Origins and Goppa codes
The origins of algebraic geometry codes trace back to the work of V. D. Goppa in the early 1980s, building on his earlier invention of classical Goppa codes. In 1970, Goppa introduced classical Goppa codes as a class of linear error-correcting codes constructed using polynomials over finite fields, specifically leveraging the rational function field where places correspond to the zeros and poles of rational functions.[11] These codes generalized earlier constructions like Reed–Solomon codes by employing more flexible polynomial structures to achieve good error-correcting capabilities.[12] Seeking to improve code parameters beyond the limitations of the rational function field, Goppa extended this framework in his 1981 paper by incorporating algebraic curves over finite fields, using Riemann surfaces and function fields of general curves to define a broader class of codes now known as geometric Goppa codes.[12] This generalization allowed for the evaluation of functions at more rational points on the curve compared to the single-variable case, motivated by the goal of constructing codes that surpass the Gilbert-Varshamov bound through the geometric properties of curves with higher genus. Unlike classical Goppa codes, which are confined to the places of and thus limited in the number of evaluation points, geometric Goppa codes exploit the richer structure of arbitrary algebraic curves, enabling potentially superior asymptotic performance. In a follow-up 1982 paper, Goppa specifically demonstrated the construction of such codes using hyperelliptic curves, further illustrating how the divisor-based approach on these curves yields linear codes with parameters tied to the curve's geometry. Over time, the terminology evolved from "geometric Goppa codes," emphasizing their connection to Goppa's classical work, to the more general "algebraic geometry codes," reflecting their reliance on broader tools from algebraic geometry beyond just curves.[13]Key breakthroughs and advancements
A landmark advancement in the theory of algebraic geometry codes occurred in 1982 with the work of Tsfasman, Vlăduţ, and Zink, who constructed sequences of codes from modular curves that exceed the asymptotic Gilbert-Varshamov bound, attaining the TVZ bound for relative distance for any , where is the rate, marking the first time codes outperformed the GV bound using geometric constructions for square . This result highlighted the potential of algebraic curves to yield asymptotically good codes, particularly for square field sizes . The TVZ construction's impact extended to the study of asymptotic optimality, where Ihara's constant —the supremum ratio of rational points to genus over curves —plays a central role. For fixed , as block length , algebraic geometry codes achieve rates and distances approaching the Drinfeld-Vlăduţ upper bound on , with TVZ providing explicit families attaining near-optimal values and demonstrating asymptotic optimality in this regime.[14] In the 1990s, further progress focused on explicit constructions, notably using Drinfeld modular curves as analogues of classical modular towers for general finite fields, enabling polynomial-time computable codes with parameters matching or approaching TVZ bounds without relying on square . These developments, building on Drinfeld modules, facilitated practical implementations and extended the applicability of algebraic geometry codes to diverse field characteristics. The 2000s saw extensions to higher-dimensional varieties, such as surfaces and abelian varieties, where codes from ideals in coordinate rings of higher-genus objects offered improved trade-offs in dimension and minimum distance, though with increased computational complexity. Concurrently, list-decoding algorithms for algebraic geometry codes emerged, adapting interpolation-based methods to decode up to a constant fraction of errors beyond half the minimum distance, significantly enhancing error-correcting capabilities over unique decoding.[15] By the 2020s, algebraic geometry codes integrated with quantum error correction, providing asymptotically good stabilizer codes for fault-tolerant quantum computing, including applications in magic state distillation with optimal scaling and decoded quantum interferometry protocols that leverage their geometric structure for robust phase estimation.[16]Construction Principles
General framework for evaluation codes
The general framework for evaluation codes establishes a paradigm for constructing linear codes over a finite field $ \mathbb{F}_q $ by evaluating functions from a vector space at a finite set of points on an algebraic variety. Consider a smooth projective variety $ X $ defined over $ \mathbb{F}_q $, a finite set of distinct $ \mathbb{F}_q $-rational points $ Z = {P_1, \dots, P_n} \subset X(\mathbb{F}_q) $, and a finite-dimensional $ \mathbb{F}_q $-vector space $ V $ of $ \mathbb{F}_q $-rational functions on $ X $. The evaluation map $ \ev_Z: V \to \mathbb{F}_q^n $ is defined by $ \ev_Z(f) = (f(P_1), \dots, f(P_n)) $ for $ f \in V $, and the resulting code $ C $ is the image of this map, a linear subspace of $ \mathbb{F}_q^n $ with length $ n $. This construction captures a broad class of codes, including generalizations of Reed-Solomon codes where $ V $ consists of polynomials of bounded degree evaluated on field elements viewed as points on the projective line.[17] In algebraic geometry codes, this framework is formalized using divisors to specify both the evaluation points and the function space. Let $ D = \sum_{i=1}^n P_i $ be the effective divisor supported on $ Z $, so $ n = \deg D $. Choose a rational divisor $ G $ on $ X $ such that $ \supp(G) \cap Z = \emptyset $, and set $ V = \mathcal{L}(G) = { f \in k(X) \mid \div(f) + G \geq 0 } \cup { 0 } $, the Riemann-Roch space of global sections of the line bundle associated to $ G $, where $ k(X) $ is the function field of $ X $. The code is then $ C(D, G) = \ev_Z(\mathcal{L}(G)) $, with dimension $ k = \dim_{\mathbb{F}_q} \mathcal{L}(G) $. By the Riemann-Roch theorem, for varieties where it applies (such as curves), $ k \geq \deg G + 1 - g $, with $ g $ denoting the genus or an analogous irregularity measure.[17] The parameters of such codes follow from geometric properties: the length is $ n = \deg D $, the dimension is approximately $ k \approx \deg G - g + 1 $, and the minimum distance satisfies $ d \geq n - \deg G $, known as the designed distance $ \delta = n - \deg G $. This distance bound arises because any nonzero $ f \in \mathcal{L}(G) $ has at most $ \deg G $ zeros (counting multiplicity), ensuring that $ \ev_Z(f) $ has weight at least $ n - \deg G $. A refinement of the Singleton bound, accounting for the geometry, gives $ d \geq n - k + 1 - g $, reflecting the overhead due to the variety's complexity compared to one-dimensional cases like Reed-Solomon codes. These parameters position algebraic geometry codes as powerful constructions exceeding classical bounds in certain regimes.[17]Codes from algebraic curves
Algebraic geometry codes from algebraic curves are constructed using a nonsingular projective algebraic curve of genus defined over a finite field . A set of distinct rational points is selected, and the divisor is formed. A divisor on is chosen such that its support is disjoint from the support of , ensuring that the evaluation map is well-defined. The code is then defined as the image of the evaluation map , where is the Riemann-Roch space associated to , consisting of rational functions on with poles controlled by . This construction generalizes classical evaluation codes by incorporating the geometry of the curve, allowing for improved parameters through the interplay of points and function spaces.[18] The dimension and minimum distance of the code are determined via the Riemann-Roch theorem applied to the curve. Specifically, the dimension satisfies , where denotes the dimension of the corresponding Riemann-Roch space; if , then , yielding . For , the Riemann-Roch theorem gives . The minimum distance follows a designed bound analogous to the BCH bound, , which arises because any function in can vanish at most points unless identically zero. These parameters enable codes that surpass certain classical bounds for sufficiently large relative to .[18] A common specialization is the one-point code, where for some rational point not among the and integer . Here, , so the code has dimension and designed distance . This setup simplifies the choice of while leveraging the full strength of Riemann-Roch for large , and it is particularly effective on curves with many rational points.[18] An illustrative example is provided by the Hermitian curve, defined over by the equation , which has genus . This curve admits exactly rational points over ; for one-point Hermitian codes, points are typically selected, excluding the point at infinity , with their sum and . The resulting codes achieve dimension and distance for , demonstrating asymptotic optimality in certain regimes.[18] For hyperelliptic curves, given by an affine model of degree or over (with projective closure), an explicit basis for can be constructed using the structure of the function field. For where is the hyperelliptic branch point at infinity, the basis consists of monomials for and for , respecting the pole orders determined by the valuation at ; this extends to differentials for dual code constructions, where uses holomorphic differentials adjusted by . Such bases facilitate efficient encoding and decoding for these codes.[18]Codes from higher-dimensional varieties
Algebraic geometry codes from higher-dimensional varieties extend the evaluation code framework to projective varieties of dimension defined over the finite field . The construction involves selecting a set of rational points on and a line bundle associated to an effective divisor . The code is then the image of the evaluation map , where , yielding a linear code over of length .[15] A primary challenge in these constructions arises from the scarcity of -rational points on higher-dimensional varieties compared to curves, with the Lang-Weil estimate bounding the number of points by approximately . To address this, methods such as adjunction—intersecting with curves to apply one-dimensional techniques—or the use of complete linear systems for divisors are employed; additional approaches include deriving codes from Grassmannians, which parameterize subspaces and yield MDS codes with parameters , and from toric varieties, linking to lattice-based toric codes.[15][19] The dimension of the code equals , computed via the Hirzebruch-Riemann-Roch theorem, which expresses it in terms of the Chern character of and the Todd class of :
where approximates under vanishing higher cohomology. Distance bounds are generally weaker than those for curve codes due to the more complex geometry, analogous to higher-genus effects; volume-based estimates from the Weil conjectures refine this to forms like for suitable constants .[15][19]
In the 1990s, seminal constructions on Hermitian surfaces provided concrete examples with improved performance. Consider the surface defined over by the equation ; evaluating sections of at all rational points yields a code with parameters , achieving relative rates superior to those from algebraic curves for certain square .[19]
Key Properties
Code parameters and bounds
Algebraic geometry (AG) codes are evaluation codes defined on the rational points of an algebraic variety, typically a curve of genus over a finite field . The length of an AG code is the number of -rational points in the support of the divisor , so . The dimension is given by , where denotes the dimension of the Riemann-Roch space; when , this simplifies to . By the Riemann-Roch theorem, for a canonical divisor , yielding when and .[20] The designed minimum distance for is , reflecting the maximum number of zeros a non-zero function in can have at points in the support of . The actual minimum distance satisfies , a bound derived from the fact that any non-constant can vanish at most points in the support of , as the degree of its zero divisor equals the degree of its pole divisor (bounded by ). Tighter values of can be obtained from weight enumerators, which count codewords of each weight, or from advanced algebraic geometry bounds such as the order bound or Feng-Rao bound.[20][21] A fundamental bound is the geometric Singleton bound, , which refines the classical Singleton bound by incorporating the genus . This improvement arises from applying the Riemann-Roch theorem to the effective divisors associated with codewords and is particularly effective for high-genus curves, where allows AG codes to outperform Reed-Solomon codes in asymptotic rate-distance tradeoffs. For instance, when the Riemann-Roch space achieves its generic dimension, the geometric Singleton bound aligns with the designed bound .[21] Proofs of the minimum distance often rely on geometric invariants like the gonality of the curve—the minimal degree of a rational map to —or adjoint conditions tied to the canonical system. The gonality provides lower bounds via the characterization , where low-gonality curves limit the degrees of such . Adjoint conditions for the dual code involve the failure of linear equivalence to a canonical divisor plus an effective divisor disjoint from evaluation points, yielding for the designed distance of the dual. A related bound is , adjusting the designed distance for geometric effects.[20][22] For one-point AG codes, where for a rational point and , explicit formulas for and stem from the Weierstrass gap theorem at . The theorem states there are exactly gaps—integers with —and the dimension is , precisely counting basis functions with poles up to order at . The minimum distance follows from analyzing the zero multiplicities at affine rational points, often yielding , where is the largest non-gap at or below , enabling exact computation for specific curves like elliptic or hyperelliptic ones.[23]Asymptotic performance
In the asymptotic regime of algebraic geometry (AG) codes, one considers families of codes where the block length tends to infinity. The relative distance is defined as , where is the minimum distance, and the rate is , where is the dimension. The optimal asymptotic performance is captured by the function , representing the maximum achievable rate for a given relative distance over the finite field . The Tsfasman-Vlăduţ-Zink (TVZ) bound provides a fundamental lower bound on . Specifically, if the Ihara constant , then for . For a perfect square, this bound exceeds the Gilbert-Varshamov bound , where is the -ary entropy function, particularly for . This superiority holds because the TVZ construction yields families of codes with rates strictly greater than for any in that range.[24][2] The Ihara constant , where is the maximum number of -rational points on an algebraic curve of genus , directly influences AG code performance. For families of curves yielding good AG codes, the number of evaluation points scales asymptotically with the genus as , while the designed distance relates to , enabling rates and distances tied to . The Drinfeld-Vladut bound states that for all .[14][25] Modular tower constructions achieve the optimal when is a perfect square, as shown using Drinfeld modular curves, which realize the TVZ bound explicitly. These towers provide sequences of function fields with the required point-genus growth, leading to AG code families that are asymptotically optimal in the specified regime. Advancements from 2017 have extended explicit tower constructions to block-transitive AG codes, attaining the TVZ bound over .[26][27][28] As of 2025, AG codes have been applied to decoded quantum interferometry, enhancing fault-tolerant quantum computing protocols.[29]Decoding Methods
Algorithms up to half the minimum distance
Standard decoding algorithms for algebraic geometry (AG) codes correct up to $ t = \lfloor (d-1)/2 \rfloor $ errors, where $ d $ is the minimum distance, relying on syndrome computations and solutions to key equations derived from the geometry of the underlying variety. These methods extend the Patterson algorithm originally developed for Goppa codes, which computes syndromes $ S_i = \sum y_j \alpha_j^i $ for received vector $ y $ and distinct points $ \alpha_j $, then solves for the error locator polynomial via square-root computations in the rational function field modulo the Goppa polynomial. This approach was generalized to AG codes from arbitrary curves by Ehrhard, who formulated a key equation solvable through linear algebra over Riemann-Roch spaces, enabling error location and evaluation without explicit square roots.[30] For AG codes defined on curves, the decoding process begins by computing syndromes from the received word $ y $, typically as residues or evaluations in the space of differentials or adjoints associated with the code's divisor. The core step involves solving a generalized key equation relating the syndrome to the error evaluator and locator within the Riemann-Roch space $ L((2t-2)P_\infty) $, where $ P_\infty $ is the point at infinity.[31] Once solved, the roots of the error locator identify error positions via interpolation on the curve, and the error evaluator yields error values, achieving unique decoding up to the designed distance. The Reed-Solomon code serves as a special case where the curve degenerates to the projective line, reducing to the Berlekamp-Massey algorithm. The computational complexity of these syndrome-based decoders is generally $ O(n^2) $ operations in the base field, where $ n $ is the code length, arising from syndrome calculation and linear system solves over spaces of dimension roughly $ 2t $; improvements to $ O(n \log^2 n) $ are possible using fast multiplication and Fourier-like transforms adapted to the curve's Jacobian or residue maps.[32] For Hermitian codes over $ \mathbb{F}_{q^2} $, defined on the curve $ x^{q+1} + y^{q+1} + z^{q+1} = 0 $, explicit algorithms leverage the curve's symmetry to compute q-ary syndromes directly from evaluations at rational points, solving the key equation via Newton identities or Gröbner bases for error locators in polynomial time up to half the distance.[33]Advanced and list decoding techniques
Advanced decoding techniques for algebraic geometry (AG) codes extend beyond the unique decoding radius of half the minimum distance, enabling correction of a larger fraction of errors at the cost of potentially outputting a list of candidate codewords rather than a unique one. The seminal Guruswami-Sudan algorithm generalizes the Sudan interpolation-based list decoding from Reed-Solomon codes to AG codes defined on algebraic curves of arbitrary genus, achieving a list-decoding radius up to the Johnson bound while producing a polynomial-sized list in the block length .[34] In this framework, decoding involves finding a nonzero bivariate polynomial over the function field, with degree at most in and in (where is the design rate and the dimension), such that for all received symbols at evaluation points , followed by factorization to recover possible messages.[34] For Hermitian codes, a prominent class of AG codes on curves over , this approach corrects up to $ n - \sqrt{k n} $ errors, approaching the theoretical limit for list decoding.[34] For one-point AG codes, the Feng-Rao decoding algorithm improves upon standard methods by exploiting the structure of the dual code to correct errors up to the designed minimum distance (where is the genus), which exceeds half the distance for low-rate codes, achieving up to errors in certain regimes through majority-logic decoding of unknown syndromes. An algebraic-geometric adaptation of the Koetter-Vardy soft-decision decoding algorithm further enhances performance by incorporating reliability information from the channel, constructing a tree of interpolation polynomials on the curve to list-decode beyond hard-decision limits, with complexity polynomial in .[35] Post-2010 advancements include adaptations of Chase decoding algorithms to AG codes on curves, particularly Hermitian codes, where low-complexity variants generate test vectors from the most unreliable positions and apply list decoding to each, yielding significant gains over Koetter-Vardy with reduced computational overhead.[36] In 2025, decoded quantum interferometry emerged as a novel application, leveraging the algebraic structure of AG codes—such as Hermitian codes—for error correction in quantum optimization tasks, mapping decoding problems to quantum Fourier transform-based interferometry protocols that reduce qubit requirements by one-third compared to Reed-Solomon-based approaches.[29]Examples
Reed–Solomon codes
Reed–Solomon codes provide a foundational example of algebraic geometry codes, specifically evaluation codes derived from the projective line over a finite field . In this construction, the underlying curve is the projective line , which is a smooth projective curve of genus 0. The code is defined by selecting distinct evaluation points , corresponding to the divisor where is the point at . The code space is then the Riemann–Roch space for the divisor , where denotes the point at infinity on , yielding functions that are polynomials of degree less than . The codewords are obtained via evaluation: for , the codeword is .[37][38] These codes achieve length , dimension , and minimum distance , saturating the Singleton bound for maximum distance separable (MDS) codes. The generator matrix for the Reed–Solomon code has entries for and , reflecting the monomial basis of polynomials of degree less than . This structure ensures optimal error-correcting capability up to errors, making them ideal for applications requiring high reliability over finite fields.[38][37] An extension of Reed–Solomon codes incorporates the point at infinity, increasing the length to while preserving the MDS property, with evaluation now including a suitable value at (often defined via homogeneous coordinates). This extended version maintains the parameters and is particularly useful in scenarios demanding full field utilization.[38][37]Hermitian codes
Hermitian codes are a family of algebraic geometry codes constructed from the Hermitian curve, providing a non-trivial example beyond Reed–Solomon codes due to the positive genus of the underlying curve. The Hermitian curve is defined by the affine equation over the finite field , where is a prime power. This curve has genus and exactly affine -rational points, which serve as the evaluation points for the code. The point at infinity is the unique hyperflex at infinity, with pole orders and .[39] The one-point Hermitian code is the evaluation code at the affine rational points, with evaluation divisor consisting of these points and pole divisor for a positive integer . The codewords are formed by evaluating a basis of the Riemann–Roch space , which is spanned by monomials satisfying . By the Riemann–Roch theorem, the dimension is when . The designed minimum distance satisfies , reflecting the bound from the geometry of the curve, though the true distance can be larger in certain ranges. The rate of the code is approximately .[39][40] This family achieves more rational points than curves of genus zero while maintaining good relative distance, making it suitable for applications requiring longer codes over .[41]Other notable codes
Hyperelliptic codes are constructed from hyperelliptic curves defined by the equation $ y^2 + h(x) y = f(x) $, where $ h(x) $ and $ f(x) $ are polynomials over a finite field $ \mathbb{F}_q $ with $ q $ even, and the degree of $ f(x) $ is $ 2g + 1 $ for genus $ g = (\deg f - 1)/2 $. These codes are particularly suitable for even characteristic fields and offer parameters comparable to those from Hermitian curves, while providing explicit bases for the Riemann-Roch spaces that facilitate computational efficiency. Codes from modular curves, such as towers of $ X_0(N) $ for increasing $ N $, yield asymptotically good constructions that achieve the Tsfasman-Vlăduţ-Zink (TVZ) bound on the tradeoff between code rate and relative minimum distance.[42] These towers over finite fields of size $ q_0^2 $ produce codes with length $ n \approx q^{1 + 1/(2 \lfloor \log_q N \rfloor)} $, enabling high rates for large genus while maintaining strong error-correcting capabilities.[42] The Garcia-Stichtenoth codes arise from explicit towers of function fields over finite fields of square cardinality $ q = r^2 $ with $ r > 2 $, constructed recursively to attain the optimal asymptotic bound $ A(q) = 1/(\sqrt{q} - 1) $, where $ A(q) $ denotes the limit of the maximal code rate as genus tends to infinity. This tower provides a concrete family of curves yielding algebraic geometry codes that surpass the Gilbert-Varshamov bound for sufficiently large parameters. Two-point codes on the Hermitian curve, using divisors of the form $ aP + bQ $ where $ P $ and $ Q $ are distinct rational points, achieve minimum distances strictly larger than those of the corresponding one-point codes for a range of designed distances, thereby improving error-correcting performance without increasing redundancy.[43]Applications
Error correction and storage
Algebraic geometry (AG) codes have found practical applications in classical error correction for communications systems, particularly where high-rate, long-length codes are required. Their asymptotic goodness allows them to outperform BCH and Reed-Solomon (RS) codes for extended code lengths, enabling more efficient data transmission over noisy channels. For instance, AG codes based on algebraic curves achieve better relative minimum distances as the field size $ q $ grows, making them suitable for scenarios demanding robust performance without exponentially increasing the alphabet size.[44] In deep-space probes and satellite links, AG codes support high-rate error correction by leveraging their superior parameters for reliable transmission of telemetry data across vast distances with low signal-to-noise ratios. These codes provide enhanced error-detecting and correcting capabilities compared to traditional block codes, contributing to the integrity of mission-critical communications. NASA evaluations have demonstrated that certain AG codes surpass RS codes in coding gain, such as achieving approximately 1/3 dB better performance than RS(511,127) for specific parameters.[44][45] For data storage systems, AG codes enhance reliability in flash memory and RAID configurations, where they effectively mitigate burst errors—clusters of consecutive errors arising from physical wear or interference—outperforming turbo codes in certain operational regimes due to their structured algebraic properties. This burst-error resilience stems from the geometric construction, allowing targeted decoding without excessive overhead. In optical storage applications, Hermitian codes, a prominent class of AG codes derived from the Hermitian curve over $ \mathbb{F}_{q^2} $, correct up to 10-15% errors for code lengths $ n \approx 10^6 $, offering scalable protection for high-density media.[44] Comparatively, AG codes outperform random linear codes even at finite lengths when $ q $ is large, as their minimum distance exceeds the Gilbert-Varshamov bound through explicit curve-based constructions, providing deterministic guarantees absent in probabilistic random ensembles. This advantage is particularly evident in storage contexts requiring predictable error thresholds.[44]Cryptography and secret sharing
Algebraic geometry (AG) codes have been adapted to variants of the McEliece public-key cryptosystem, where the generator matrix of an AG code, such as a Hermitian code, serves as the basis for encryption, with security relying on the hardness of the syndrome decoding problem.[46] In this setup, the public key consists of a scrambled generator matrix $ G_{\text{pub}} = S G P $, where $ G $ is the generator matrix of the AG code, $ S $ is an invertible scrambling matrix, and $ P $ is a permutation matrix, while encryption appends an error vector of weight up to half the minimum distance to a codeword.[47] The syndrome decoding problem for general linear codes is NP-complete, providing the foundational security assumption for these systems.[47] Constructions of such AG-based McEliece variants emerged in the 1990s, leveraging the efficient decoding algorithms available for AG codes up to half their minimum distance, with security grounded in the NP-hardness of decoding linear codes and related problems like finding minimum-weight codewords.[46][47] Hermitian codes, as a prominent class of AG codes defined over the Hermitian curve $ x^{q+1} + y^{q+1} + z^{q+1} = 0 $ in projective space over $ \mathbb{F}_{q^2} $, have been particularly used due to their good parameters, such as length $ n = q^3 $ and dimension scaling favorably with the genus.[48] Post-2009 developments include quantum-resistant variants employing structured subfield subcodes of Hermitian AG codes to enhance efficiency while preserving security against known attacks on the syndrome decoding problem.[49] In secret sharing protocols, AG codes enable ramp schemes that support complex access structures, allowing reconstruction of a secret from $ t $ shares out of $ n $ while providing privacy against fewer than $ t $ shares, with information rates exceeding $ 1/2 $.[50] These schemes distribute shares $ s_i = f(P_i) $ for distinct points $ P_i $ on an algebraic curve and a random function $ f $ drawn from the Riemann-Roch space $ L(G) $ associated with a divisor $ G $, such that the secret can be reconstructed via interpolation when sufficiently many points are available.
Reconstruction is possible if the number of shares meets or exceeds the degree threshold implicit in the divisor, enabling high-rate ramp schemes over constant-sized fields using constructions like Garcia-Stichtenoth towers.[50] List decoding techniques can enhance robustness in these schemes by allowing recovery even with some corrupted shares.[50]