Plotkin-Grenze

Plotkin-Grenze

In der Kanalcodierung verwendet man Blockcodes, um Fehler in Datenströmen erkennen und korrigieren zu können. Jeder Blockcode C der Länge n über einem q-nären Alphabet mit einem Minimalabstand d erfüllt die Plotkin-Grenze[1][2] (oder -Schranke)

 |C|\leq \frac{d}{d-(\frac{q-1}{q})\cdot n} ,

sofern der Nenner positiv ist. Somit liefert die Plotkin-Grenze nur dann ein Resultat, wenn d hinreichend nahe bei n liegt.

Nimmt ein Code C die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau d ist.

Ist q\geq 3 und |C|=a\cdot q+b mit b < q, so gilt sogar die schärfere Beziehung[3]

 d{|C|\choose 2}\leq n\left({|C|\choose 2}-b{a+1\choose 2}-(q-b){a\choose 2}\right).

Beispielsweise liefert die Plotkin-Grenze für q = 3, n = 9 und d = 7 nur |C|\leq 7, die Verschärfung jedoch |C|\leq 6, da sich für a = 2 und b = 1 ein Widerspruch ergibt.

Einzelnachweise

  1. M. Plotkin: Binary codes with specified minimum distance, IRE Transactions on Information Theory, 6:445-450, 1960 (engl.)
  2. W.C. Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003 (engl.)
  3. Die Plotkin-Grenze und ihre Verschärfung (engl.)

Siehe auch


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”