Singleton bound

The singleton limit designates an upper limit for the minimum distance of a block code of length for information words of length over a uniform alphabet . ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \Sigma }$

It is:

${\displaystyle d\leq n-k+1}$

The barrier can be made intuitively clear in the following way:

• Assumption: alphabet ${\displaystyle \Sigma =\{0,\ldots ,q-1\}}$
• Number of possible information words: ${\displaystyle |{\mathcal {I}}|=q^{k}}$
• Number of code words: ${\displaystyle |{\mathcal {C}}|=|{\mathcal {I}}|=q^{k}}$
• Minimum distance: ${\displaystyle d}$

If the last ( ) of the positions in the code words is deleted , the remaining code words still have at least the Hamming distance 1 from one another . In the case of deletions, this would no longer be guaranteed. So all code words are still different, so ${\displaystyle d-1}$ ${\displaystyle n}$ ${\displaystyle d}$

${\displaystyle |{\mathcal {C}}'|=|{\mathcal {C}}|=q^{k}}$

This is why the number of words that can be generated by the length must also be. If you rearrange this equation, the singleton limit results ${\displaystyle n-(d-1)}$ ${\displaystyle q^{n-d+1}\geq q^{k}}$

${\displaystyle n-d+1\geq k\Leftrightarrow d\leq n-k+1}$

The same applies to non-linear codes

${\displaystyle M\leq q^{n-d+1}}$,

whereby . ${\displaystyle M=|{\mathcal {C}}|}$

Codes that satisfy the singleton limit with equality are also called MDS codes .

Relationship to the Hamming bound

In the case of the Hamming barrier, the maximum number of correctable errors in a code is the Hamming distance . ${\displaystyle t=\lfloor (d-1)/2\rfloor }$ ${\displaystyle d}$

The Hamming bound states that

${\displaystyle q^{n}\geq q^{k}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}$,

respectively

${\displaystyle n\geq k+\log _{q}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}$

must be fulfilled for a code that uses symbols of an alphabet of size to transport a message of length . ${\displaystyle n}$ ${\displaystyle \Sigma }$ ${\displaystyle q}$ ${\displaystyle k}$

For example and (requires a Hamming distance of ) one gets, depending on the size of the alphabet : ${\displaystyle n=512}$ ${\displaystyle t=11}$ ${\displaystyle d=23}$ ${\displaystyle q}$ ${\displaystyle \Sigma }$

• ${\displaystyle q=2:k\leq 438{,}3746}$
• ${\displaystyle q=4:k\leq 466{,}4807}$
• ${\displaystyle q=16:k\leq 482{,}8572}$
• ${\displaystyle q=2^{8}:k\leq 491{,}8086}$
• ${\displaystyle q=2^{16}:k\leq 496{,}4004}$
• ${\displaystyle q=2^{32}:k\leq 498{,}7002}$
• ${\displaystyle q=2^{64}:k\leq 499{,}8501}$
• ${\displaystyle q=2^{128}:k\leq 500{,}4250}$
• ${\displaystyle q=2^{256}:k\leq 500{,}7125}$
• ${\displaystyle q\to \infty :k\leq 501{,}0000}$

The Hamming bound makes comparatively precise statements depending on , and . For very large ones it strives towards a limit value. ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle q}$ ${\displaystyle q}$

In the case of the singleton barrier, the maximum number of correctable errors of a code is the minimum distance . ${\displaystyle t=d-1}$ ${\displaystyle d}$

For example and (requires a minimum distance of ) one gets: ${\displaystyle n=512}$ ${\displaystyle t=11}$ ${\displaystyle d=12}$

• ${\displaystyle k\leq 501}$

regardless of . The singleton bound is a less precise estimate than the Hamming bound, which does not take into account the size of the alphabet. There are also differences in the relationship between and . ${\displaystyle q}$ ${\displaystyle t}$ ${\displaystyle d}$

literature

• JH van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics) . 2nd Edition. Springer, Berlin, ISBN 978-3-540-54894-2 .
• Martin Bossert: Channel Coding . 3rd revised edition, Oldenbourg Verlag, Munich 2013, ISBN 3-486-72128-3 .
• Otto Mildenberger (Ed.): Information technology compact. Theoretical foundations. Friedrich Vieweg & Sohn Verlag, Wiesbaden 1999, ISBN 3-528-03871-3 .
• Werner Heise, Pasquale Quattrocchi: Information and Coding Theory . 2nd edition, Springer Verlag, Berlin / Heidelberg 1989, ISBN 978-3-540-50537-2 .

Web links

• Coding Theory (accessed September 22, 2017)
• Algebraic Coding Theory (accessed September 22, 2017)
• Introduction to Coding Theory (accessed September 22, 2017)
• Signals and Codes (accessed September 22, 2017)
• ERROR-CORRECTING CODES (accessed September 22, 2017)