In der Kanalcodierung verwendet man Blockcodes, um Fehler in Datenströmen erkennen und korrigieren zu können. Ein Blockcode der Länge über einem -nären Alphabet mit einem Minimalabstand erfüllt die Plotkin-Grenze, auch als Plotkin-Schranke bezeichnet,Morris Plotkin: Binary codes with specified minimum distance. In: IRE Transactions on Information Theory. Nr. 6, 1960, S. 445–450, (englisch).W. Cary Huffman, Vera Pless: Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003, ISBN 0-511-80707-4, , S. 58 und S. 89 (englisch).
dann, wenn der Nenner positiv ist. Somit liefert die Plotkin-Grenze nur dann ein Resultat, wenn hinreichend nahe bei liegt.
Nimmt ein Code die Plotkin-Schranke an, so gilt insbesondere, dass der Abstand zweier beliebiger Codewörter genau ist.
Ist und mit , so gilt sogar die schärfere Beziehung:Jörn Quistorff: Some Remarks on the Plotkin Bound. In: The Electronic Journal of Combinatorics. Vol. 10, 2003, (englisch).
Beispielsweise liefert die Plotkin-Grenze für , und nur , die Verschärfung jedoch , da sich für und ein Widerspruch ergibt.
Sie wurde 1960 von Morris Plotkin veröffentlicht.
Siehe auch Optimaler Code
Einzelnachweise
Kategorie:Diskrete Mathematik Kategorie:Kodierungstheorie Kategorie:Übertragungstechnik