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,^[1]^[2]

|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:^[3]

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

Einzelnachweise

↑ M. Plotkin: Binary codes with specified minimum distance, IRE Transactions on Information Theory, 6:445-450, 1960 (engl.).
↑ W.C. Huffman, V. Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003 (engl.).
↑ Die Plotkin-Grenze und ihre Verschärfung (englisch).

[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).

[1]

[2]

[3]