Singleton-Schranke
aus Wikipedia, der freien Enzyklopädie
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:
- .
Die Schranke kann auf folgende Art intuitiv klargemacht werden:
- Annahme: Alphabet Σ = {0,..,q − 1}
- Anzahl der möglichen Informationsworte : |I|=qk
- Anzahl der Codeworte: |C|=|I|= qk
- Mindestdistanz: d
Streicht man nun in den Codeworten jeweils die letzten (d-1) der n Stellen so haben die übrigen Codeworte zueinander immer noch mindestens den Hamming-Abstand 1(bei d Streichungen wäre dies nicht mehr gewährleistet). Damit sind immer noch alle Codeworte unterschiedlich also | C' | = | C | = qk. Deswegen muss auch die Anzahl der, durch die Länge n-(d-1) erzeugbaren, Worte sein. Stellt man diese Gleichung um ergibt sich daraus die Singleton-Schranke
- .
Codes die die Singleton-Schranke erfüllen nennt man auch MDS-Codes.