Plotkin-Grenze

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,

$|C|\le \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\ge 3$ und $|C|=a\cdot q+b$ mit $b<q$, so gilt sogar die schärfere Beziehung:

$d(\genfrac{}{}{0ex}{}{|C|}{2})\le n((\genfrac{}{}{0ex}{}{|C|}{2})-b(\genfrac{}{}{0ex}{}{a+1}{2})-(q-b)(\genfrac{}{}{0ex}{}{a}{2}))$

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

Sie wurde 1960 von Morris Plotkin veröffentlicht.

Siehe auch

• Optimaler Code