Plotkin-Grenze

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

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

dann, wenn 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.

Sie wurde 1960 von Morris Plotkin veröffentlicht.

Einzelnachweise[Bearbeiten]

  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[Bearbeiten]