Plotkin-Grenze

In der Kanalcodierung verwendet man Blockcodes, um Fehler in Datenströmen erkennen und korrigieren zu können. Ein Blockcode <math>C</math> der Länge <math>n</math> über einem <math>q</math>-nären Alphabet mit einem Minimalabstand <math>d</math> erfüllt die Plotkin-Grenze, auch als Plotkin-Schranke bezeichnet,<ref>Morris Plotkin: Binary codes with specified minimum distance. In: IRE Transactions on Information Theory. Nr. 6, 1960, S. 445–450, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}} (englisch).</ref><ref>W. Cary Huffman, Vera Pless: Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003, ISBN 0-511-80707-4, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}, S. 58 und S. 89 (englisch).</ref>

dann, wenn der Nenner positiv ist. Somit liefert die Plotkin-Grenze nur dann ein Resultat, wenn <math>d</math> hinreichend nahe bei <math>n</math> liegt.

Nimmt ein Code <math>C</math> die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau <math>d</math> ist.

Ist <math>q\geq 3</math> und <math>|C|=a\cdot q+b</math> mit <math>b<q</math>, so gilt sogar die schärfere Beziehung:<ref>Jörn Quistorff: Some Remarks on the Plotkin Bound. In: The Electronic Journal of Combinatorics. Vol. 10, 2003, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}} (englisch).</ref>

<math> d{|C|\choose 2}\leq n\left({|C|\choose 2}-b{a+1\choose 2}-(q-b){a\choose 2}\right)</math>

Beispielsweise liefert die Plotkin-Grenze für <math>q=3</math>, <math>n=9</math> und <math>d=7</math> nur <math>|C|\leq 7</math>, die Verschärfung jedoch <math>|C|\leq 6</math>, da sich für <math>a=2</math> und <math>b=1</math> ein Widerspruch ergibt.

Sie wurde 1960 von Morris Plotkin veröffentlicht.

Siehe auch

Optimaler Code

Einzelnachweise