Singleton-Schranke

Die Singleton-Schranke bezeichnet eine obere Schranke für die Mindestdistanz ${\displaystyle d}$ eines Blockcodes der Länge ${\displaystyle n}$ bei Informationswörtern der Länge ${\displaystyle k}$ über einem einheitlichen Alphabet ${\displaystyle \Sigma }$.

Sie lautet:

${\displaystyle d\leq n-k+1}$

Die Schranke kann auf folgende Art intuitiv klargemacht werden:

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

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

${\displaystyle |{\mathcal {C}}'|=|{\mathcal {C}}|=q^{k}}$

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

${\displaystyle n-d+1\geq k\Leftrightarrow d\leq n-k+1}$

Für nicht-lineare Codes gilt entsprechend

${\displaystyle M\leq q^{n-d+1}}$,

wobei ${\displaystyle M=|{\mathcal {C}}|}$.

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