Maximum distance separable (MDS) code

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 \(q\)-ary codes can also be formulated; see Thm. 1.9.10 in Ref. [2]. 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).

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\).
Universally optimal \(q\)-ary code — MDS codes are LP universally optimal codes [5].

Children

Single parity-check (SPC) code
Hexacode
\(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 [6][7]. The dual of a MDS code is an MDS code, so MDS codes are projective.
Matrix computation code — The first matrix multiplication code encoded each entry of the matrices to be multiplied into an MDS code [8].
Maximum-rank distance (MRD) code — MRD codes are matrix-code analogues of MDS codes.
Algebraic-geometry (AG) code — Near MDS \([n,k,d]_{GF(p^m)}\) AG codes exist when \(n,p,m\) satisfy certain relations according to the Tsfasman-Vladut bound [9][10].
Elliptic code — Elliptic codes can be MDS ([2], Ex. 15.5.3; [9], pg. 310; [11], Sec. 4.4.2).
Extended GRS code — An MDS GRS code can be extended to an MDS code ([12], Thm. 5.3.4). Extended and doubly extended narrow-sense RS codes are MDS ([12], Thms. 5.3.2 and 5.3.4), and there is an equivalence between the two for odd prime \(q\) [13].
Generalized RS (GRS) code — GRS codes have distance \(n-k+1\), saturating the Singleton bound.
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 [13].
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é, 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]: H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[6]: S. M. Dodunekov and I. N. Landgev, “On near-MDS codes”, Proceedings of 1994 IEEE International Symposium on Information Theory DOI
[7]: 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
[8]: K. Lee et al., “Speeding Up Distributed Machine Learning Using Codes”, IEEE Transactions on Information Theory 64, 1514 (2018) arXiv:1512.02673 DOI
[9]: M. A. Tsfasman and S. G. Vlăduţ, Algebraic-Geometric Codes (Springer Netherlands, 1991) DOI
[10]: I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000) DOI
[11]: M. Tsfasman, S. Vlǎduţ, and D. Nogin. Algebraic geometric codes: basic notions. Vol. 139. American Mathematical Society, 2022.
[12]: W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[13]: 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

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

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