Singleton bound#MDS codes

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{{cite book |last1=Keedwell |first1=A. Donald |last2=Dénes |first2=József |title=Latin Squares: New Developments in the Theory and Applications |date=24 January 1991 |publisher=Elsevier |publication-place=Amsterdam |isbn=0-444-88899-3 |page=270 |url=https://books.google.com/books?id=Ey8iXKkQpDkC&pg=PA270}} proved by {{harvtxt|Joshi|1958}} and even earlier by {{harvtxt|Komamiya|1953}}.

Statement of the bound

The minimum distance of a set $C$ of codewords of length $n$ is defined as

$d = \min_{\{x,y \in C : x \neq y\}} 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) \leq 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:{{harvnb|Ling|Xing|2004|loc=p. 93}}

$|C| \le A_q(n,d) \leq 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 \leq q^{n-d+1},$

so that

$k \leq n - d + 1,$

which is usually written as{{harvnb|Roman|1992|loc=p. 175}}

$d \leq 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$ .{{harvnb|Pless|1998|loc=p. 26}} 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 {{harvtxt|Singleton|1964}}, but it was proven earlier by {{harvtxt|Joshi|1958}}. Joshi notes that the result had been obtained earlier by {{harvtxt|Komamiya|1953}} using a more complex proof. {{harvtxt|Welsh|1988|loc=p. 72}} also notes the same regarding {{harvtxt|Komamiya|1953}}.

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\mathbb{F}_q$ , having thus minimum distance $n$ ), codes that use the whole of $(\mathbb{F}_{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.{{harvnb|Vermani|1996|loc= Proposition 9.2}}{{harvnb|Ling|Xing|2004|loc=p. 94 Remark 5.4.7}}

Examples of non-trivial MDS codes include Reed-Solomon codes and their extended versions.{{harvnb|MacWilliams|Sloane|1977|loc= Ch. 11}}{{harvnb|Ling|Xing|2004|loc=p. 94}}

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:{{harvnb|Roman|1992|loc=p. 237, Theorem 5.3.7}}

{{math theorem | math_statement = Let $C$ be a linear [ $n,k,d$ ] code over $\mathbb{F}_q$ . The following are equivalent:

$C$ is an MDS code.
Any $k$ columns of a generator matrix for $C$ are linearly independent.
Any $n-k$ columns of a parity check matrix for $C$ are linearly independent.
$C^{\perp}$ is an MDS code.
If $G = (I|A)$ is a generator matrix for $C$ in standard form, then every square submatrix of $A$ is nonsingular.
Given any $d$ coordinate positions, there is a (minimum weight) codeword whose support is precisely these positions.}}

The last of these characterizations permits, by using the MacWilliams identities, an explicit formula for the complete weight distribution of an MDS code.{{harvnb|Roman|1992|loc=p. 240}}

{{math theorem | math_statement = Let $C$ be a linear [ $n,k,d$ ] MDS code over $\mathbb{F}_q$ . If $A_w$ denotes the number of codewords in $C$ of weight $w$ , then

$A_w = \binom{n}{w} \sum_{j=0}^{w-d} (-1)^j \binom{w}{j} (q^{w-d+1-j} -1) = \binom{n}{w}(q-1)\sum_{j=0}^{w-d} (-1)^j \binom{w-1}{j}q^{w-d-j}.$ }}

=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 $\mathbb{F}_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,{{citation|first1=A.A.|last1=Bruen| first2=J.A.|last2=Thas|first3=A.|last3=Blokhuis|title=On M.D.S. codes, arcs in PG(n,q), with q even, and a solution of three fundamental problems of B. Segre|journal=Invent. Math.|volume=92|year=1988|issue=3|pages=441–459|doi=10.1007/bf01393742| bibcode=1988InMat..92..441B|s2cid=120077696}}

{{math theorem | math_statement = $K$ is a (spatial) $m$ -arc if and only if $G$ is the generator matrix of an $[m,N+1,m-N]$ MDS code over $\mathbb{F}_q$ .}}

Notes

References

{{citation|first= D.D|last=Joshi|title=A Note on Upper Bounds for Minimum Distance Codes |journal=Information and Control | volume=1| pages=289–295 | year=1958 | doi=10.1016/S0019-9958(58)80006-6 | issue=3 | doi-access=free }}
{{citation|first=Y.|last=Komamiya|year=1953|title=Application of logical mathematics to information theory|journal=Proc. 3rd Japan. Nat. Cong. Appl. Math.|page=437}}
{{citation|first1=San|last1=Ling|first2=Chaoping|last2=Xing|title=Coding Theory / A First Course|publisher=Cambridge University Press|year=2004|isbn=0-521-52923-9}}
{{citation | first1=F.J. | last1=MacWilliams | author1-link=Jessie MacWilliams | first2=N.J.A. | last2=Sloane | author2-link=Neil Sloane | title=The Theory of Error-Correcting Codes | publisher=North-Holland | date=1977 | isbn=0-444-85193-3 | pages=[https://archive.org/details/theoryoferrorcor0000macw/page/33 33, 37] | url=https://archive.org/details/theoryoferrorcor0000macw/page/33 }}
{{citation|first=Vera|last=Pless|author-link=Vera Pless|title=Introduction to the Theory of Error-Correcting Codes|title-link= Introduction to the Theory of Error-Correcting Codes |edition=3rd|publisher=Wiley Interscience|year=1998|isbn=0-471-19047-0}}
{{citation|first=Steven|last=Roman|title=Coding and Information Theory|series=GTM|volume=134|publisher=Springer-Verlag|year=1992|isbn=0-387-97812-7}}
{{citation| first=R.C.|last=Singleton | title=Maximum distance q-nary codes | journal=IEEE Trans. Inf. Theory | volume=10 | pages=116–118 | year=1964 | doi=10.1109/TIT.1964.1053661 | issue=2 }}
{{citation|first=L. R.|last= Vermani|title=Elements of algebraic coding theory|publisher=Chapman & Hall|year= 1996}}
{{citation|first=Dominic|last=Welsh|title=Codes and Cryptography|year=1988|publisher=Oxford University Press|isbn=0-19-853287-3}}