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. Many, but not all, \(q\)-ary MDS codes are related to RS codes and their extensions; see, e.g., [3; Prob. 11.11].

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 ([4], Ch. 7).

Notes

See Refs. [5][3; Sec. 11.4 notes][6; Ch. 11 notes] for more on MDS codes and the MDS conjecture.

Parents

Children

Cousins

References

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: mds

Cite as:
“Maximum distance separable (MDS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/mds
BibTeX:
@incollection{eczoo_mds, title={Maximum distance separable (MDS) code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/mds} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/mds

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.