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|\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:

$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.

Siehe auch

• Optimaler Code