Кодтанудағы жоғарғы шекаралар: Синглтон шекарасы және MDS кодтары

Upper bound in coding theory
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 and even earlier by .

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

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 codewords (the all word for , 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. 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. 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:

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

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,