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.

1. ↑ Morris Plotkin: Binary codes with specified minimum distance. In: IRE Transactions on Information Theory. Nr. 6, 1960, S. 445–450, doi:10.1109/TIT.1960.1057584 (englisch).
2. ↑ W. Cary Huffman, Vera Pless: Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003, ISBN 0-511-80707-4, doi:10.1017/CBO9780511807077, S. 58 und S. 89 (englisch).
3. ↑ Jörn Quistorff: Some Remarks on the Plotkin Bound. In: The Electronic Journal of Combinatorics. Vol. 10, 2003, doi:10.37236/1746 (englisch).