Here is a list of classical 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 Linear binary 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.
B-code The first array code, constructed over \(\mathbb{F}_q\). See [6] 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]_{2^a}\) codes for \(i < a\) constructed using Denniston arcs.
Diagonal code Member of an explicit family of high-rate \([n,k,d,\alpha, \beta = \frac{\alpha}{d-k+1}, M=k\alpha]\) MSR codes for any \(r\) and \(n\). Such codes can optimally repair any \(f\) failed nodes from any \(d\) helper nodes for all \(d\), \(1 \le f \le r\) and \(k \le d \le n-f\) simultaneously. These codes can be constructed over any base field \(\mathbb{F}_q\) as long as \(|\mathbb{F}_q| \ge sn\), where \(s = \text{lcm}(1,2,\cdots,r)\).
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 [7].
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) [8,9]. 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 [10; 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) [11; Thm. 6] become an equality. MDS codes give rise to families of EA Galois-qudit codes that saturate the original (erroneous) EAQECC Singleton bound [12].
EVENODD code A binary array code that can correct any two disk failures (i.e., two erasures). See [6] for more details.
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 [13; 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 ([14], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([14], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [15].
Gabidulin code A linear code over \(\mathbb{F}_{q^N}\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(\mathbb{F}_{q^N}\) can be written as an \(N\)-dimensional vector with coefficients in \(\mathbb{F}_q\), and the rank of a set of elements is rank of the matrix formed by their coefficients.
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 \(\mathbb{F}_q\) via an extension of qubit CSS-to-homology correspondence to Galois qudits.
Generalized EVENODD code A generalization of the EVENODD code defined for parameters \(m\) and \(r\); see [6].
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 \(\mathbb{F}_{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 evaluation code Evaluation code of polynomials evaluated on points lying on a finite-field Grassmannian embedded into projective space using the Plucker embedding [16,17].
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 [18; 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.
Linearized RS code A linearized version of a skew RS code, i.e., an RS code constructed by evaluating skew polynomials [19,20].
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 \(q\)-ary linear 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 [21; 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.
Minimum-storage regenerating (MSR) code An RGC that corresponds to an extreme point in the storage-bandwidth trade-off curve that is characterised by \(\alpha = (d-k+1)\beta\).
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 \(\mathbb{F}_q\). Extended and doubly extended narrow-sense RS codes are MDS [14; Thms. 5.3.2 and 5.3.4], and there is an equivalence between the two for odd prime \(q\) [15].
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 [22–27].
Projective RM (PRM) code GRM 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 \(\mathbb{F}_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 [28–31]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([9,3]\) MDS codes have been tabulated [32] in terms of 9-arcs in the projective plane.
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 [33].
Reed-Solomon (RS) code An \([n,k,n-k+1]_q\) linear code based on polynomials over \(\mathbb{F}_q\). If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [15].
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.
Row-Diagonal Parity (RDP) code An MDS array code protecting against double erasures.
Star code An MDS array code protecting against triple erasures.
X-code An MDS array code with a simple geometrical construction that achieves optimal encoding and update complexity.
Ye-Barg code An MDS array code with the optimal access property; see Ref. [34] for definitions.
Zigzag code An MDS array code correcting against two erasures with optimal rebuilding ratio; see Ref. [35] for definitions.
\([2^m-1,m,2^{m-1}]\) simplex code A member of the equidistant 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. Simplex codes saturate the Plotkin bound and hence have nonzero codewords all of the same weight, \(2^{m-1}\) [5; Th. 11(a)]. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping.
\([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) Kasami code Member of the family of \([2^{2r}-1, 3r, 2^{2r-1} - 2^{r-1} ]\) cyclic binary linear codes. Gold and Kasami codes are both constructed by picking a set of cyclically unrelated sequences of binary linear codes with low cross-correlation [36,37].
\([4,2,3]_3\) Tetracode The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [9].
\([6,3,4]_4\) Hexacode The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [9], and conformal field theory [38]. The hexacode is an MDS code [14; 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.
\([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\).
\([n,n-1,2]_q\) \(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 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 [39,40].
\(q\)-ary repetition code An \([n,1,n]_q\) code encoding consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\).
\(q\)-ary simplex code An \([n,m,q^{m-1}]_q\) equidistant 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. All nonzero simplex codewords have a constant weight of \(q^{m-1}\) [41,42].

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]
M. Blaum, P. G. Farrell, H. C. A. van Tilborg, 1998. Array codes. Handbook of coding theory, 2 (Part 2), pp. 1855-1909.
[7]
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
[8]
S. Kurz, “Divisible Codes”, (2023) arXiv:2112.11763
[9]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[10]
W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[11]
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
[12]
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
[13]
A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[14]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[15]
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
[16]
D. Yu. Nogin, “Codes associated to Grassmannians”, Arithmetic, Geometry, and Coding Theory DOI
[17]
V. Lakshmibai and J. Brown, The Grassmannian Variety (Springer New York, 2015) DOI
[18]
S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
[19]
D. Boucher and F. Ulmer, “Linear codes using skew polynomials with automorphisms and derivations”, Designs, Codes and Cryptography 70, 405 (2012) DOI
[20]
S. Liu, F. Manganiello, and F. R. Kschischang, “Construction and decoding of generalized skew-evaluation codes”, 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT) 9 (2015) DOI
[21]
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
[22]
A. V. Thapliyal, Multipartite maximally entangled states, minimal entanglement generating states and entropic inequalities unpublished presentation (2003).
[23]
W. Helwig and W. Cui, “Absolutely Maximally Entangled States: Existence and Applications”, (2013) arXiv:1306.2536
[24]
W. Helwig, “Absolutely Maximally Entangled Qudit Graph States”, (2013) arXiv:1306.2879
[25]
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
[26]
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
[27]
D. Alsina, “PhD thesis: Multipartite entanglement and quantum algorithms”, (2017) arXiv:1706.08318
[28]
R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166.
[29]
S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory 427 DOI
[30]
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
[31]
Beutelspacher, Albrecht, and Ute Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, 1998.
[32]
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
[33]
J. Fan, Y. Li, M.-H. Hsieh, and H. Chen, “On Quantum Tensor Product Codes”, (2017) arXiv:1605.09598
[34]
M. Ye and A. Barg, “Explicit constructions of high-rate MDS array codes with optimal repair bandwidth”, (2016) arXiv:1604.00454
[35]
I. Tamo, Z. Wang, and J. Bruck, “Zigzag Codes: MDS Array Codes With Optimal Rebuilding”, IEEE Transactions on Information Theory 59, 1597 (2013) arXiv:1112.0371 DOI
[36]
D. V. Sarwate and M. B. Pursley, “Crosscorrelation properties of pseudorandom and related sequences”, Proceedings of the IEEE 68, 593 (1980) DOI
[37]
T. Helleseth, C. Li, “Pseudo-Noise Sequences.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[38]
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
[39]
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.
[40]
J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI
[41]
A. E.F. Jr. and H. F. Mattson, “Error-correcting codes: An axiomatic approach”, Information and Control 6, 315 (1963) DOI
[42]
E. Weiss, “Linear Codes of Constant Weight”, SIAM Journal on Applied Mathematics 14, 106 (1966) DOI