Evaluation AG code

Description

Also called a function code. 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 a nontrivial polynomial that is 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][2] for more details.

In the case of polynomial functions \(f\), evaluation AG codes reduce to polynomial evaluation codes on algebraic curves. In the general case of rational functions, which are ratios of two polynomials, one can select such features for both the numerator and denominator polynomials. Zeroes of the denominator polynomial are called poles of the rational function, and their multiplicities correspond to orders of the poles. A bookkeeping device for this data is the divisor \(D\), and the corresponding vector space of functions defined using the curve \(\cal X\) and the divisor is the Riemann-Roch space \(L=L(D)\) ([3], pg. 313).

Protection

Riemann-Roch theorem yields code length \(n\), dimension \(k\), and a lower bound on distance in terms of features of \(L\) and genus of the curve \(\cal X\) ([3], 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 [4][5][6]. Connection to semigroups yields another bound [7][1].

Decoding

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

Notes

See Refs. [1][20][21][3][22] 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 ([23], Ch. 3.2; [1]).
  • Hermitian code — Hermitian codes are evaluation AG codes with \(\cal X\) being a Hermitian curve ([1], 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 ([1], Ex. 2.75).
  • Plane-curve code — Plane-curve codes are evaluation AG codes of bivariate polynomials with \(\cal X\) being an affine plane curve ([1], Thm. 2.27).
  • 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 ([3], Lemma 15.3.10; [1], Thm. 2.72). In addition, evaluation and residue AG codes are dual to each other ([3], pg. 313; [1]).
  • 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 ([3], Thm. 15.3.24; [23], Ch. 3.2; [1]).
  • Hexacode — The hexacode is an evaluation AG code over \(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\) ([1], 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].
  • Polynomial evaluation code — Evaluation AG codes are evaluation codes on algebraic curves. Polynomial evaluation codes are evaluation codes of polynomials. Evaluation AG codes of polynomials are equivalent to polynomial evaluation codes on algebraic curves.

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. Tomlinson et al., Error-Correction Coding and Decoding (Springer International Publishing, 2017) DOI
[3]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[4]
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
[5]
R. Pellikaan, “The shift bound for cyclic, Reed-Muller and geometric Goppa codes”, Arithmetic, Geometry, and Coding Theory DOI
[6]
P. Beelen, “The order bound for general algebraic geometric codes”, Finite Fields and Their Applications 13, 665 (2007) DOI
[7]
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
[8]
A. N. Skorobogatov and S. G. Vladut, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 36, 1051 (1990) DOI
[9]
V. Yu. Krachkovskii, "Decoding of codes on algebraic curves," (in Russian), Conference Odessa, 1988.
[10]
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
[11]
D. Ehrhard, “Decoding Algebraic-Geometric Codes by solving a key equation”, Lecture Notes in Mathematics 18 (1992) DOI
[12]
R. Pellikaan, “On a decoding algorithm for codes on maximal curves”, IEEE Transactions on Information Theory 35, 1228 (1989) DOI
[13]
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
[14]
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
[15]
S. Sakata, “Extension of the Berlekamp-Massey algorithm to N dimensions”, Information and Computation 84, 207 (1990) DOI
[16]
S. Sakata, “Decoding binary 2-D cyclic codes by the 2-D Berlekamp-Massey algorithm”, IEEE Transactions on Information Theory 37, 1200 (1991) DOI
[17]
D. Ehrhard, “Achieving the designed error capacity in decoding algebraic-geometric codes”, IEEE Transactions on Information Theory 39, 743 (1993) DOI
[18]
M. A. Shokrollahi and H. Wasserman, “List decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 45, 432 (1999) DOI
[19]
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
[20]
T. Hoholdt and R. Pellikaan, “On the decoding of algebraic-geometric codes”, IEEE Transactions on Information Theory 41, 1589 (1995) DOI
[21]
P. Beelen and T. Høholdt, “The Decoding of Algebraic Geometry Codes”, Series on Coding Theory and Cryptology 49 (2008) DOI
[22]
R. E. Blahut, Algebraic Codes on Lines, Planes, and Curves (Cambridge University Press, 2001) DOI
[23]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) 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
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: evaluation

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

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