Singleton-Schranke

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

d \le n-k+1

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

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

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

|C'|=|C|=q^k

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

n-d+1\geq k \Leftrightarrow d\leq n-k+1

Für nicht-lineare Codes gilt entsprechend M\le q^{n-d+1} wobei M=|C|.

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

Literatur[Bearbeiten]

  •  J.H. van Lint: Introduction to Coding Theory (Graduate Texts in Mathematics). 2. Auflage. Springer, Berlin, ISBN 978-3-540-54894-2.