Here is a list of codes related to MDS codes.

[Jump to code graph excerpt]

Code Description MDS Detail
Algebraic-geometry (AG) code Binary or \(q\)-ary code or subcode 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]_{p^m}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [1–3].
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–5] 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.
Distributed 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 [6].
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, \(8\)-divisible) code is called even (doubly even, triply even) [7,8]. A code is called singly even if all codewords are even and at least one has weight equal to 2 modulo 4. More generally, a code is \(m\)-even if it is \(2^{m}\)-divisible.
Dual linear code For any \([n,k]_q\) linear code \(C\), the dual code is the set of \(q\)-ary strings that are orthogonal to the codewords of \(C\) under a particular inner product. 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 [9; Thm. 1.9.13].
EA MDS code EA Galois-qudit code whose parameters make the EAQECC Singleton bound (a.k.a. qubit-ebit Singleton bound) [10; Thm. 6] become an equality. MDS codes give rise to families of EA Galois-qudit codes that saturate the original (erroneous) EAQECC Singleton bound [11].
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 [12; Exam. 15.5.3][2; pg. 310][1; 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 ([13], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([13], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [14].
Galois-qudit CSS code An \([[n,k,d]]_q \) Galois-qudit true stabilizer code admitting a set of stabilizer generators that are either \(Z\)-type or \(X\)-type Galois-qudit Pauli strings. Codes can be defined from chain complexes over \(GF(q)\) via an extension of qubit CSS-to-homology correspondence to Galois qudits.
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. GRS codes have distance \(n-k+1\), saturating the Singleton bound.
Generalized Srivastava code An \([n,k \geq n-mst,d \geq st+1 ]_q\) alternant code defined for \(n+s\) distinct elements \(\alpha_1,\alpha_2,\cdots,\alpha_n,w_1,w_2,\cdots,w_s\) and \(n\) nonzero elements \(z_1,z_2,\cdots,z_n\) of \(GF(q^m)\). Generalized Srivastava codes for \(m=1\) are MDS codes [5; pg. 359].
Glynn code The unique trace-Hermitian self-dual \([10,5,6]_9\) code, constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve. The Glynn code is a rare example of an MDS code that is not related to an RS code.
Grassmannian code Evaluation code of polynomials evaluated on points lying on a Grassmannian \({\mathbb{G}}(\ell,m)\) [15].
Griesmer code A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. Singleton bound implies the Griesmer bound.
Hirschfeld code A projective geometry code that is an example of an MDS code that is not an RS code; see [16; Exam. 7.6] for the description. The Hirschfeld code is a rare example of an MDS code that is not related to an RS code.
Kasami code Member of the family of \([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) cyclic binary linear codes.
MDS array code An \((n,k,m)\) array code whose codewords can be recovered by any \(k\) out of \(n\) nodes, where each node stores a length-\(m\) column of the codeword. MDS array codes are MDS codes when each matrix codeword is treated as a vector by converting each column into a single coordinate via subpacketization. MDS array codes are MDS codes when each matrix codeword is treated as a vector by converting each column into a single coordinate via subpacketization.
Maximum distance separable (MDS) code A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality.
Maximum-rank distance (MRD) 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*{(1)}\end{align} becomes an equality. MRD codes are matrix-code analogues of MDS codes.
Maximum-sum-rank distance (MSRD) code An \([n\times m,k,d]_q\) rank-metric code whose parameters are such that the sum-rank-metric Singleton bound [17; Prop. 34] \begin{align} d_{\text{SR}}(C) \leq n - k + 1 \tag*{(2)}\end{align} becomes an equality, where \(d_{\text{SR}}\) is the sum-rank metric.
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 \(GF(q)\). Extended and doubly extended narrow-sense RS codes are MDS [13; Thms. 5.3.2 and 5.3.4], and there is an equivalence between the two for odd prime \(q\) [14].
Perfect-tensor code Block quantum code encoding one subsystem into an odd number \(n\) subsystems whose encoding isometry is a perfect tensor. This code stems from an AME\((n,q)\) AME state, or equivalently, a \(((n+1,1,\lfloor (n+1)/2 \rfloor + 1))\) code. MDS codes can be used to obtain cluster states that are AME with minimal support [18–23].
Projective RM (PRM) code Reed-Muller code for nonzero points \(\{\alpha_1,\cdots,\alpha_n\}\) with \(n=m+1\) whose leftmost nonzero coordinate is one, corresponding to an evaluation code of polynomials over projective coordinates.
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 [24–27]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([9,3]\) MDS codes have been tabulated [28] in terms of 9-arcs in the projective plane.
Quantum convolutional code One-dimensional translationally invariant qubit stabilizer code whose whose stabilizer group can be partitioned into constant-size subsets of constant support and of constant overlap between neighboring sets. Initially formulated as a quantum analogue of convolutional codes, which were designed to protect a continuous and never-ending stream of information. Precise formulations sometimes begin with a finite-dimensional lattice, with the intent to take the thermodynamic limit; logical dimension can be infinite as well.
Quantum irregular convolutional code (QIRCC) Quantum convolutional code whose stabilizer group consists of different constant-size subsets.
Quantum maximum-distance-separable (MDS) code A type of block quantum code whose parameters satisfy the quantum Singleton bound with equality.
Quantum tensor-product code CSS code constructed from a tensor code. In some cases, only one of the classical codes forming the tensor code needs to be self-orthogonal. MDS codes can be used to construct quantum tensor-product codes [29].
Quantum turbo code A quantum version of the turbo code, obtained from an interleaved serial quantum concatenation [30; Def. 30] of quantum convolutional codes.
Reed-Solomon (RS) code An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [14].
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. Its automorphism group is \(S_n\).
Roth-Lempel code Member of a \(q\)-ary linear code family that includes many examples of MDS codes that are not GRS codes. Roth-Lempel codes are examples of MDS codes that are not GRS codes.
Tetracode The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [8].
\((5,1,2)\)-convolutional code Family of quantum convolutional codes that are 1D lattice generalizations of the five-qubit perfect code, with the former''s lattice-translation symmetry being the extension of the latter''s cyclic permutation symmetry.
\([2^m-1,m,2^{m-1}]\) simplex code A member of the code family that is dual to the \([2^m,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping.
\([6,3,4]_4\) Hexacode The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [8], and conformal field theory [31]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [32]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). The hexacode is an MDS code [13; Exer. 578].
\([7,3,4]\) simplex code Second-smallest 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.
\([7,4,3]\) Hamming code Second-smallest member of the Hamming code family.
\([[5,1,3]]\) Five-qubit perfect code Five-qubit cyclic stabilizer code that is the smallest qubit stabilizer code to correct a single-qubit error.
\([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. Its automorphism group is \(S_n\).
\(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\). The \([4,2,3]_3\) Hamming code is a unique MDS code [33,34].
\(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 simplex code An \([n,m,q^{m-1}]_q\) 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.

References

[1]
M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[2]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[3]
I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[4]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
[7]
S. Kurz, “Divisible Codes”, (2023) arXiv:2112.11763
[8]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[9]
W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[10]
M. Grassl, F. Huber, and A. Winter, “Entropic Proofs of Singleton Bounds for Quantum Error-Correcting Codes”, IEEE Transactions on Information Theory 68, 3942 (2022) arXiv:2010.07902 DOI
[11]
J. Fan, H. Chen, and J. Xu, “Constructions of q-ary entanglement-assisted quantum MDS codes with minimum distance greater than q + 1”, (2016) arXiv:1602.02235
[12]
A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[13]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[14]
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 14, 733 (2012) DOI
[15]
D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI
[16]
S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
[17]
U. Martínez-Peñas, “Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring”, (2018) arXiv:1710.03109
[18]
A. V. Thapliyal, Multipartite maximally entangled states, minimal entanglement generating states and entropic inequalities unpublished presentation (2003).
[19]
W. Helwig and W. Cui, “Absolutely Maximally Entangled States: Existence and Applications”, (2013) arXiv:1306.2536
[20]
W. Helwig, “Absolutely Maximally Entangled Qudit Graph States”, (2013) arXiv:1306.2879
[21]
D. Goyeneche, D. Alsina, J. I. Latorre, A. Riera, and K. Życzkowski, “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
[22]
Z. Raissi, C. Gogolin, A. Riera, and A. Acín, “Optimal quantum error correcting codes from absolutely maximally entangled states”, Journal of Physics A: Mathematical and Theoretical 51, 075301 (2018) arXiv:1701.03359 DOI
[23]
D. Alsina, “PhD thesis: Multipartite entanglement and quantum algorithms”, (2017) arXiv:1706.08318
[24]
R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166.
[25]
S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory 427 DOI
[26]
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
[27]
Beutelspacher, Albrecht, and Ute Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, 1998.
[28]
A. V. Iampolskaia, A. N. Skorobogatov, and E. A. Sorokin, “Formula for the number of [9,3] MDS codes”, IEEE Transactions on Information Theory 41, 1667 (1995) DOI
[29]
J. Fan, Y. Li, M.-H. Hsieh, and H. Chen, “On Quantum Tensor Product Codes”, (2017) arXiv:1605.09598
[30]
D. Poulin, J.-P. Tillich, and H. Ollivier, “Quantum serial turbo-codes”, (2009) arXiv:0712.2888
[31]
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
[32]
G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
[33]
Taussky, Olga, and John Todd. "Covering theorems for groups." Bulletin of the American Mathematical Society. Vol. 54. No. 3. 201 CHARLES ST, PROVIDENCE, RI 02940-2213: AMER MATHEMATICAL SOC, 1948.
[34]
J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI