| Algebraic-geometry (AG) code |
Binary or \(q\)-ary code constructed from an algebraic curve of some genus over a finite field via the evaluation construction, the residue construction, or more general constructions that yield nonlinear codes. Linear AG codes from the first two constructions are also called geometric Goppa codes. |
Near MDS \([n,k,d]_{GF(p^m)}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [1][2]. |
| Anticode |
Code for which the distance between any two codewords is less than or equal to some value \(\delta\) called the maximum distance. Anticodes can be used to construct codes that saturate the Griesmer bound; see Refs. [3][2][4] for more details. |
|
| 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\). |
|
| 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. |
|
| Divisible code |
A linear binary or \(q\)-ary code is \(\Delta\)-divisible if the Hamming weight of each of its codewords is divisible by divisor \(\Delta\). A \(2\)-divisible (\(4\)-divisible) code is called even (doubly even) [5]. A code is called singly even if all codewords are even and at least one has weight equal to 2 modulo 4. |
|
| Dual linear code |
For any \([n,k]\) binary or \(q\)-ary linear code \(C\), the dual (or orthogonal) code, \begin{align}
C^\perp = \{ y\in GF(q)^{n} ~|~ x\cdot y=0 \forall x\in C\},
\end{align} where the ordinary, standard, or Euclidean inner product is \(x\cdot y = \sum_{i=1}^n x_i y_i\) for coordinates \(x_i,y_i\). |
A linear binary or \(q\)-ary \([n,k,n-k+1]\) code is MDS if and only if its dual \([n,n-k,k+1]\) is MDS ([6], Thm. 1.9.13). |
| Elliptic code |
Evaluation AG code of rational functions evaluated on points lying on an elliptic curve, i.e., a curve of genus one. |
Elliptic codes can be MDS ([6], Ex. 15.5.3; [1], pg. 310; [7], Sec. 4.4.2). |
| 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. |
An MDS GRS code can be extended to an MDS code ([8], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([8], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [9]. |
| 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} |
GRS codes have distance \(n-k+1\), saturating the Singleton bound. |
| Grassmannian code |
Evaluation code of polynomials evaluated on points lying on a Grassmannian \({\mathbb{G}}(\ell,m)\). |
|
| Griesmer code |
A \([n,k,d]\) binary or \(q\)-ary linear code is a Griesmer code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Griesmer bound \begin{align}
n\geq\sum_{j=0}^{k-1}\left\lceil \frac{d}{q^{j}}\right\rceil ~,
\end{align} where \(\left\lceil x\right\rceil \) is the ceiling function, becomes an equality. |
Singleton bound implies the Griesmer bound. |
| 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 [10] and conformal field theory [11]. |
|
| Matrix computation code |
Encoding that provides an extra redundancy for distributed matrix computation algorithms such as matrix multiplication. Parallelized algorithms distribute a desired computation over many nodes, and a key performance bottleneck is due to some nodes completing their individual tasks much later than other nodes. Matrix computation codes provide a layer of redundancy such that the computation can be performed without having all nodes finish their piece of the computation. |
The first matrix multiplication code encoded each entry of the matrices to be multiplied into an MDS code [12]. |
| Maximum distance separable (MDS) code |
A \([n,k,d]_q\) \(q\)-ary linear code is an MDS code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the Singleton bound \begin{align}
d \leq n-k+1
\end{align} becomes an equality. A code is called almost MDS (AMDS) when \(d=n-k\). A bound for general \(q\)-ary codes can also be formulated; see Thm. 1.9.10 in Ref. [6]. A code is near MDS (NMDS) if the code and its dual are mode AMDS. |
|
| Maximum-rank distance (MRD) code |
Also called an optimal rank-distance code. An \([n\times m,k,d]_q\) rank-metric code whose parameters are such that the Singleton-like bound \begin{align}
k \leq \max(n, m) (\min(n, m) - d + 1)
\end{align} become an equality. |
MRD codes are matrix-code analogues of MDS codes. |
| Parity-check code |
Also known as a sum-zero 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. |
|
| 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 [13] \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. |
A linear code is MDS (almost MDS) if and only if columns of its parity-check matrix form an \(n\)-arc (\(n\)-track) in projective space [14][15]. The dual of a MDS code is an MDS code, so MDS codes are projective. |
| Quantum maximum-distance-separable (MDS) code |
An \(((n,q^k,d))\) code constructed out of \(q\)-dimensional qudits is an MDS code if parameters \(n\), \(k\), \(d\), and \(q\) are such that the quantum Singleton bound \begin{align}
2(d-1) \leq n-k
\end{align} becomes an equality. |
|
| 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} |
RS codes have distance \(n-k+1\), saturating the Singleton bound. If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [9]. |
| 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\). |
|
| 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 [10]. |
|
| \(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. |
|