Singleton bound

Template:Short description 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 $C$ with block length $n$, size $M$ and minimum distance $d$. It is also known as the Joshibound proved by Template:Harvtxt and even earlier by Komamiya.

Statement of the bound

The minimum distance of a set $C$ of codewords of length $n$ is defined as $$d=\underset{\{x,y\in C:x\ne y\}}{min}d(x,y)$$ where $d(x,y)$ is the Hamming distance between $x$ and $y$. The expression $A_q(n,d)$ represents the maximum number of possible codewords in a $q$-ary block code of length $n$ and minimum distance $d$.

Then the Singleton bound states that $$A_q(n,d)\le q^{n-d+1}.$$

Proof

First observe that the number of $q$-ary words of length $n$ is $q^n$, since each letter in such a word may take one of $q$ different values, independently of the remaining letters.

Now let $C$ be an arbitrary $q$-ary block code of minimum distance $d$. Clearly, all codewords $c\in C$ are distinct. If we puncture the code by deleting the first $d-1$ letters of each codeword, then all resulting codewords must still be pairwise different, since all of the original codewords in $C$ have Hamming distance at least $d$ from each other. Thus the size of the altered code is the same as the original code.

The newly obtained codewords each have length $$n-(d-1)=n-d+1,$$ and thus, there can be at most $q^{n-d+1}$ of them. Since $C$ was arbitrary, this bound must hold for the largest possible code with these parameters, thus: $$|C|\le A_q(n,d)\le q^{n-d+1}.$$

Linear codes

If $C$ is a linear code with block length $n$, dimension $k$ and minimum distance $d$ over the finite field with $q$ elements, then the maximum number of codewords is $q^k$ and the Singleton bound implies: $$q^k\le q^{n-d+1},$$ so that $$k\le n-d+1,$$ which is usually written as $$d\le n-k+1.$$

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 $n-k$. Another simple proof follows from observing that the rows of any generator matrix in standard form have weight at most $n-k+1$.

History

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

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 $q$ codewords (the all-$x$ word for $x\in {𝔽}_q$, having thus minimum distance $n$), codes that use the whole of $({𝔽}_q{)}^n$ (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 $n$ and $k$, 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. Let $PG(N,q)$ be the finite projective space of (geometric) dimension $N$ over the finite field ${𝔽}_q$. Let $K=\{P_1,P_2,\dots ,P_m\}$ be a set of points in this projective space represented with homogeneous coordinates. Form the $(N+1)\times m$ matrix $G$ whose columns are the homogeneous coordinates of these points. Then,

See also

• Gilbert–Varshamov bound
• Griesmer bound
• Hamming bound
• Johnson bound
• Plotkin bound

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

Further reading

• Template:Cite book
• Template:Cite book