imported>Jesi: Erg., Korr.

2024-08-01T16:21:32Z

Erg., Korr.

Neue Seite

In der [[Kanalcodierung]] verwendet man [[Blockcode]]s, 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, {{doi|10.1109/TIT.1960.1057584}} (englisch).</ref><ref>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).</ref>

:<math> |C|\leq \frac{d}{d-(\frac{q-1}{q})\cdot n} </math>

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: [https://www.combinatorics.org/ojs/index.php/eljc/article/view/v10i1n6/pdf ''Some Remarks on the Plotkin Bound.''] In: ''The Electronic Journal of Combinatorics.'' Vol. 10, 2003, {{doi|10.37236/1746}} (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 ==
<references />

[[Kategorie:Diskrete Mathematik]]
[[Kategorie:Kodierungstheorie]]
[[Kategorie:Übertragungstechnik]]

Plotkin-Grenze - Versionsgeschichte

imported>Jesi: Erg., Korr.