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

• Optimaler Code