Singleton-Schranke

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 Σ = {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$.

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