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 w​urde 1960 v​on Morris Plotkin veröffentlicht.

Siehe auch

• Optimaler Code

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 (englisch).