Kraft-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Kraft-Ungleichung, auch als Kraft-McMillan-Ungleichung bezeichnet, ist in der Kodierungstheorie eine notwendige und hinreichende Bedingung für die Existenz eines eindeutig dekodierbaren Codes für einen gegebenen Satz an Schlüssellängen. Seine Implikationen auf Präfixcodes und Binärbäume finden häufig in der Informatik und Informationstheorie Anwendung.

Die Kraft-Ungleichung wurde 1949 von Leon G. Kraft entwickelt, wobei er in seiner Arbeit ausschließlich Präfixcodes behandelte.[1] Unabhängig von Kraft gelangte Brockway McMillan 1956 zu identischen Ergebnissen.[2]

Aussage[Bearbeiten | Quelltext bearbeiten]

Sei T ein (n,q)-Baum mit maximal q Kindknoten je Knoten und n Blättern, deren Tiefen seien.

Dann gilt:

Gleichheit gilt, falls T ein vollständiger Baum ist.

Beweis[Bearbeiten | Quelltext bearbeiten]

Man sieht leicht, dass für einen Baum der Tiefe 0 gilt:

Da ein Knoten eines -nären Baumes maximal Kinder hat oder ein Blatt ist, verteilt jeder Knoten seinen Wert (Tiefe ) auf maximal Kinder mit dem Wert , die zusammen höchstens einen Wert von besitzen. Ist der Baum unvollständig, d. h. besitzt ein Knoten weniger als Kinder, so sinkt die Summe sogar unter 1. Die Ungleichung wird genau dann verletzt, wenn innere Knoten als Blätter verwendet werden, weil z. B. alle Knoten auf einer Tiefenebene als Codewort verwendet werden, gleichzeitig aber noch längere, tiefer liegende Codewörter existieren. Da diese längeren Codewörter dann aber ein Codewort als Präfix haben, ist dadurch auch die Eigenschaft der Präfixfreiheit verletzt. Es ist natürlich möglich und auch nicht selten, dass der Baum unbalanciert ist, d. h. ein Pfad mit der Länge existiert, während in einem anderen Ast noch tiefer liegende Blätter zu finden sind.

Andererseits ist es aber auch möglich, „dumme“ Codes zu konstruieren, die die Ungleichung erfüllen, aber trotzdem einen Teil eines Pfades zu einem Blatt als Codewort verwenden.

Im Kontext der Codierungstheorie müssen für jeden eindeutig dekodierbaren Code über dem Alphabet der Länge die Längen der Codewörter die Kraft-Ungleichung erfüllen. In der Umkehrung existiert zu jeder Menge von Codewort-Längen, welche die Kraft-Ungleichung erfüllt, ein eindeutig dekodierbarer, präfixfreier Code mit diesen Längen.

Beweis für unendliche Folgen von Codewortlängen[Bearbeiten | Quelltext bearbeiten]

Sei für alle genau dann ein präfixfreier Binärcode, wenn

Seien präfixfreie Binärcode mit Codewortlängen

. Da endlicher präfixfreier Binärcode, gilt weiter für

Sei Die Summe konvergiert absolut wir können umsortieren o.B.d.A

Induktion nach k

OK
haben präfixfreien Binärcode zu , repräsentiere B als Binärbaum D und ersetze dann jedes Blatt der aktuellen Tiefe durch vollständigen Binärbaum der Höhe . Das ändert nichts an der "Hinzufügbarkeit", alle Blätter in D' haben Tiefe und an der Summe ändert sich auch nichts, denn

Sei b gleich der Anzahl der Blätter in T . Dann gilt T' nicht vollständig Können Codewort mit Länge hinzufügen def. b induktiv, daraus ergibt sich präfixfreier Binärcode.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • John G. Proakis, Masoud Salehi: Digital Communications. 5. Auflage. McGraw Hill, 2008, ISBN 978-0-07-126378-8, S. 340–342.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Leon G. Kraft: A device for quantizing, grouping, and coding amplitude modulated pulses. Hrsg.: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology. Cambridge, MA 1949 (Online).
  2. Brockway McMillan: Two inequalities implied by unique decipherability. In: IEEE Trans. Information Theory. Band 2, Nr. 4, 1956, S. 115–116 (Online).