Singleton-Schranke
# Singleton-Schranke

Die Singleton-Schranke bezeichnet eine obere Schranke für die Mindestdistanz $d$ eines Blockcodes der Länge $n$ bei Informationswörtern der Länge $k$ über einem einheitlichen Alphabet $\Sigma$.

Sie lautet:

    $d\leq n-k+1$

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

* Annahme: Alphabet $\Sigma =\{0,\ldots ,q-1\}$
* Anzahl der möglichen Informationswörter : $|{\mathcal {I}}|=q^{k}$
* Anzahl der Codewörter: $|{\mathcal {C}}|=|{\mathcal {I}}|=q^{k}$
* Mindestdistanz: $d$

Streicht man nun in den Codewörtern jeweils die letzten ($d-1$) der $n$ Stellen, so haben die übrigen Codewörter zueinander immer noch mindestens den Hamming-Abstand 1. Bei $d$ Streichungen wäre dies nicht mehr gewährleistet. Damit sind immer noch alle Codewörter unterschiedlich, also

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

Deswegen muss auch die Anzahl der durch die Länge $n-(d-1)$ erzeugbaren Wörter $q^{n-d+1}\geq q^{k}$ sein. Stellt man diese Gleichung um, ergibt sich daraus die Singleton-Schranke

    $n-d+1\geq k\Leftrightarrow d\leq n-k+1$

Für nicht-lineare Codes gilt entsprechend

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

wobei $M=|{\mathcal {C}}|$.

Codes, die die Singleton-Schranke mit Gleichheit erfüllen, nennt man auch MDS-Codes.

## Beziehung zur Hamming-Schranke

Im Falle der Hamming-Schranke ist $t=\lfloor (d-1)/2\rfloor$ die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz $d$.

Die Hamming-Schranke sagt aus, dass

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

beziehungsweise

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

erfüllt sein muss für einen Code, der mittels $n$ Symbolen eines Alphabets $\Sigma$ der Größe $q$ eine Nachricht mit der Länge $k$ transportiert.

Für zum Beispiel $n=512$ und $t=11$ (erfordert eine Hamming-Distanz von $d=23$) erhält man in Abhängigkeit von der Größe $q$ des Alphabets $\Sigma$:

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

Die Hamming-Schranke macht vergleichsweise genaue Aussagen in Abhängigkeit von $n$, $t$ und $q$. Für sehr große $q$ strebt sie einem Grenzwert zu.

Im Falle der Singleton-Schranke ist $t=\lfloor (d-1)/2\rfloor =\lfloor (n-k)/2\rfloor$) die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Mindestdistanz $d$.

Für zum Beispiel $n=512$ und $t=11$ (erfordert eine Mindestdistanz von $d=12$) erhält man:

* $k\leq 501$

unabhängig von $q$. Die Singleton-Schranke ist eine ungenauere Abschätzung als die Hamming-Schranke, die die Größe des Alphabets nicht berücksichtigt. Weiterhin gibt es Unterschiede in der Beziehung zwischen $t$ und $d$.

