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 der Länge über einem -nären Alphabet mit einem Minimalabstand erfüllt die Plotkin-Grenze, auch als Plotkin-Schranke bezeichnet,[1][2]

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

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

Ist und mit , so gilt sogar die schärfere Beziehung:[3]

Beispielsweise liefert die Plotkin-Grenze für , und nur , die Verschärfung jedoch , da sich für und ein Widerspruch ergibt.

Sie wurde 1960 von Morris Plotkin veröffentlicht.

Einzelnachweise[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]