Kraft-Ungleichung

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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \sum_{i=1}^{\inf 2^-l_i}\leq 1 }

$\sum _{i=1}^{\inf }a_{i}=\lim _{n\rightarrow \inf }\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$ Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \sum_{i=1}^{\inf}2^{-l_i} = \lim_{n \rightarrow \inf}\sum_{i=1}^{\inf}2^{-l_i}} . Da $\forall n\in N,b_{1}\dots b_{n}$endllicher präfixfreier Binärcode gilt weiter für $\forall n$ Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \sum_{i=1}^{n}2^{-l_i}\leq 1 \Rightarrow \lim_{n \rightarrow \inf} \sum_{i=1}^{n}2^{-l_i}\leq 1}

$\Leftarrow$

Sei $l_{i}\in N\sum _{i=1}^{inf}2^{-l_{i}}\leq 1$

Die Summe konvergiert absolut $\Rightarrow$ wir können umsortieren $\Rightarrow o.B.d.Al_{1}\leq l_{2}\leq \dots$

Induktion nach k

$k=1$ OK

$k\rightarrow k+1$ haben präfixfreien Binärcode Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle 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 $l_{k+1}-l+1$. Das ändert nichts an der "Hinzufügbarkeit", alle Blätter in D' haben Tiefe $l_{k+1}$ und an der Summe ändert sich auch nichts, denn $2^{-l}=2^{(l_{k}+1-l)}2^{-l_{k}+1}.$

Sei b = # 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 $l_{k+1}$ hinzufügen $\Rightarrow$ def. b induktiv, daraus ergibt sich präfixfreier Binärcode.

Literatur

• 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 (mit.edu). 
• B. McMillan: Two inequalities implied by unique decipherability. In: IEEE Trans. Information Theory. Band 2, Nr. 4, 1956, S. 115–116 (ieee.org).