Maximum distance separable (MDS) code

Maximum distance separable (MDS) code[1]

Description

A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality.

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 \tag*{(1)}\end{align} becomes an equality. A code is called almost MDS (AMDS) when \(d=n-k\). A bound for general (i.e., nonlinear or unrestricted) \(q\)-ary codes can also be formulated; see [2; Thm. 1.9.10]. A code is near MDS (NMDS) if the code and its dual are mode AMDS.

The codes \( [n,1,n]_q, [n,n-1,2]_q, [n,n,1]_q \) for any \(q\) are MDS codes. These are called the trivial MDS codes. The only binary MDS codes are the trivial ones.

Protection

Given \(n\) and \(k\), MDS codes have the highest distance possible of all codes and so have the best possible error-correction properties.

Realizations

Automatic repeat request (ARQ) data transmission protocols ([3], Ch. 7).

Notes

See Ref. [4] for a review of MDS codes and the MDS conjecture.

Parents

Linear \(q\)-ary code
Optimal LRC — The generalized Singleton bound becomes the Singleton bound for \(k=r\), so optimal LRCs with that constraint are MDS.
Universally optimal \(q\)-ary code — MDS codes are LP universally optimal codes [5].
Orthogonal array (OA) — An MDS code is an OA\(_{1}(k,n,q)\) [6; Thm. 3.3.19].

Children

Single parity-check (SPC) code
Generalized RS (GRS) code — GRS codes have distance \(n-k+1\), saturating the Singleton bound.
Roth-Lempel code — Roth-Lempel codes are examples of MDS codes that are not GRS codes.
Glynn code
Hexacode — The hexacode is an MDS code [7; Exer. 578].
\(q\)-ary parity-check code
Tetracode
Griesmer code — Singleton bound implies the Griesmer bound.

Cousins

Dual linear code — 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 [2; Thm. 1.9.13].
Projective geometry code — 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 [8–10]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([[9,3]]\) MDS codes have been tabulated [11] in terms of 9-arcs in the projective plane.
Matrix computation code — The first matrix multiplication code encoded each entry of the matrices to be multiplied into an MDS code [12].
Maximum-rank distance (MRD) code — MRD codes are matrix-code analogues of MDS codes.
Algebraic-geometry (AG) code — Near MDS \([n,k,d]_{p^m}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [13–15].
Elliptic code — Elliptic codes can be MDS [16; Ex. 15.5.3][14; pg. 310][13; Sec. 4.4.2].
Extended GRS code — A GRS code can be extended to an MDS code ([7], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([7], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [17].
Reed-Solomon (RS) code — 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 [17].
\(q\)-ary Hamming code — The \((4,9,3)_3\) Hamming code is a unique MDS code [18,19].
Quantum maximum-distance-separable (MDS) code
Perfect-tensor code — MDS codes can be used to obtain perfect-tensor codes with minimal support [20–22].
Quantum tensor-product code — MDS codes can be used to construct quantum tensor-product codes [23].
EA MDS code — MDS codes give rise to families of EA Galois-qudit codes that saturate the original (erroneous) EAQECC Singleton bound [24].

References

[1]: R. Singleton, “Maximum distance&lt;tex&gt;q&lt;/tex&gt;-nary codes”, IEEE Transactions on Information Theory 10, 116 (1964) DOI
[2]: W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[3]: S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE, 1999) DOI
[4]: J. W. P. Hirschfeld and J. A. Thas, “Open problems in finite projective spaces”, Finite Fields and Their Applications 32, 44 (2015) DOI
[5]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[6]: P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[7]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[8]: R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166.
[9]: S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory DOI
[10]: 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
[11]: 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
[12]: K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
[13]: M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[14]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[15]: I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[16]: A. Couvreur, H. Randriambololona, "Algebraic Geometry Codes and Some Applications." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[17]: 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
[18]: 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.
[19]: J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI
[20]: W. Helwig and W. Cui, “Absolutely Maximally Entangled States: Existence and Applications”, (2013) arXiv:1306.2536
[21]: D. Goyeneche et al., “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
[22]: Z. Raissi et al., “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]: J. Fan et al., “On Quantum Tensor Product Codes”, (2017) arXiv:1605.09598
[24]: 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

Page edit log

Markus Grassl (2024-07-11) — most recent
Victor V. Albert (2024-07-11)
Victor V. Albert (2022-08-09)
Victor V. Albert (2022-04-28)
Victor V. Albert (2021-12-16)
Eric Kubischta (2021-12-15)

Cite as:

“Maximum distance separable (MDS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/mds

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/distributed_storage/mds.yml.