Here is a list of evaluation codes.
| Code | Description |
|---|---|
| Alternant code | Given a length-\(n\) GRS code \(C\) over \(GF(q^m)\), an alternant code is the \(GF(q)\)-subfield subcode of the dual of \(C\). |
| Binary BCH code | Cyclic binary code of odd length \(n\) whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\) (see Cyclic-to-polynomial correspondence). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=2^r-1\) for some \(r\geq 2\). |
| Bose–Chaudhuri–Hocquenghem (BCH) code | Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively coprime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). |
| Cartier code | Subcode of a certain residue AG code that is constructed using the Cartier operator. |
| Classical Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \). |
| 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. |
| 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 | 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. |
| 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 with an additional parity-check coordinate with corresponding evaluation point of zero. In other words, an \([n+1,k,n-k+2]_q\) GRS code whose polynomials are evaluated at the points \((\alpha_1,\cdots,\alpha_n,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 | Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at a set of distinct points \(\{\alpha_1,\cdots,\alpha_n\}\) in \(GF(q)\). |
| 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. Each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), multiplied by a corresponding nonzero factor \(v_i \in GF(q)\), \begin{align} \mu\to\left( v_{1}f_{\mu}\left(\alpha_{1}\right),v_{2}f_{\mu}\left(\alpha_{2}\right),\cdots,v_{n}f_{\mu}\left(\alpha_{n}\right)\right)~. \tag*{(2)}\end{align} |
| Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [1] and sporadic simple groups [2]. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters. |
| Grassmannian code | Evaluation code of polynomials evaluated on points lying on a Grassmannian \({\mathbb{G}}(\ell,m)\). |
| Hamming code | Member of an infinite family of perfect linear codes with parameters \([2^r-1,2^r-r-1, 3]\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity-check matrix \(H\) has all possible non-zero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code. |
| 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 evaluated on points lying on a Hermitian curve \(H(x,y) = x^{q+1} + y^{q+1} - 1\) over \(\mathbb{F}_q = GF(q)\) in either affine or projective space. Hermitian codes directly improve over RS codes in the sense that RS codes have length at most \(q\) while Hermitian codes have length \(q^3 + 1\). |
| Hermitian-hypersurface code | Evaluation code of polynomials evaluated on points lying on a Hermitian hypersurface. |
| Hexacode | The \([6,3,4]_4\) self-dual MDS code with generator matrix \begin{align} \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & \omega\\ 0 & 1 & 0 & 1 & \omega & 1\\ 0 & 0 & 1 & \omega & 1 & 1 \end{pmatrix}~, \tag*{(3)}\end{align} where \(GF(4) = \{0,1,\omega, \bar{\omega}\}\). Has connections to projective geometry, lattices [1], and conformal field theory [3]. |
| Klein-quartic code | Evaluation AG code over \(GF(8)\) of rational functions evaluated on points lying in the Klein quartic, which is defined by the equation \(x^3 y + y^3 z + z^3 x = 0\) ([4], Ex. 2.75). |
| Plane-curve code | Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine plane curve. |
| Polynomial evaluation code | Evaluation code of polynomials at points \({\cal P} = \left( P_1,P_2,\cdots,P_n \right)\) on an algebraic variety \(\cal X\). Codewords \begin{align} \left( f(P_1), f(P_2), \cdots, f(P_n) \right) \tag*{(4)}\end{align} are evaluations of a linear space \(L\) of polynomials \(f\). If the space is taken to be all polynomials up to some degree, the code is called a Reed-Muller-type code or RM-type code of that degree. |
| Projective RM (PRM) code | Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates. PRM codes PRM\(_q(r,m)\) for \(r<q\) are injective evaluation codes with parameters [5] \begin{align} \left[ q^m+q^{m-1}\cdots +1, {m+r \choose r},(q+1-r)q^{m-1} \right]~. \tag*{(5)}\end{align} |
| 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 or more coordinates from each codeword. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). Let \(\{\alpha_1,\cdots,\alpha_n\}\) be \(n\) distinct points in \(GF(q)\). An RS code encodes a message \(\mu=\{\mu_0,\cdots,\mu_{k-1}\}\) into \(\{f_\mu(\alpha_1),\cdots,f_\mu(\alpha_n)\}\) using a message-dependent polynomial \begin{align} f_\mu(x)=\mu_0+\mu_1 x + \cdots + \mu_{k-1}x^{k-1}. \tag*{(6)}\end{align} In other words, each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), \begin{align} \mu\to\left( f_{\mu}\left(\alpha_{1}\right),f_{\mu}\left(\alpha_{2}\right),\cdots,f_{\mu}\left(\alpha_{n}\right)\right) \,. \tag*{(7)}\end{align} |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. |
| Residue AG code | Also called a differential code. Linear \(q\)-ary code defined using 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\) and a linear space \(\Omega\) of certain rational differential forms \(\omega\). Codewords are evaluations of residues of the differential forms in the specified points, \begin{align} \left(\text{Res}_{P_{1}}(\omega),\text{Res}_{P_{2}}(\omega),\cdots,\text{Res}_{P_{n}}(\omega)\right)\quad\quad\forall\omega\in\Omega~. \tag*{(8)}\end{align} The code is denoted as \(C_{\Omega}({\cal X},{\cal P},D)\), where the divisor \(D\) determines which rational rational differential forms to use. |
| Ruled-surface code | Evaluation code of polynomials evaluated on points lying on a ruled surface. |
| Schubert code | Evaluation code of polynomials evaluated on points lying on a Schubert variety. |
| Serge-variety RM-type code | Evaluation code of polynomials evaluated on points lying on a Serge variety. |
| Single parity-check (SPC) code | Also known as a sum-zero, zero-sum, or even-weight code. An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check 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. |
| 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\). |
| Tetracode | The \([4,2,3]_3\) self-dual MDS code with generator matrix \begin{align} \begin{pmatrix}1 & 0 & 1 & 1\\ 0 & 1 & 1 & 2 \end{pmatrix}~, \tag*{(9)}\end{align} where \(GF(3) = \{0,1,2\}\). Has connections to lattices [1]. |
| Tsfasman-Vladut-Zink (TVZ) code | Member of a family of residue AG codes where \(\cal X\) is either a reduction of a Shimura curve or an elliptic curve of varying genus. |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family with generator matrix \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)~. \tag*{(10)}\end{align} Up to equivalence, this is the only nontrivial length-seven perfect binary code containing the zero vector. |
| \(q\)-ary parity-check code | Also known as a sum-zero or zero-sum 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. |
References
- [1]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- 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
- [4]
- T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
- [5]
- G. Lachaud, “Number of points of plane sections and linear codes defined on algebraic varieties”, Arithmetic, Geometry, and Coding Theory DOI