Maximum distance separable (MDS) code[1]
Description
A \(q\)-ary linear code whose parameters satisfy the Singleton bound with equality.
An \([n,k,d]_q\) code is MDS 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. Equivalently, a code with minimum distance \(d\) and dual distance \(d'\) is MDS precisely when \(d+d'=n+2\) and all distances occur [2; Thm. 12.3.1]. 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 [3; Thm. 1.9.10]. A code is near MDS (NMDS) if both the code and its dual are 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 [4; Sec. 3.3.2]. 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., [5; 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 [6; Ch. 7].Notes
See Refs. [7][5; Sec. 11.4 notes][8; Ch. 11 notes] for more on MDS codes and the MDS conjecture.An MDS code with \(k=2\) is equivalent to a set of \(n-k\) mutually orthogonal Latin squares of order \(q\) [8; Ch. 11 notes].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 [3; 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 [9–12]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([9,3]\) MDS codes have been tabulated [13] in terms of 9-arcs in the projective plane.
- MDS array code— 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.
- Distributed computation code— The first matrix multiplication code encoded each entry of the matrices to be multiplied into an MDS code [14].
- Maximum-sum-rank distance (MSRD) code— MSRD codes generalize MDS codes from the Hamming metric to the sum-rank metric.
- 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 [15–17].
- Elliptic code— Elliptic codes can be MDS [18; Exam. 15.5.3][16; pg. 310][15; Sec. 4.4.2].
- Extended GRS code— A GRS code can be extended to an MDS code [19; Thm. 5.3.4]. Extended and doubly extended narrow-sense RS codes are MDS [19; Thms. 5.3.2 and 5.3.4], and there is an equivalence between the two for odd prime \(q\) [20].
- Narrow-sense RS code— Extended and doubly extended narrow-sense RS codes are MDS [19; Thms. 5.3.2 and 5.3.4][5; Ch. 11], and there is an equivalence between the two for odd prime \(q\) [20].
- Reed-Solomon (RS) code— Reed-Solomon codes are important examples of MDS codes, and for prime \(q\), every \([q+1,k,q-k+2]_q\) MDS code is Reed-Solomon; for non-prime \(q\), non-equivalent maximal-length MDS codes also exist [20][4; Sec. 3.3.2][5; Ch. 11].
- Generalized Srivastava code— Generalized Srivastava codes for \(m=1\) are MDS codes [8; pg. 359].
- Quantum maximum-distance-separable (MDS) code— Quantum MDS codes are quantum analogues of MDS codes.
- Perfect-tensor code— MDS codes can be used to obtain cluster states that are AME with minimal support [21–26].
- Quantum tensor-product code— MDS codes can be used to construct quantum tensor-product codes [27].
- EA MDS code— MDS codes give rise to families of EA Galois-qudit codes that saturate the original (erroneous) EAQECC Singleton bound [28].
Primary Hierarchy
Parents
The generalized Singleton bound becomes the Singleton bound for \(k=r\), so optimal LRCs with that constraint are MDS.
MDS codes are LP universally optimal codes [29].
An MDS code is an OA\(_{1}(k,n,q)\) [4; Thm. 3.3.19].
Maximum distance separable (MDS) code
Children
Binary repetition codes are trivial MDS codes [2; Thm. 12.3.1][4; Sec. 3.3.2].
GRS codes have distance \(n-k+1\), saturating the Singleton bound.
Roth-Lempel codes are examples of MDS codes that are not GRS codes.
The Glynn code is a rare example of an MDS code that is not related to an RS code.
The hexacode is an MDS code [19; Exer. 578].
The Hirschfeld code is a rare example of an MDS code that is not related to an RS code.
Singleton bound implies the Griesmer bound.
References
- [1]
- R. Singleton, “Maximum distanceq-nary codes”, IEEE Transactions on Information Theory 10, 116 (1964) DOI
- [2]
- P. Boyvalenkov, D. Danev, “Linear programming bounds.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- W. C. Huffman, J.-L. Kim, and P. Solé, “Basics of coding theory.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [4]
- P. R. J. Östergård, “Construction and Classification of Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- R. Roth, Introduction to Coding Theory (Cambridge University Press, 2006) DOI
- [6]
- S. B. Wicker and V. K. Bhargava, “Reed-Solomon Codes and Their Applications”, (1999) DOI
- [7]
- J. W. P. Hirschfeld and J. A. Thas, “Open problems in finite projective spaces”, Finite Fields and Their Applications 32, 44 (2015) DOI
- [8]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [9]
- R. C. Bose (1947). Mathematical theory of the symmetrical factorial design. Sankhyā: The Indian Journal of Statistics, 107-166
- [10]
- S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory 427 DOI
- [11]
- 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
- [12]
- A. Beutelspacher and U. Rosenbaum. Projective geometry: from foundations to applications. Cambridge University Press, 1998
- [13]
- 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
- [14]
- 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
- [15]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin, Algebraic Geometric Codes: Basic Notions, vol. 139 (American Mathematical Society, 2022)
- [16]
- M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
- [17]
- I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
- [18]
- A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [19]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) 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]
- A. V. Thapliyal, Multipartite maximally entangled states, minimal entanglement generating states and entropic inequalities unpublished presentation (2003)
- [22]
- W. Helwig and W. Cui, “Absolutely Maximally Entangled States: Existence and Applications”, (2013) arXiv:1306.2536
- [23]
- W. Helwig, “Absolutely Maximally Entangled Qudit Graph States”, (2013) arXiv:1306.2879
- [24]
- 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
- [25]
- 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
- [26]
- D. Alsina, “PhD thesis: Multipartite entanglement and quantum algorithms”, (2017) arXiv:1706.08318
- [27]
- J. Fan, Y. Li, M.-H. Hsieh, and H. Chen, “On Quantum Tensor Product Codes”, (2017) arXiv:1605.09598
- [28]
- 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
- [29]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [30]
- O. Taussky and J. 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
- [31]
- J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI
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