www.wikidata.de-de.nina.az

Singleton Schranke Die bezeichnet eine obere Schranke für die Mindestdistanz d displaystyle d eines Blockcodes der Länge

Singleton-Schranke

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

Sie lautet:

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

  • Annahme: Alphabet
  • Anzahl der möglichen Informationswörter :
  • Anzahl der Codewörter:
  • Mindestdistanz:

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

Deswegen muss auch die Anzahl der durch die Länge erzeugbaren Wörter sein. Stellt man diese Gleichung um, ergibt sich daraus die Singleton-Schranke

Für nicht-lineare Codes gilt entsprechend

wobei .

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

Beziehung zur Hamming-Schranke Bearbeiten

Im Falle der Hamming-Schranke ist die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming-Distanz .

Die Hamming-Schranke sagt aus, dass

beziehungsweise

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

Für zum Beispiel und (erfordert eine Hamming-Distanz von ) erhält man in Abhängigkeit von der Größe des Alphabets :

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

Im Falle der Singleton-Schranke ist die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Mindestdistanz .

Für zum Beispiel und (erfordert eine Mindestdistanz von ) erhält man:

unabhängig von . 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 und .

Literatur Bearbeiten

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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Singleton Schranke bezeichnet eine obere Schranke fur die Mindestdistanz d displaystyle d eines Blockcodes der Lange n displaystyle n bei Informationswortern der Lange k displaystyle k uber einem einheitlichen Alphabet S displaystyle Sigma Sie lautet d n k 1 displaystyle d leq n k 1 Die Schranke kann auf folgende Art intuitiv klargemacht werden Annahme Alphabet S 0 q 1 displaystyle Sigma 0 ldots q 1 Anzahl der moglichen Informationsworter I q k displaystyle mathcal I q k Anzahl der Codeworter C I q k displaystyle mathcal C mathcal I q k Mindestdistanz d displaystyle d Streicht man nun in den Codewortern jeweils die letzten d 1 displaystyle d 1 der n displaystyle n Stellen so haben die ubrigen Codeworter zueinander immer noch mindestens den Hamming Abstand 1 Bei d displaystyle d Streichungen ware dies nicht mehr gewahrleistet Damit sind immer noch alle Codeworter unterschiedlich also C C q k displaystyle mathcal C mathcal C q k Deswegen muss auch die Anzahl der durch die Lange n d 1 displaystyle n d 1 erzeugbaren Worter q n d 1 q k displaystyle q n d 1 geq q k sein Stellt man diese Gleichung um ergibt sich daraus die Singleton Schranke n d 1 k d n k 1 displaystyle n d 1 geq k Leftrightarrow d leq n k 1 Fur nicht lineare Codes gilt entsprechend M q n d 1 displaystyle M leq q n d 1 wobei M C displaystyle M mathcal C Codes die die Singleton Schranke mit Gleichheit erfullen nennt man auch MDS Codes Beziehung zur Hamming Schranke BearbeitenIm Falle der Hamming Schranke ist t d 1 2 displaystyle t lfloor d 1 2 rfloor nbsp die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Hamming Distanz d displaystyle d nbsp Die Hamming Schranke sagt aus dass q n q k i 0 t q 1 i n i displaystyle q n geq q k sum i 0 t q 1 i binom n i nbsp beziehungsweise n k log q i 0 t q 1 i n i displaystyle n geq k log q sum i 0 t q 1 i binom n i nbsp erfullt sein muss fur einen Code der mittels n displaystyle n nbsp Symbolen eines Alphabets S displaystyle Sigma nbsp der Grosse q displaystyle q nbsp eine Nachricht mit der Lange k displaystyle k nbsp transportiert Fur zum Beispiel n 512 displaystyle n 512 nbsp und t 11 displaystyle t 11 nbsp erfordert eine Hamming Distanz von d 23 displaystyle d 23 nbsp erhalt man in Abhangigkeit von der Grosse q displaystyle q nbsp des Alphabets S displaystyle Sigma nbsp q 2 k 438 374 6 displaystyle q 2 k leq 438 3746 nbsp q 4 k 466 480 7 displaystyle q 4 k leq 466 4807 nbsp q 16 k 482 857 2 displaystyle q 16 k leq 482 8572 nbsp q 2 8 k 491 808 6 displaystyle q 2 8 k leq 491 8086 nbsp q 2 16 k 496 400 4 displaystyle q 2 16 k leq 496 4004 nbsp q 2 32 k 498 700 2 displaystyle q 2 32 k leq 498 7002 nbsp q 2 64 k 499 850 1 displaystyle q 2 64 k leq 499 8501 nbsp q 2 128 k 500 425 0 displaystyle q 2 128 k leq 500 4250 nbsp q 2 256 k 500 712 5 displaystyle q 2 256 k leq 500 7125 nbsp q k 501 000 0 displaystyle q to infty k leq 501 0000 nbsp Die Hamming Schranke macht vergleichsweise genaue Aussagen in Abhangigkeit von n displaystyle n nbsp t displaystyle t nbsp und q displaystyle q nbsp Fur sehr grosse q displaystyle q nbsp strebt sie einem Grenzwert zu Im Falle der Singleton Schranke ist t d 1 2 n k 2 displaystyle t lfloor d 1 2 rfloor lfloor n k 2 rfloor nbsp die Anzahl der maximal korrigierbaren Fehler eines Codes mit der Mindestdistanz d displaystyle d nbsp Fur zum Beispiel n 512 displaystyle n 512 nbsp und t 11 displaystyle t 11 nbsp erfordert eine Mindestdistanz von d 12 displaystyle d 12 nbsp erhalt man k 501 displaystyle k leq 501 nbsp unabhangig von q displaystyle q nbsp Die Singleton Schranke ist eine ungenauere Abschatzung als die Hamming Schranke die die Grosse des Alphabets nicht berucksichtigt Weiterhin gibt es Unterschiede in der Beziehung zwischen t displaystyle t nbsp und d displaystyle d nbsp Literatur BearbeitenJ 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 uberarbeitete Auflage Oldenbourg Verlag Munchen 2013 ISBN 3 486 72128 3 Otto Mildenberger Hrsg Informationstechnik kompakt Theoretische Grundlagen Friedrich Vieweg amp 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 BearbeitenCodierungstheorie abgerufen am 22 September 2017 Algebraische Codierungstheorie abgerufen am 22 September 2017 Einfuhrung in die Codierungstheorie abgerufen am 22 September 2017 Signale und Codes abgerufen am 22 September 2017 FEHLERKORRIGIERENDE CODES abgerufen am 22 September 2017 Abgerufen von https de wikipedia org w index php title Singleton Schranke amp oldid 236970574