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$:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2: k \leq 438{,}3746}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=4: k \leq 466{,}4807}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=16: k \leq 482{,}8572}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{8}: k \leq 491{,}8086}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{16}: k \leq 496{,}4004}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{32}: k \leq 498{,}7002}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{64}: k \leq 499{,}8501}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{128}: k \leq 500{,}4250}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q=2^{256}: k \leq 500{,}7125}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q \to \infty: k \leq 501{,}0000}

Die Hamming-Schranke macht vergleichsweise genaue Aussagen in Abhängigkeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} . Für sehr große Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} strebt sie einem Grenzwert zu.

Im Falle der Singleton-Schranke ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t = d - 1} die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Mindestdistanz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} .

Für zum Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 512} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t = 11} (erfordert eine Mindestdistanz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = 12} ) erhält man:

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \leq 501}

unabhängig von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} .

Literatur

• J.H. van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics). 2. Auflage. Springer, Berlin, ISBN 978-3-540-54894-2. 
• Martin Bossert: Kanalcodierung. 3. überarbeitete Auflage, Oldenbourg Verlag, München 2013, ISBN 3-486-72128-3.
• Otto Mildenberger (Hrsg.): Informationstechnik kompakt. Theoretische Grundlagen. Friedrich Vieweg & Sohn Verlag, Wiesbaden 1999, ISBN 3-528-03871-3.
• Werner Heise, Pasquale Quattrocchi: Informations- und Codierungstheorie. 2. Auflage, Springer Verlag, Berlin / Heidelberg 1989, ISBN 978-3-540-50537-2.

Weblinks

• Codierungstheorie (abgerufen am 22. September 2017)
• Algebraische Codierungstheorie (abgerufen am 22. September 2017)
• Einführung in die Codierungstheorie (abgerufen am 22. September 2017)
• Signale und Codes (abgerufen am 22. September 2017)
• FEHLERKORRIGIERENDE CODES (abgerufen am 22. September 2017)