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
It is also known as the Joshibound[1] proved by Joshi (1958) and even earlier by Komamiya (1953).
The minimum distance of a set
represents the maximum number of possible codewords in a
-ary block code of length
Then the Singleton bound states that
different values, independently of the remaining letters.
-ary block code of minimum distance
The newly obtained codewords each have length
was arbitrary, this bound must hold for the largest possible code with these parameters, thus:[2]
is a linear code with block length
elements, then the maximum number of codewords is
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
[4] Another simple proof follows from observing that the rows of any generator matrix in standard form have weight at most
The usual citation given for this result is Singleton (1964), but it was proven earlier by Joshi (1958).
Joshi notes that the result was obtained earlier by Komamiya (1953) using a more complex proof.
Welsh (1988, p. 72) also notes the same regarding Komamiya (1953).
Linear block codes that achieve equality in the Singleton bound are called MDS (maximum distance separable) codes.
(minimum distance 1), codes with a single parity symbol (minimum distance 2) and their dual codes.
These are often called trivial MDS codes.
In the case of binary alphabets, only trivial MDS codes exist.
[5][6] Examples of non-trivial MDS codes include Reed-Solomon codes and their extended versions.
, they have the greatest error correcting and detecting capabilities.
There are several ways to characterize MDS codes:[9] Theorem — Let
The following are equivalent: The last of these characterizations permits, by using the MacWilliams identities, an explicit formula for the complete weight distribution of an MDS code.
denotes the number of codewords in
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.
be the finite projective space of (geometric) dimension
be a set of points in this projective space represented with homogeneous coordinates.
whose columns are the homogeneous coordinates of these points.