In coding theory, the Singleton bound, named after the American mathematician Richard Collom Singleton (1928–2007), is a relatively crude upper bound on the size of an arbitrary block code. It is also known as the Joshibound proved by and even earlier by Komamiya.

Statement of the bound

is the Hamming distance and minimum distance.

Proof

different values, independently of the remaining letters.

are distinct. If we puncture have Hamming distance from each other. Thus the size of the altered code is the same as the original code.

was arbitrary, this bound must hold for the largest possible code with these parameters, thus:

Linear codes

is a linear code over the finite field which is usually written as

In the linear code case a different proof of the Singleton bound can be obtained by observing that rank of the parity check matrix..

History

The usual citation given for this result is , but it was proven earlier by . Joshi notes that the result had been obtained earlier by using a more complex proof. also notes the same regarding .

MDS codes

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.

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:

The last of these characterizations permits, by using the MacWilliams identities, an explicit formula for the complete weight distribution of an MDS code.

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 be the finite projective space be a set of points in this projective space represented with homogeneous coordinates whose columns are the homogeneous coordinates of these points. Then,

See also

• Gilbert–Varshamov bound

• Griesmer bound

• Hamming bound

• Johnson bound

• Plotkin bound

Notes

References

Further reading