In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary
block code
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
with block length
, size
and minimum distance
. It is also known as the Joshibound. proved by and even earlier by .
Statement of the bound
The minimum distance of a set
of codewords of length
is defined as
where
is the
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
between
and
. The expression
represents the maximum number of possible codewords in a
-ary block code of length
and minimum distance
.
Then the Singleton bound states that
Proof
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
Puncture, punctured or puncturing may refer to:
* a flat tyre in British English (US English "flat tire" or just "flat")
* a penetrating wound caused by pointy objects as nails or needles
* Lumbar puncture, also known as a spinal tap
* 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
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
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
and thus, there can be at most
of them. Since
was arbitrary, this bound must hold for the largest possible code with these parameters, thus:
Linear codes
If
is a
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
with block length
, dimension
and minimum distance
over the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
with
elements, then the maximum number of codewords is
and the Singleton bound implies:
so that
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 In coding theory, a parity-check matrix of a linear block code ''C'' is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide whether a particular vector is a codeword and is also used ...
is
. Another simple proof follows from observing that the rows of any generator matrix in standard form have weight at most
.
History
The usual citation given for this result is , but was proven earlier by . According to the result can be found in a 1953 paper of
MDS codes
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 code
In coding theory, the dual code of a linear code
:C\subset\mathbb_q^n
is the linear code defined by
:C^\perp = \
where
:\langle x, c \rangle = \sum_^n x_i c_i
is a scalar product. In linear algebra terms, the dual code is the annihilator ...
s. 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.
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
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant with respect to projective transformations. This means that, compared to elementary Euclidean geometry, projective geometry has a different setting, pro ...
. Let
be the finite
projective space
In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet ''at infinity''. A projective space may thus be viewed as the extension of a Euclidean space, or, more generally ...
of (geometric) dimension
over the finite field
. Let
be a set of points in this projective space represented with
homogeneous coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry. T ...
. Form the
matrix
whose columns are the homogeneous coordinates of these points. Then,
See also
*
Gilbert–Varshamov bound In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert and independently Rom Varshamov.) is a limit on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert– Shannon–Varshamov bound (or the GS ...
*
Plotkin bound
In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length ''n'' and given minimum distance ''d''.
Statement of the bound ...
*
Hamming bound
In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of pack ...
*
Johnson bound In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.
Definition
Let C be a ''q''-ary code of length n, i ...
*
Griesmer bound In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension ''k'' and minimum distance ''d''.
There is also a very similar version for non-binary codes.
St ...
Notes
References
*
*
*
*
*
*
*
*
*
Further reading
*
*
{{DEFAULTSORT:Singleton Bound
Coding theory
Inequalities
Articles containing proofs