| 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\). |
| Ben-Sasson-Sudan code |
Locally testable \([[n,k/2,d]]_{2^m}\) code with \(k\) a power of two, \(n = k \log^{c} k\), and query complexity \(\log^{c}k\) for some universal constant \(c\). |
| 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} \). |
| Cyclic linear \(q\)-ary code |
A \(q\)-ary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=q^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
| Denniston code |
Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{GF(2^a)}\) codes for \(i < a\) constructed using Denniston arcs. |
| Dodecacode |
Self-dual \([12,6,6]_{GF(4)}\) code whose codewords are cyclic permutations of \((\omega 10100100101)\), where \(GF(4)=\{0,1,\omega,\bar{\omega}\}\). |
| 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~.
\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. |
| 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. |
| Folded RS (FRS) code |
A linear \([n/m,k]_{q^m}\) code that is a modification of an \([n,k]_q\) RS code such that evaluations are grouped to yield a code with smaller length. In this case, the evaluation points are all powers of a generating field element \(\gamma\), \(\alpha_i=\gamma^i\). Each codeword \(\mu\) of an \(m\)-folded RS code is a string of \(n/m\) symbols, with each symbol being a string of values of a polynomial \(f_\mu\) at consecutive powers of \(\gamma\), \begin{align}
\begin{split}
\mu\to&\Big(\left(f_{\mu}(\alpha^{0}),\cdots,f_{\mu}(\alpha^{m-1})\right),\left(f_{\mu}(\alpha^{m}),\cdots,f_{\mu}(\alpha^{2m-1})\right)\cdots\\&\cdots,\left(f_{\mu}(\alpha^{n-m}),\cdots,f_{\mu}(\alpha^{n-1})\right)\Big)~.
\end{split}
\end{align} |
| Gabidulin code |
Also called a vector rank-metric code. A linear code over \(GF(q^N)\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(GF(q^N)\) can be written as an \(N\)-dimensional vector with coefficients in \(GF(q)\), and the rank of a set of elements is rank of the matrix formed by their coefficients. |
| 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)~.
\end{align} |
| 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\). |
| Hexacode |
The \([6,3,4]_{GF(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}~,
\end{align} where \(GF(4) = \{0,1,\omega, \bar{\omega}\}\). Has connections to projective geometry, lattices [1] and conformal field theory [2]. |
| Incidence-matrix projective code |
Code whose generator matrix is the incidence matrix of points and hyperplanes of a projective spaces. Has been generalized to incidence matrices of other structures ([3][4]; [5], Sec. 14.4). |
| Interleaved RS (IRS) code |
A modification of RS codes where multiple polynomials are used to define each codeword. Each codeword \(\mu\) of a \(t\)-interleaved RS code is a string of values of the corresponding set \(\{f_\mu^{(1)},f_\mu^{(2)},\cdots,f_\mu^{(t)}\}\) of \(t\) polynomials at the points \(\alpha_i\). The vector codewords can be arranged in an array whose rows are ordinary RS codes for each polynomial \(f^{j}\), yielding the encoding \begin{align}
\mu\to\left(
\begin{array}{cccc}
f_{\mu}^{(1)}\left(\alpha_{1}\right) & f_{\mu}^{(1)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(1)}\left(\alpha_{n}\right)\\
f_{\mu}^{(2)}\left(\alpha_{1}\right) & f_{\mu}^{(2)}\left(\alpha_{2}\right) & & f_{\mu}^{(2)}\left(\alpha_{n}\right)\\
\vdots & & \ddots & \vdots\\
f_{\mu}^{(t)}\left(\alpha_{1}\right) & f_{\mu}^{(t)}\left(\alpha_{2}\right) & \cdots & f_{\mu}^{(t)}\left(\alpha_{n}\right)
\end{array}\right)~.
\end{align} |
| 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\) ([6], Ex. 2.75). |
| Linear \(q\)-ary code |
An \((n,K,d)_q\) linear code is denoted as \([n,k,d]_q\), where \(k=\log_{q}K\) need not be an integer. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(\alpha x+ \beta y\) is also a codeword for any \(q\)-ary digits \(\alpha,\beta\). |
| Meir code |
Locally testable \([[n,k,d]]_q\) code with query complexity \(\text{poly}(\log k)\) and rejection ratio \(R/n = 1/\text{poly}(\log k)\). Code construction is probabilistic and combinatorial. |
| Parvaresh-Vardy (PV) code |
Also called a correlated RS code. An IRS code with additional algebraic relations (a.k.a. correlations) between the codeword polynomials \(\{f^{(j)}\}_{j=1}^{t}\). These relations yielded a list decoder that achieves list-decoding capacity. |
| Plane-curve code |
Evaluation AG code of bivariate polynomials of some finite maximum degree, evaluated at points lying on an affine plane curve. |
| 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 [7] \begin{align}
\left[ q^m+q^{m-1}\cdots +1, {m+r \choose r},(q+1-r)q^{m-1} \right]~.
\end{align} |
| Projective geometry code |
Linear \(q\)-ary \([n,k,d]\) code such that columns of its generator matrix \(G\) does not contain any repeated columns or the zero column. That way, each column corresponds to a distinct point in the projective space \(PG(k-1,q)\) arising from a \(k\)-dimensional vector space over \(GF(q)\). If the columns are linearly independent, then the codewords are collectively called an information set. Columns of a code's parity-check matrix can similarly correspond to points in projective space. This formulation yields connections to projective geometry, which can be applied to determine code properties. |
| 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}.
\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) \,.
\end{align} |
| 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~.
\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. |
| Simplex code |
Also known as a maximum length feedback shift register code. An \([n,k,q^{k-1}]_q\) projective code with \(n=\frac{q^k-1}{q-1}\), denoted as \(S(q,k)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(k-1,q)\), with each column being a chosen representative of the corresponding element. Its dual code is the \([n,n-k,3]_q\) \(q\)-ary Hamming code. The name of the code comes from the property that, for \(q=2\), the codewords form a \((2^k-1)\)-simplex of constant edge length if the codewords are interpreted as points in \(\mathbb{R}^n\). |
| Suzuki-curve code |
Evaluation AG code of rational functions evaluated on points lying on a Suzuki curve. |
| Ternary Golay Code |
A \([11,6,5]_{GF(3)}\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [1] and sporadic simple groups [8]. Adding a parity bit to the code results in the \([12, 6, 6]\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters. |
| Tetracode |
The \([4,2,3]_{GF(3)}\) self-dual MDS code with generator matrix \begin{align}
\begin{pmatrix}1 & 0 & 1 & 1\\
0 & 1 & 1 & 2
\end{pmatrix}~,
\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. |
| Wozencraft ensemble code |
Stub. |
| \(q\)-ary Hamming code |
Member of an infinite family of perfect linear \(q\)-ary codes with parameters \([(q^r-1)/(q-1),(q^r-1)/(q-1)-r, 3]_q\) for \(r \geq 2\). |
| \(q\)-ary duadic code |
Member of a pair of cyclic linear binary codes that satisfy certain relations, depending on whether the pair is even-like or odd-like duadic. Duadic codes exist only when \(q\) is a square modulo \(n\) [9]. |
| \(q\)-ary linear LTC |
A \(q\)-ary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(q)^{r\times n}\) have weight at most \(u\) and if \begin{align}
\frac{1}{r}|H x| \geq \frac{R}{n} D(x,C)
\end{align} holds for any \(q\)-ary string \(x\), where \(D(x,C)\) is the \(q\)-ary Hamming distance between \(x\) and the closest codeword to \(x\) [10; Def. 11]. |
| \(q\)-ary parity-check code |
Also known as a sum-zero code. An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check digit such that the sum over all coordinates of each codeword is zero. |
| \(q\)-ary quadratic-residue (QR) code |
Member of a quadruple of cyclic \(q\)-ary codes of prime length \(n\) where \(q\) is prime and a quadratic residue modulo \(n\). The codes are constructed using quadratic residues and nonresidues of \(n\). |