Plotkin-Grenze

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

${\displaystyle |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 ${\displaystyle d}$ hinreichend nahe bei ${\displaystyle n}$ liegt.

Nimmt ein Code ${\displaystyle C}$ die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau ${\displaystyle d}$ ist.

Ist ${\displaystyle q\geq 3}$ und ${\displaystyle |C|=a\cdot q+b}$ mit ${\displaystyle b<q}$, so gilt sogar die schärfere Beziehung:^[3]

${\displaystyle 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 ${\displaystyle q=3}$, ${\displaystyle n=9}$ und ${\displaystyle d=7}$ nur ${\displaystyle |C|\leq 7}$, die Verschärfung jedoch ${\displaystyle |C|\leq 6}$, da sich für ${\displaystyle a=2}$ und ${\displaystyle b=1}$ ein Widerspruch ergibt.

Sie wurde 1960 von Morris Plotkin veröffentlicht.