# Maximum distance separable (MDS) code[1]

## Description

A \([n,k,d]_q\) binary or \(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

## Realizations

## Notes

## 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 [6].
- Orthogonal array (OA) — An MDS code is an OA\(_{1}(k,n,q)\) [7; 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 [8; 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 [9–11]. The dual of a MDS code is an MDS code, so MDS codes are projective. All \([[9,3]]\) MDS codes have been tabulated [12] 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 [13].
- 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 [14,15].
- Elliptic code — Elliptic codes can be MDS [16; Ex. 15.5.3][14; pg. 310][17; Sec. 4.4.2].
- Extended GRS code — A GRS code can be extended to an MDS code ([8], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([8], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [18].
- 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 [18].
- \(q\)-ary Hamming code — The \((4,9,3)_3\) Hamming code is a unique MDS code [19,20].
- Quantum maximum-distance-separable (MDS) code

## 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]
- McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN Progress Report pp. 114–116 (1978).
- [4]
- S. B. Wicker and V. K. Bhargava, Reed-Solomon Codes and Their Applications (IEEE, 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]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [7]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [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 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. 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
- [13]
- K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
- [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]
- M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
- [18]
- 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
- [19]
- 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.
- [20]
- 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

- Victor V. Albert (2022-08-09) — most recent
- 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.), 2022. https://errorcorrectionzoo.org/c/mds