Evaluation code[13] 

Description

Code whose codewords are evaluations of functions at certain fixed points. Code properties can be inferred from the structure of the functions and the underlying geometric object containing the points, often using results from algebraic geometry.

Let \(\cal{X}\) be a geometric object that contains a subset \({\cal P} = \left( P_1,P_2,\cdots,P_n \right) \) consisting of \(n\) points \(P_j\). Let \(L\) be a vector space over \(GF(q)\) of functions \(f\) that take values in \(GF(q)\). Each \(f\in L\) yields a codeword of an evaluation code \(C_L({\cal X},{\cal P})\) of the form \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \quad\quad\forall f\in L~. \tag*{(1)}\end{align} This is a linear \(q\)-ary code since the functions \(f\) take values in \(GF(q)\) and form a vector space.

Examples of geometric objects \(\cal X\) include affine or projective spaces over \(GF(q)\) as well as subsets of those spaces determined by some constraints. Prominent subsets are algebraic varieties, which, for algebraically closed fields, are sets of solutions of systems of polynomial equations in either affine or projective space. Algebraic curves are algebraic varieties of dimension one [1], and those used for this construction are sets of zeroes of one or more nontrivial polynomials forming a prime ideal.

The functions \(f\) are typically polynomials for the case of algebraic varieties, but can be promoted to rational functions to either define codes on projective coordinates and/or to determine code properties using results from algebraic geometry. For example, any degree-\(k\) univariate polynomial \(\sum_j^{k} p_j x^j\) is homogenized into a bivariate polynomial \(\sum_j^{k} p_j x^j y^{k-j}\) and divided by another bivariate polynomial of the same degree, giving rise to a homogeneous rational function, or form. Similar homogenization can be done for multivariate polynomials by adding an extra variable as above. Forms are the most general cases considered for evaluation codes since they encompass all polynomials via the reverse of the above procedure.

One can specify the space \(L\) by the number of variables input into the rational functions as well as their maximum degree. One can additionally select only functions that have zeroes at certain points with certain multiplicities. A bookkeeping device for this data is the divisor \(D\), and the corresponding vector space of functions defined using the variety \(\cal X\) and the divisor is the Riemann-Roch space \(L=L(D)\) [4; pg. 313]. Codes based on divisors with only one pole (of arbitrary order) are called one-point codes [1; Remark 4.4].

Protection

Properties of the underlying geometric object \(\cal X\) can be used to bound the code dimension \(k\) and distance \(d\). The order or Feng-Rao bound gives a lower bound on the distance of evaluation codes [1,5,6]; see [7][1; Ch. 4] for more discussion.

Notes

See books [1,2,810] for more information.See LMFDB [11] for a database of varieties.

Parent

  • Linear \(q\)-ary code — Evaluation codes are defined using polynomial or rational functions evaluated on a subset of affine or projective space. Given access to more general structures (i.e., morphisms of algebras), any \(q\)-ary linear code can be formulated as an evaluation code [1; Sec. 4.1][2; Prop. 1.1.4].

Children

  • Evaluation AG code — Evaluation AG codes are evaluation codes for which \(\cal X\) is an algebraic curve, i.e., an algebraic variety of dimension one [1].
  • Polynomial evaluation code — Polynomial evaluation codes are evaluation codes for which \(\cal X\) is an algebraic variety of dimension greater than one.

Cousins

  • Algebraic-geometry (AG) code — Evaluation codes on varieties can also be considered AG codes since they use algebraic geometry in quantifying code bounds. However, early AG constructions all used only one-dimensional varieties, i.e., algebraic curves.
  • Projective geometry code — Codewords of an evaluation code of multivariate polynomials up to degree one evaluated at points in projective space yield a projective code.

References

[1]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[2]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[3]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[4]
A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[5]
O. Geil, “Evaluation Codes from an Affine Variety Code Perspective”, Series on Coding Theory and Cryptology 153 (2008) 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]
J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
[8]
H. Stichtenoth, Algebraic Function Fields and Codes (Springer Berlin Heidelberg, 2009) DOI
[9]
V. D. Goppa, Geometry and Codes (Springer Netherlands, 1988) DOI
[10]
Lachaud, G. (1985). Les codes géométriques de Goppa. Sem. Bourbaki, 37, 1984-85.
[11]
The LMFDB Collaboration, The L-functions and modular forms database, https://www.lmfdb.org, 2024.
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: evaluation_varieties

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

Cite as:

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

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