In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary block code with block length , size and minimum distance . It is also known as the Joshibound. proved by Joshi (1958) and even earlier by Komamiya (1953).
Statement of the bound
The minimum distance of a set of codewords of length is defined as
Then the Singleton bound states that
First observe that the number of -ary words of length is , since each letter in such a word may take one of different values, independently of the remaining letters.
Now let be an arbitrary -ary block code of minimum distance . Clearly, all codewords are distinct. If we puncture the code by deleting the first letters of each codeword, then all resulting codewords must still be pairwise different, since all of the original codewords in have Hamming distance at least from each other. Thus the size of the altered code is the same as the original code.
The newly obtained codewords each have length
In the linear code case a different proof of the Singleton bound can be obtained by observing that rank of the parity check matrix is . Another simple proof follows from observing that the rows of any generator matrix in standard form have weight at most .
Linear block codes that achieve equality in the Singleton bound are called MDS (maximum distance separable) codes. Examples of such codes include codes that have only two codewords (the all-zero word and the all-one word, having thus minimum distance ), codes that use the whole of (minimum distance 1), codes with a single parity symbol (minimum distance 2) and their dual codes. These are often called trivial MDS codes.
MDS codes are an important class of block codes since, for a fixed and , they have the greatest error correcting and detecting capabilities. There are several ways to characterize MDS codes:
Theorem — Let be a linear  code over . The following are equivalent:
- is an MDS code.
- Any columns of a generator matrix for are linearly independent.
- Any columns of a parity check matrix for are linearly independent.
- is an MDS code.
- If is a generator matrix for in standard form, then every square submatrix of is nonsingular.
- Given any coordinate positions, there is a (minimum weight) codeword whose support is precisely these positions.
Theorem — Let be a linear  MDS code over . If denotes the number of codewords in of weight , then
Arcs in projective geometry
The linear independence of the columns of a generator matrix of an MDS code permits a construction of MDS codes from objects in finite projective geometry. Let be the finite projective space of (geometric) dimension over the finite field . Let be a set of points in this projective space represented with homogeneous coordinates. Form the matrix whose columns are the homogeneous coordinates of these points. Then,
Theorem — is a (spatial) -arc if and only if is the generator matrix of an MDS code over .
- Keedwell, A. Donald; Dénes, József (24 January 1991). Latin Squares: New Developments in the Theory and Applications. Amsterdam: Elsevier. p. 270. ISBN 0-444-88899-3.
- Ling & Xing 2004, p. 93
- Roman 1992, p. 175
- Pless 1998, p. 26
- Vermani 1996, Proposition 9.2
- Ling & Xing 2004, p. 94 Remark 5.4.7
- MacWilliams & Sloane 1977, Ch. 11
- Ling & Xing 2004, p. 94
- Roman 1992, p. 237, Theorem 5.3.7
- Roman 1992, p. 240
- Bruen, A.A.; Thas, J.A.; Blokhuis, A. (1988), "On M.D.S. codes, arcs in PG(n,q), with q even, and a solution of three fundamental problems of B. Segre", Invent. Math., 92 (3): 441–459, Bibcode:1988InMat..92..441B, doi:10.1007/bf01393742, S2CID 120077696
- Joshi, D.D (1958), "A Note on Upper Bounds for Minimum Distance Codes", Information and Control, 1 (3): 289–295, doi:10.1016/S0019-9958(58)80006-6
- Komamiya, Y. (1953), "Application of logical mathematics to information theory", Proc. 3rd Japan. Nat. Cong. Appl. Math.: 437
- Ling, San; Xing, Chaoping (2004), Coding Theory / A First Course, Cambridge University Press, ISBN 0-521-52923-9
- MacWilliams, F.J.; Sloane, N.J.A. (1977), The Theory of Error-Correcting Codes, North-Holland, pp. 33, 37, ISBN 0-444-85193-3
- Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
- Roman, Steven (1992), Coding and Information Theory, GTM, vol. 134, Springer-Verlag, ISBN 0-387-97812-7
- Singleton, R.C. (1964), "Maximum distance q-nary codes", IEEE Trans. Inf. Theory, 10 (2): 116–118, doi:10.1109/TIT.1964.1053661
- Vermani, L. R. (1996), Elements of algebraic coding theory, Chapman & Hall
- Welsh, Dominic (1988), Codes and Cryptography, Oxford University Press, ISBN 0-19-853287-3
- J.H. van Lint (1992). Introduction to Coding Theory. GTM. Vol. 86 (2nd ed.). Springer-Verlag. p. 61. ISBN 3-540-54894-7.
- Niederreiter, Harald; Xing, Chaoping (2001). "6. Applications to algebraic coding theory". Rational points on curves over finite fields. Theory and Applications. London Mathematical Society Lecture Note Series. Vol. 285. Cambridge: Cambridge University Press. ISBN 0-521-66543-4. Zbl 0971.11033.