Kraft–McMillan-Theorem

Kraft–McMillan-Theorem

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

Dann gilt:

\sum_{i=1}^n q^{-\ell_i} \leq 1

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

Beweis

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

\sum_{v \in Blaetter} q^{-depth(v)} = \sum_{v\in Blaetter} q^{0} = 1

Da ein Knoten eines q-nären Baumes maximal q Kinder hat oder ein Blatt ist, verteilt jeder Knoten seinen Wert q k (Tiefe k) auf maximal q Kinder mit dem Wert q − (k + 1), die zusammen höchsten einen Wert von q \cdot q^{-(k+1)} = q^{-(k+1)+1} = q^{-k} besitzen. Ist der Baum unvollständig, dh. besitzt ein Knoten weniger als k Kinder, so sinkt die Summe sogar unter 1. Die Ungleichung wird genau dann verletzt, wenn innere Knoten als Blätter verwendet werden, weil zB. alle Knoten auf einer Tiefenebene als Codewort verwendet werden, gleichzeitig aber noch längere, tiefer liegendere 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, dh. ein Pfad mit der Länge \ell_i existiert, während in einem anderen Ast noch tiefer liegendere 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 C über dem Alphabet der Länge q die Längen der Codeworte \ell_1,\ldots,\ell_n 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

Sei l_{i} \in N für alle  i\in N \rightarrow \exists genau dann ein präfixfreier Binärcode, wenn  \sum_{i=1}^{\infty} 2^-l_i\leq 1 \sum_{i=1}^{\infty}a_i = \lim_{n \rightarrow \infty} \sum{i=1}^{n}a_i

"\Rightarrow"

Seien b_1 , b_2 , \dots präfixfreie Binärcode mit Codewortlängen l_1 , l_2 , \dots

\sum_{i=1}^{\infty}2^{-l_i} = \lim_{n \rightarrow \infty}\sum_{i=1}^{\infty}2^{-l_i}. Da \forall n \in N, b_1 \dots b_n endlicher präfixfreier Binärcode, gilt weiter für \forall n

\sum_{i=1}^{n}2^{-l_i}\leq 1 \Rightarrow \lim_{n \rightarrow \infty} \sum_{i=1}^{n}2^{-l_i}\leq 1

"\Leftarrow"

Sei l_i \in N \sum_{i=1}^{\infty}2^{-l_i}\leq 1

Die Summe konvergiert absolut \Rightarrow wir können umsortieren \Rightarrow o.B.d.A l_1 \leq l_2 \leq \dots

Induktion nach k
k = 1 OK
k \rightarrow k+1 haben präfixfreien Binärcode b_1 \dots b_k zu l_1 \dots l_k, repräsentiere B als Binärbaum D und ersetze dann jedes Blatt der aktuellen Tiefe durch vollständigen Binärbaum der Höhe lk + 1l + 1. Das ändert nichts an der "Hinzufügbarkeit", alle Blätter in D' haben Tiefe lk + 1 und an der Summe ändert sich auch nichts, denn  2^{-l}=2^{(l_k+1 -l)}2^{-l_k+1}.

Sei b gleich der Anzahl der Blätter in T \sum_{i=1}^{k}2^{-l_k} < 1. Dann gilt b2^{-l_{k+1}} \Leftrightarrow b< 2^{k+1} \Rightarrow T' nicht vollständig \Rightarrow Können Codewort mit Länge lk + 1 hinzufügen \Rightarrow def. b induktiv, daraus ergibt sich präfixfreier Binärcode.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kraft's inequality — In coding theory, Kraft s inequality, named after Leon Kraft, gives a necessary and sufficient condition for the existence of a uniquely decodable code for a given set of codeword lengths. Its applications to prefix codes and trees often find use …   Wikipedia

  • Kullback–Leibler divergence — In probability theory and information theory, the Kullback–Leibler divergence[1][2][3] (also information divergence, information gain, relative entropy, or KLIC) is a non symmetric measure of the difference between two probability distributions P …   Wikipedia

  • Minimum description length — The minimum description length (MDL) principle is a formalization of Occam s Razor in which the best hypothesis for a given set of data is the one that leads to the best compression of the data. MDL was introduced by Jorma Rissanen in 1978. It is …   Wikipedia

  • Liste von Physikern — Die Liste von Physikern ist alphabetisch sortiert und enthält nur Forscher, die wesentliche Beiträge zum Fachgebiet geleistet haben. Die Liste soll neben den Lebensdaten das Fachgebiet des Forschers nennen und wenige Stichworte zu den Aspekten… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”