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

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

Zoo code information

Internal code ID: mds

Your contribution is welcome!

on github.com (edit & pull request)

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.), 2022. https://errorcorrectionzoo.org/c/mds
BibTeX:
@incollection{eczoo_mds, title={Maximum distance separable (MDS) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/mds} }
Permanent link:
https://errorcorrectionzoo.org/c/mds

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.