Singleton-Schranke

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

Sie lautet:

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

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

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

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

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

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

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

Für nicht-lineare Codes gilt entsprechend

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

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

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

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

Die Hamming-Schranke sagt aus, dass

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

beziehungsweise

${\displaystyle n\geq k+\log _{q}{\sum _{i=0}^{t}(q-1)^{i}{\binom {n}{i}}}}${\displaystyle 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 ${\displaystyle n}${\displaystyle n} Symbolen eines Alphabets ${\displaystyle \Sigma }${\displaystyle \Sigma } der Größe ${\displaystyle q}${\displaystyle q} eine Nachricht mit der Länge ${\displaystyle k}${\displaystyle k} transportiert.

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

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

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

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

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

• ${\displaystyle k\leq 501}${\displaystyle k\leq 501}

unabhängig von ${\displaystyle q}${\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 ${\displaystyle t}${\displaystyle t} und ${\displaystyle d}${\displaystyle d}.

• 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.

• 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)

• Nachrichtentechnik
• Diskrete Mathematik
• Kodierungstheorie
• Ungleichung