Evaluation AG code 

Description

Evaluation code over \(GF(q)\) on a set of points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) in \(GF(q)\) lying on an algebraic curve \(\cal X\) whose corresponding vector space \(L\) of functions \(f\) consists of certain polynomials or rational functions.

Codewords are evaluations of all functions at the specified points, \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \quad\quad\forall f\in L~. \tag*{(1)}\end{align} The code is denoted as \(C_L({\cal X},{\cal P},D)\), where the divisor \(D\) (of degree less than \(n\)) determines which rational functions to use by prescribing features associated with their zeroes and poles. The original motivation for evaluation codes, which are generalizations of RS codes that expand both the types of functions used as well as the available evaluation points, was to increase code length while maintaining good distance and size.

The algebraic curve \(\cal X\) used for this construction is the set of zeroes of one or more nontrivial polynomials forming a prime ideal. Such curves are both smooth and irreducible over any field extension of \(GF(q)\). The curve can be defined over affine space or projective space, which contains the affine coordinates as a subset and which can yield an increase in length. If evaluations are made over projective coordinates, then the codewords are evaluations of homogeneous polynomials, and there are relations between such polynomials with polynomials over affine space. See Refs. [1–4] for more details.

Protection

A lower bound on distance is \(d \geq n- \deg (D)\) [5; Thm. 15.3.12]. The order or Feng-Rao bound, a generalization of the shift bound for cyclic codes, gives a lower bound on the distance of evaluation AG codes [6–8]. Connection to semigroups yields another bound [3,9].

Decoding

Generalization of plane-curve decoder [10]. Another decoder [11] was later showed to be equivalent in Ref. [12]. Application of several algorthims in parallel can be used to decode up to half the minimum distance [13,14]. Computational procedure implementing these decoders is based on an extension of the Berlekamp-Massey algorithm by Sakata [15–17].Decoder based on majority voting of unknown syndromes [6] decodes up to half of the minimum distance [18].List decoders generalizing Sudan's RS decoder by Shokrollahi-Wasserman [19] and Guruswami-Sudan [20].

Notes

See Refs. [3,5,21–23] for surveys and overviews of decoders.

Parents

Children

  • Elliptic code — Elliptic codes are evaluation AG codes with \(\cal X\) being an elliptic curve, i.e., curve of genus one [1,3][2; Ch. 3.2].
  • Hermitian code — Hermitian codes are evaluation AG codes with \(\cal X\) being a Hermitian curve [23][3; Ex. 2.74]. This curve is maximal, meaning that Hermitian codes are evaluation AG codes with maximum possible length given a fixed genus.
  • Klein-quartic code — Klein-quartic codes are evaluation AG codes with \(\cal X\) being the Klein quartic ([3], Ex. 2.75)[2].
  • Plane-curve code — Plane-curve codes are evaluation AG codes of bivariate polynomials with \(\cal X\) being an affine plane curve ([3], Thm. 2.27)[2].
  • Suzuki-curve code — Suzuki-curve codes are evaluation AG codes with \(\cal X\) being a Suzuki curve.
  • Residue AG code — Any residue AG code of differential forms can be equivalently stated as an evaluation AG code of functions [1,2][5; Lemma 15.3.10][3; Thm. 2.72]. In addition, evaluation and residue AG codes are dual to each other [3][5; pg. 313].
  • Tsfasman-Vladut-Zink (TVZ) code — TVZ codes are evaluation AG codes where \(\cal X\) is either a Drinfeld modular curve, a classic modular curve, or a Garcia-Stichtenoth curve, but can also be formulated as residue AG codes.
  • Generalized RS (GRS) code — GRS (RS) codes are in one-to-one correspondence with evaluation AG codes of univariate polynomials \(f\) with \(\cal X\) being the projective (affine) line [1,3][5; Thm. 15.3.24][2; Ch. 3.2].
  • Tamo-Barg-Vladut code — Tamo-Barg-Vladut codes are evaluation AG codes on algebraic curves, such as Hermitian or Garcia-Stichtenoth curves.
  • Hexacode — The hexacode is an evaluation AG code over the quaternary Galois field \(GF(4) = \{0,1,\omega, \bar{\omega}\}\) with \(\cal X\) defined by \(x^2 y + \omega y^2 z + \bar{\omega} z^2 x = 0\) [3; Ex. 2.77].

Cousins

  • Linear \(q\)-ary code — The degree of the divisor for evaluation AG codes is restricted to be less than \(n\). When there is no restriction, any \(q\)-ary linear code can be formulated as an evaluation AG code [24].
  • Frameproof (FP) code — Asymptotic bounds on FP codes can be formulated using evaluation AG codes [25,26]. A sufficient condition for an evaluation AG code to be FP can be recast as an instance of the Riemann-Roch equation [27; Sec. 15.8.2].

References

[1]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[2]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[3]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[4]
M. Tomlinson et al., Error-Correction Coding and Decoding (Springer International Publishing, 2017) DOI
[5]
A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[6]
G.-L. Feng and T. R. N. Rao, “Decoding algebraic-geometric codes up to the designed minimum distance”, IEEE Transactions on Information Theory 39, 37 (1993) DOI
[7]
R. Pellikaan, “The shift bound for cyclic, Reed-Muller and geometric Goppa codes”, Arithmetic, Geometry, and Coding Theory DOI
[8]
P. Beelen, “The order bound for general algebraic geometric codes”, Finite Fields and Their Applications 13, 665 (2007) DOI
[9]
T. Johnsen, S. Manshadi, and N. Monzavi, “A determination of the parameters of a large class of Goppa codes”, IEEE Transactions on Information Theory 40, 1678 (1994) DOI
[10]
J. Justesen et al., “Construction and decoding of a class of algebraic geometry codes”, IEEE Transactions on Information Theory 35, 811 (1989) DOI
[11]
S. C. Porter, B.-Z. Shen, and R. Pellikaan, “Decoding geometric Goppa codes using an extra place”, IEEE Transactions on Information Theory 38, 1663 (1992) DOI
[12]
D. Ehrhard, “Decoding Algebraic-Geometric Codes by solving a key equation”, Lecture Notes in Mathematics 18 (1992) DOI
[13]
R. Pellikaan, “On a decoding algorithm for codes on maximal curves”, IEEE Transactions on Information Theory 35, 1228 (1989) DOI
[14]
S. Vladut, “On the decoding of algebraic-geometric codes over F/sub q/ for q<or=16”, IEEE Transactions on Information Theory 36, 1461 (1990) DOI
[15]
S. Sakata, “Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array”, Journal of Symbolic Computation 5, 321 (1988) DOI
[16]
S. Sakata, “Extension of the Berlekamp-Massey algorithm to N dimensions”, Information and Computation 84, 207 (1990) DOI
[17]
S. Sakata, “Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm”, IEEE Transactions on Information Theory 37, 1200 (1991) DOI
[18]
D. Ehrhard, “Achieving the designed error capacity in decoding algebraic-geometric codes”, IEEE Transactions on Information Theory 39, 743 (1993) DOI
[19]
M. A. Shokrollahi and H. Wasserman, “List decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 45, 432 (1999) DOI
[20]
V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) DOI
[21]
T. Hoholdt and R. Pellikaan, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 41, 1589 (1995) DOI
[22]
P. Beelen and T. Høholdt, “The Decoding of Algebraic Geometry Codes”, Series on Coding Theory and Cryptology 49 (2008) DOI
[23]
R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves (Cambridge University Press, 2001) DOI
[24]
R. Pellikan, B.-Z. Shen, and G. J. M. van Wee, “Which linear codes are algebraic-geometric?”, IEEE Transactions on Information Theory 37, 583 (1991) DOI
[25]
Chaoping Xing, “Asymptotic bounds on frameproof codes”, IEEE Transactions on Information Theory 48, 2991 (2002) DOI
[26]
H. Randriambololona, “(2,1)-separating systems beyond the probabilistic bound”, (2012) arXiv:1010.5764
[27]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: evaluation

Cite as:
“Evaluation AG code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/evaluation
BibTeX:
@incollection{eczoo_evaluation, title={Evaluation AG code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/evaluation} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/evaluation

Cite as:

“Evaluation AG code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/evaluation

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/ag/evaluation.yml.