Evaluation code[1–3]

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].