imported>SchlurcherBot: Bot: http → https

2025-10-10T22:56:27Z

Bot: http → https

Neue Seite

Die '''Singleton-Schranke''' bezeichnet eine obere Schranke für die [[Hamming-Abstand#Mindestdistanz|Mindestdistanz]] <math>d</math> eines [[Blockcode]]s der Länge <math>n</math> bei Informationswörtern der Länge <math>k</math> über einem einheitlichen Alphabet <math>\Sigma</math>.

Sie lautet:

:<math>d \le n-k+1</math>

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

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

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

: <math>|\mathcal C'| = |\mathcal C| = q^k</math>

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

:<math>n-d+1\geq k \Leftrightarrow d\leq n-k+1</math>

Für nicht-lineare Codes gilt entsprechend

:<math>M \le q^{n-d+1}</math>,

wobei <math>M = |\mathcal C|</math>.

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

== Beziehung zur Hamming-Schranke ==

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

Die Hamming-Schranke sagt aus, dass
:<math> q^n \geq q^k {\sum_{i=0}^t(q-1)^i \binom n i} </math>,
beziehungsweise
:<math> n \geq k + \log_q{\sum_{i=0}^t(q-1)^i \binom n i} </math>
erfüllt sein muss für einen Code, der mittels <math>n</math> Symbolen eines Alphabets <math>\Sigma</math> der Größe <math>q</math> eine Nachricht mit der Länge <math>k</math> transportiert.

Für zum Beispiel <math>n = 512</math> und <math>t = 11</math> (erfordert eine Hamming-Distanz von <math>d = 23</math>) erhält man in Abhängigkeit von der Größe <math>q</math> des Alphabets <math>\Sigma</math>:
* <math>q=2: k \leq 438{,}3746</math>
* <math>q=4: k \leq 466{,}4807</math>
* <math>q=16: k \leq 482{,}8572</math>
* <math>q=2^{8}: k \leq 491{,}8086</math>
* <math>q=2^{16}: k \leq 496{,}4004</math>
* <math>q=2^{32}: k \leq 498{,}7002</math>
* <math>q=2^{64}: k \leq 499{,}8501</math>
* <math>q=2^{128}: k \leq 500{,}4250</math>
* <math>q=2^{256}: k \leq 500{,}7125</math>
* <math>q \to \infty: k \leq 501{,}0000</math>
Die Hamming-Schranke macht vergleichsweise genaue Aussagen in Abhängigkeit von <math>n</math>, <math>t</math> und <math>q</math>. Für sehr große <math>q</math> strebt sie einem Grenzwert zu.

Im Falle der Singleton-Schranke ist <math>t = \lfloor(d - 1)/2\rfloor = \lfloor(n-k)/2\rfloor </math> die Anzahl der maximal korrigierbaren Fehler eines Codes mit der [[Hamming-Abstand#Mindestdistanz|Mindestdistanz]] <math>d</math>.

Für zum Beispiel <math>n = 512</math> und <math>t = 11</math> (erfordert eine Mindestdistanz von <math>d = 12</math>) erhält man:
* <math>k \leq 501</math>
unabhängig von <math>q</math>. 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 <math>t</math> und <math>d</math>.

== Literatur ==
*{{Literatur | Autor = J.H. van Lint | Titel = Introduction to Coding Theory (Graduate Texts in Mathematics) | Verlag = Springer | Ort = Berlin | Auflage = 2. | 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 ==
* [https://www.math.rwth-aachen.de/~Sebastian.Thomas/teaching/codierungstheorie_09/vorlesung02.pdf Codierungstheorie] (abgerufen am 22. September 2017)
* [http://www.stud.fernuni-hagen.de/q7267622/wp-content/uploads/2012/07/coding-theory.pdf Algebraische Codierungstheorie] (abgerufen am 22. September 2017)
* [http://mint.sbg.ac.at/rudi/CodingTheory2007/vl.pdf Einführung in die Codierungstheorie] (abgerufen am 22. September 2017)
* [https://crypto.iti.kit.edu/fileadmin/User/Signale_und_Codes/WS_15_16/SignaleundCodes.pdf Signale und Codes] (abgerufen am 22. September 2017)
* [http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/FKC/outline.pdf FEHLERKORRIGIERENDE CODES] (abgerufen am 22. September 2017)

[[Kategorie:Nachrichtentechnik]]
[[Kategorie:Diskrete Mathematik]]
[[Kategorie:Kodierungstheorie]]
[[Kategorie:Ungleichung]]

Singleton-Schranke - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https