# Maximum distance separable (MDS) code[1]

## Description

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
\end{align}
becomes an equality. A code is called almost MDS (AMDS) when \(d=n-k\). A bound for general \(q\)-ary codes can also be formulated; see Thm. 1.9.10 in Ref. [2].

## 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

The McEliece Public Key Cryptosystem [3] uses algebraic coding theory to secure communications against eavesdropping attack, in which private keys are generator matrices of linear codes, i.e., \(G\). Public Keys shared to outside world are scrambled and permutated versions of \(G\), i.e., \(G^\prime=SGP\). Data to be encrypted, \(u\), is multiplied by public key and added intentional errors \(e\), i.e., \(x=uG^\prime+e\). Upon receiving encrypted data, private key owner can apply inverse permutation \(P^{-1}\) to \(x\), decode the scrambled message given the presence of \(e\) errors, and finally unscramble to obtain \(u\). Security parameters of the system are \(n\) and \(e\), hence MDS codes, such as GRS codes may provide the same security level for shorter key sizes, and the private key owner can decode arguably fast enough using known decoding algorithms.

## Notes

The dual of an MDS codes is always MDS.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.

## Parents

- Linear \(q\)-ary code
- Locally recoverable code (LRC) — MDS codes are most efficient in terms of minimizing storage overhead for handling erasures. They are locally recoverable with locality \(k\).

## Child

- Reed-Solomon (RS) code — Every RS code is MDS. If \(k \leq p\), then all linear MDS codes \( [n,k,n-k+1]_{p^m} \) are RS codes [4].

## Cousins

- Maximum-rank distance (MRD) code — MRD codes are matrix-code analogues of MDS codes.
- Quantum maximum-distance-separable (MDS) code

## Zoo code information

## 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é, 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. 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

## Cite as:

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

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