Singleton-Schranke

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|=qk
  • Anzahl der Codewörter: |C|=|I|= qk
  • 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 | = qk. 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.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Block-Code — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Block-Codes — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Blockkode — systematischer Blockcode Ein Blockcode ist eine Art von Kanalkodierung, gekennzeichnet dadurch, dass die benutzten Codewörter alle dieselbe Anzahl an Symbolen aus einem Alphabet (Informatik), z. B. Bits haben. Obwohl Blockcodes häufig nicht… …   Deutsch Wikipedia

  • Hamming-Distanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming-Gewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hamming Abstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hammingabstand — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Hammingdistanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Mindestdistanz — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

  • Minimalgewicht — Der Hamming Abstand, die Hamming Distanz und das Hamming Gewicht, benannt nach dem US amerikanischen Mathematiker Richard Wesley Hamming (1915–1998), sind Maße für die Unterschiedlichkeit von Zeichenketten. Häufig handelt es sich um binär… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”