Here is a list of code families which contain MDS codes.
Code | Description | MDS Detail |
---|---|---|
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. [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 \(q\)-ary block 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,6]. 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]_q\) 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\}, \tag*{(1)}\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 [7; 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 [8; Ex. 15.5.3][1; pg. 310][9; 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. | A GRS code can be extended to an MDS code ([10], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([10], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [11]. |
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} | 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]_q\) 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 ~, \tag*{(3)}\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]_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*{(4)}\end{align} where \(GF(4) = \{0,1,\omega, \bar{\omega}\}\). Has connections to projective geometry, lattices [6], and conformal field theory [12]. | The hexacode is an MDS code [10; Exer. 578]. |
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 [13]. |
Maximum distance separable (MDS) code | A \([n,k,d]_q\) binary or \(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 \tag*{(5)}\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 [7; Thm. 1.9.10]. 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) \tag*{(6)}\end{align} become an equality. | MRD codes are matrix-code analogues of MDS codes. |
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 [14] \begin{align} \left[ q^m+q^{m-1}\cdots +1, {m+r \choose r},(q+1-r)q^{m-1} \right]~. \tag*{(7)}\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 [15,16]. 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 \tag*{(8)}\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}. \tag*{(9)}\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*{(10)}\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 [11]. |
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\). | |
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. | |
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*{(11)}\end{align} where \(GF(3) = \{0,1,2\}\). Has connections to lattices [6]. | |
\([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*{(12)}\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]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [2]
- I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
- [3]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [4]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [5]
- S. Kurz, “Divisible Codes”, (2022) arXiv:2112.11763
- [6]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [7]
- W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [9]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [10]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [11]
- S. Ball, “On sets of vectors of a finite vector space in which every subset of basis size is a basis”, Journal of the European Mathematical Society 733 (2012) DOI
- [12]
- 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
- [13]
- K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
- [14]
- G. Lachaud, “Number of points of plane sections and linear codes defined on algebraic varieties”, Arithmetic, Geometry, and Coding Theory DOI
- [15]
- S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory DOI
- [16]
- J. W. P. Hirschfeld and L. Storme, “The Packing Problem in Statistics, Coding Theory and Finite Projective Spaces: Update 2001”, Developments in Mathematics 201 (2001) DOI