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

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.Automatic repeat request (ARQ) data transmission protocols ([4], Ch. 7).

Notes

See Ref. [5] for a review of 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]
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

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.), 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} }
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.), 2022. https://errorcorrectionzoo.org/c/mds

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