Singleton barrier-Wikipedia

The Singleton barrier describes an upper barrier for the minimum distance

${displaystyle d}$

of a block code of the length

${displaystyle n}$

for information words of the length

${displaystyle k}$

About a uniform alphabet

${displaystyle Sigma }$

.

It is:

${displaystyle dleq n-k+1}$

The barrier can be intuitively cleared in the following way:

• Acceptance: 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}$

  

Now stroke the last in the code words (

${displaystyle d-1}$

) the

${displaystyle n}$

Position, the other code words still have at least the Hamming distance 1. at

${displaystyle d}$

Deletions would no longer be guaranteed. So all code words are still different, so

${displaystyle |{mathcal {C}}’|=|{mathcal {C}}|=q^{k}}$

That is why the number of length must also

${DisplayStyle N- (D-1)}$

Commerible words

${displaystyle q^{n-d+1}geq q^{k}}$

be.
If you change this equation, this results in the singleton barrier

${displaystyle n-d+1geq kLeftrightarrow dleq n-k+1}$

For non-linear codes applies accordingly

${displaystyle Mleq q^{n-d+1}}$

,

whereby

${displaystyle M=|{mathcal {C}}|}$

.

Codes that meet the singleton barrier with equality is also called MDS codes.

In the case of the Hamming barrier

${displaystyle t=lfloor (d-1)/2rfloor }$

The number of the maximum correctional errors of a code with the Hamming distance

${displaystyle d}$

.

The Hamming barrier says that

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

,

or

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

It must be fulfilled for a code that means

${displaystyle n}$

Symbols of an alphabet

${displaystyle Sigma }$

size

${displaystyle q}$

A message with the length

${displaystyle k}$

transported.

For example

${displaystyle n=512}$

and

${displaystyle t=11}$

(requires a Hamming distance of

${displaystyle d=23}$

) you get depending on the size

${displaystyle q}$

alphabets

${displaystyle Sigma }$

:

• 
  ${displaystyle q=2:kleq 438{,}3746}$

  

• 
  ${displaystyle q=4:kleq 466{,}4807}$

  

• 
  ${displaystyle q=16:kleq 482{,}8572}$

  

• 
  ${displaystyle q=2^{8}:kleq 491{,}8086}$

  

• 
  ${displaystyle q=2^{16}:kleq 496{,}4004}$

  

• 
  ${displaystyle q=2^{32}:kleq 498{,}7002}$

  

• 
  ${displaystyle q=2^{64}:kleq 499{,}8501}$

  

• 
  ${displaystyle q=2^{128}:kleq 500{,}4250}$

  

• 
  ${displaystyle q=2^{256}:kleq 500{,}7125}$

  

• 
  ${displaystyle qto infty :kleq 501{,}0000}$

  

The Hamming barrier makes comparatively precisely precise statements depending on

${displaystyle n}$

,

${displaystyle t}$

and

${displaystyle q}$

. For very large

${displaystyle q}$

it strives for a limit.

In the case of the singleton barrier is

${displaystyle t=d-1}$

The number of the maximum correctional errors of a code with the minimum distance

${displaystyle d}$

.

For example

${displaystyle n=512}$

and

${displaystyle t=11}$

(requires a minimum distance of

${displaystyle d=12}$

) you get:

• 
  ${displaystyle kleq 501}$

  

irrespective of

${displaystyle q}$

. The singleton barrier is an inaccurate assessment than the hamming barrier, which does not take into account the size of the alphabet.
There are also differences in the relationship between

${displaystyle t}$

and

${displaystyle d}$

.

• J.H. Van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics) . 2nd Edition. Springer, Berlin, ISBN 978-3-540-54894-2.
• Martin Bossert: Sewer coding . 3rd revised edition, Oldenbourg Verlag, Munich 2013, ISBN 3-486-72128-3.
• Otto Mildenberger (ed.): Information technology compact. Theoretical basics. 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.