Here is a list of evaluation codes.
| Code | Description |
|---|---|
| Complete-intersection RM-type code | Evaluation code of polynomials evaluated on points lying on a complete intersection. |
| Deligne-Lusztig code | Evaluation code of polynomials evaluated on points lying on a Deligne-Lusztig variety, often a Deligne-Lusztig curve in the classical one-dimensional cases. |
| Elliptic code | Evaluation AG code of rational functions evaluated on points lying on an elliptic curve, i.e., a curve of genus one. |
| Evaluation AG code | Evaluation code over \(\mathbb{F}_q\) on a set of points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) lying on an algebraic curve \(\cal X\) defined over \(\mathbb{F}_q\), where the corresponding vector space \(L\) of functions \(f\) consists of certain rational functions (or, in special cases, polynomials). |
| Evaluation code | 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. |
| Extended GRS code | A GRS code extended by one extra coordinate to form an \([n+1,k,n-k+2]_q\) MDS code. In projective language, this corresponds to adding one more evaluation point, often interpreted as the point at infinity; in suitable equivalent descriptions, one may instead use an affine point such as \(0\). The case when \(n=q-1\), multipliers \(v_i=1\), and \(\alpha_i\) are \(i-1\)st powers of a primitive \(n\)th root of unity is an extended narrow-sense RS code. |
| Flag-variety code | Evaluation code of polynomials evaluated on points lying on a flag variety. |
| Generalized RM (GRM) code | Extensions of RM codes to \(q\)-ary coordinates that can be described as multivariate polynomial evaluation codes over affine or projective space. |
| Generalized RS (GRS) code | An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors [1; Def. 15.3.19]. |
| Grassmannian evaluation code | Evaluation code of polynomials evaluated on points lying on a finite-field Grassmannian embedded into projective space using the Plucker embedding [2,3]. |
| Hansen toric code | Evaluation code of a linear space of polynomials evaluated on points lying on an affine or projective toric variety. If the space is taken to be all polynomials up to some degree, the code is called a toric RM-type code of that degree. |
| Hermitian code | Evaluation AG code of rational functions on a Hermitian curve over \(\mathbb{F}_{q^2}\). |
| Hermitian-hypersurface code | Evaluation code of polynomials evaluated on points lying on a Hermitian hypersurface. |
| Hyperbolic evaluation code | An evaluation code over polynomials in two variables. Generator matrices are determined in Ref. [4] following initial formulations of the codes as generalized concatenations of RS codes [5,6]; see [7; Exam. 4.26]. |
| Klein-quartic code | Evaluation AG code over \(\mathbb{F}_8\) of rational functions evaluated on points lying on the Klein quartic, which is defined by the equation \(x^3 y + y^3 z + z^3 x = 0\) [7; Ex. 2.75]. |
| Narrow-sense RS code | An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(\mathbb{F}_q\). |
| Norm-trace code | Evaluation AG code of rational functions evaluated on points lying on a Miura-Kamiya curve in either affine or projective space. The family is named as such because the equations defining the curves can be expressed in terms of the field norm and field trace. |
| Plane-curve evaluation code | Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine or projective plane curve. |
| Polynomial evaluation code | Evaluation code of polynomials (or, more generally, rational functions) at points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic variety \(\cal X\) of dimension greater than one (i.e., not an algebraic curve). |
| Projective RM (PRM) code | Evaluation code obtained by evaluating homogeneous polynomials on the points of the projective space \(PG(m,q)\), equivalently on representatives of the nonzero vectors in \(\mathbb{F}_q^{m+1}\) whose leftmost nonzero coordinate is one. |
| Quadric code | Evaluation code of polynomials evaluated on points lying on a quadric hypersurface. |
| Reed-Muller (RM) code | Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(\mathbb{F}_q\). |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. Majority decoding requires \(n\) to be odd in order to avoid ties. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. Its automorphism group is \(S_n\). |
| Residue AG code | Linear \(q\)-ary code defined using a set of \(\mathbb{F}_q\)-rational points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic curve \(\cal X\) and a linear space \(\Omega\) of certain rational differential forms \(\omega\) [1; Def. 15.3.2]. |
| Ruled-surface code | Evaluation code obtained by evaluating global sections of a line bundle, or equivalently suitable polynomial functions, on rational points of a ruled surface over a finite field. Such codes extend algebraic-geometry constructions from curves to certain projective surfaces [8,9]. |
| Schubert evaluation code | Evaluation code of polynomials evaluated on points lying on a Schubert variety. |
| Segre-variety RM-type code | Evaluation code of multihomogeneous polynomials evaluated on points of a Segre variety, i.e., on the Segre embedding of a product of projective spaces. These codes are Reed-Muller-type analogues adapted to product projective geometries [10]. |
| Suzuki-curve code | Evaluation AG code of rational functions evaluated on points lying on a Suzuki curve. |
| Tamo-Barg code | A family of \(q\)-ary polynomial evaluation codes that are optimal LRCs and for which \(q\) is comparable to \(n\). |
| Tamo-Barg-Vladut code | Evaluation AG code on algebraic curves built from a Galois cover \(\phi:Y\to X\), where the recovery sets are fibres over rational points of \(X\) that split completely in the cover [1; Def. 15.9.10][1; Thm. 15.9.14]. This generalizes the Tamo-Barg construction from \(PG(1,q)\) to longer AG codes, and variants can be built with higher local distance or availability \(2\) via fibre products of curves [1; Thm. 15.9.19][1; Thm. 15.9.21]. |
| Tsfasman-Vladut-Zink (TVZ) code | Member of a family of residue AG or, more generally, evaluation AG codes where \(\cal X\) is a Drinfeld modular curve, a classical modular curve, or a Garcia-Stichtenoth curve [1; Sec. 15.4.2]. |
| \([2^m,2^m-m-1,4]\) Extended Hamming code | Member of an infinite family of RM\((m-2,m)\) codes with parameters \([2^m,2^m-m-1, 4]\) for \(m \geq 2\) that are extensions of the Hamming codes by a parity-check bit. |
| \([2^m,m+1,2^{m-1}]\) First-order RM code | A member of the family of first-order RM codes. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). The family is self-orthogonal for \(m \geq 3\) [11]. They form a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping. |
| \([2^m-1,m,2^{m-1}]\) simplex code | A member of the equidistant code family dual to the \([2^m-1,2^m-m-1,3]\) Hamming family. |
| \([4,2,3]_3\) Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [12]. Its weight enumerator is the Gleason polynomial \(g_4\) [13; Rem. 4.2.6]. |
| \([4,2,3]_4\) RS\(_4\) code | A Type II Euclidean self-dual extended RS code that is the smallest quaternary extended QR code [14; pg. 296][15; Sec. 2.4.2]. |
| \([6,3,4]_4\) Hexacode | The \([6,3,4]_4\) Hermitian self-dual MDS code that has connections to projective geometry, lattices [12], and conformal field theory [16]. Its weight enumerator is the Gleason polynomial \(g_7\) [13; Rem. 4.2.6]. |
| \([7,3,4]\) simplex code | Second-smallest nontrivial member of the simplex-code family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(2,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((8,9)\) simplex spherical code under the antipodal mapping. As a simplex code, it is equidistant: every nonzero codeword has Hamming weight \(4\). |
| \([8,4,4]\) extended Hamming code | Extension of the \([7,4,3]\) Hamming code by a parity-check bit. The smallest doubly even self-dual code, and the unique Type II code of length \(8\) [13; Rem. 4.3.10]. |
| \([n,n-1,2]\) Single parity-check (SPC) code | An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings, and its parity-check matrix is a row vector of all ones. Its automorphism group is \(S_n\). |
| \([n,n-1,2]_q\) \(q\)-ary parity-check code | An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check or zero-sum check digit such that the sum over all coordinates of each codeword is zero. |
| \(q\)-ary repetition code | An \([n,1,n]_q\) code consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\). |
| \(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) equidistant projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. All nonzero simplex codewords have a constant weight of \(q^{m-1}\) [17,18]. |
References
- [1]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI
- [3]
- V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
- [4]
- O. Geil and T. Høholdt, “On Hyperbolic Codes”, Lecture Notes in Computer Science 159 (2001) DOI
- [5]
- K. Saints and C. Heegard, “On hyperbolic cascaded Reed-Solomon codes”, Lecture Notes in Computer Science 291 (1993) DOI
- [6]
- Gui-Liang Feng and T. R. N. Rao, “Improved geometric Goppa codes. I. Basic theory”, IEEE Transactions on Information Theory 41, 1678 (1995) 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]
- S. H. Hansen, “Error-Correcting Codes from Higher-Dimensional Varieties”, Finite Fields and Their Applications 7, 530 (2001) DOI
- [9]
- C. Lomont, “Error Correcting Codes on Algebraic Surfaces”, (2003) arXiv:math/0309123
- [10]
- M. González-Sarabia, C. Renterı́a, and H. Tapia-Recillas, “Reed-Muller-Type Codes Over the Segre Variety”, Finite Fields and Their Applications 8, 511 (2002) DOI
- [11]
- M. Shi, S. Li, T. Helleseth, and J.-L. Kim, “Binary self-orthogonal codes which meet the Griesmer bound or have optimal minimum distances”, (2023) arXiv:2303.16729
- [12]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [13]
- S. Bouyuklieva, “Self-dual codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [14]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [15]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [16]
- J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI
- [17]
- A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
- [18]
- E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI