Evaluation code[1,2] 

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 binary or \(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, i.e., sets of solutions of systems of polynomial equations in either affine or projective space. The functions \(f\) are typically polynomials or rational functions.

Protection

Properties of \(\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 [3–7]; see Ref. [7], Ch. 4 and Ref. [8] for more discussion.

Notes

See books [7,9–12] for more information.

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 ([7], Sec. 4.1; [9], Prop. 1.1.4).

Children

  • Evaluation AG code — Evaluation AG codes are evaluation codes of rational functions \(f\) for which \(\cal X\) is an algebraic curve, i.e., an algebraic variety of dimension one [7].
  • Polynomial evaluation code — Polynomial evaluation codes are evaluation codes of polynomials \(f\) for which \(\cal X\) is an algebraic variety.

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 yields a projective code.

References

[1]
S. G. Vléduts and Yu. I. Manin, “Linear codes and modular curves”, Journal of Soviet Mathematics 30, 2611 (1985) DOI
[2]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[3]
O. Geil, “Evaluation Codes from an Affine Variety Code Perspective”, Series on Coding Theory and Cryptology 153 (2008) DOI
[4]
Gui-Liang Feng et al., “Simplified understanding and efficient decoding of a class of algebraic-geometric codes”, IEEE Transactions on Information Theory 40, 981 (1994) DOI
[5]
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
[6]
J. Fitzgerald and R. F. Lax, Designs, Codes and Cryptography 13, 147 (1998) DOI
[7]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[8]
J. B. Little, “Algebraic geometry codes from higher dimensional varieties”, (2008) arXiv:0802.2349
[9]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[10]
H. Stichtenoth, Algebraic Function Fields and Codes (Springer Berlin Heidelberg, 2009) DOI
[11]
V. D. Goppa, Geometry and Codes (Springer Netherlands, 1988) DOI
[12]
Lachaud, G. (1985). Les codes géométriques de Goppa. Sem. Bourbaki, 37, 1984-85.
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: evaluation_varieties

Cite as:
“Evaluation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/evaluation_varieties
BibTeX:
@incollection{eczoo_evaluation_varieties,
  title={Evaluation code},
  booktitle={The Error Correction Zoo},
  year={2022},
  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.), 2022. https://errorcorrectionzoo.org/c/evaluation_varieties

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