Singleton-Schranke

mathematischer Satz

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