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