Difference between revisions of "Applets:Huffman- und Shannon-Fano-Codierung"

Latest revision as of 15:49, 28 May 2021

Programmbeschreibung

Dieses Applet verdeutlicht die Quellencodierverfahren nach Huffman bzw. Shannon–Fano. Diese Verfahren komprimieren redundante wertdiskrete Quellen ohne Gedächtnis mit Stufenzahl $M$, dem Symbolvorrat $\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \} = \{ \rm A, \hspace{0.1cm} B, \hspace{0.1cm}\text{ ...}\}$ und den Symbolwahrscheinlichkeiten $p_{\rm A} \hspace{0.05cm},\hspace{0.1cm} p_{\rm B} \hspace{0.05cm}, \hspace{0.05cm}\text{ ...}$ .

Ziel der Quellencodierung und insbesondere der Klasse der Entropiecodierung – zu der "Huffman" und "Shannon–Fano" gehören – ist, dass die mittlere Codewortlänge $L_{\rm M}$ des binären Codes – darstellbar durch unterschiedlich lange Folgen von Nullen und Einsen – möglichst nahe an die Quellenentropie

$$H = \sum_{\mu = 1}^{M} \hspace{0.2cm} {\rm Pr}(q_{\mu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\mu})} = -\sum_{\mu = 1}^{M} \hspace{0.2cm} {\rm Pr}(q_{\mu}) \cdot {\rm log_2}\hspace{0.1cm}{\rm Pr}(q_{\mu})\hspace{0.5cm}\big[\hspace{0.05cm}{\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Quellensymbol}\hspace{0.05cm}\big]$$

heranreicht. Allgemein gilt $L_{\rm M} \ge H$, wobei das Gleichheitszeichen nicht für alle Symbolwahrscheinlichkeiten erreicht werden kann.

Dargestellt werden jeweils

das Baumdiagramm zur Herleitung des jeweiligen Binärcodes, und
eine simulierte Quellensymbolfolge der Länge $N = 10000$ (Entropie $H\hspace{0.05cm}' \approx H)$ und die dazugehörige Codesymbolfolge der Länge $L_{\rm M}\hspace{0.05cm}' \hspace{-0.03cm}\cdot \hspace{-0.03cm} N$.

Auf die Einheiten "$\rm bit/Quellensymbol$" für die Entropie und die mittlere Codewortlänge wird im Programm verzichtet.

Theoretischer Hintergrund

Der Huffman–Algorithmus

Wir setzen voraus, dass die Quellensymbole $q_\nu$ einem Alphabet $\{q_μ\} = \{$ $\rm A$, $\rm B$ , $\rm C$ , ...$\}$ mit dem Symbolumfang $M$ entstammen und statistisch voneinander unabhängig seien. Beispielsweise gelte für den Symbolumfang $M = 8$:

$$\{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm}, \boldsymbol{\rm B}\hspace{0.05cm}, \boldsymbol{\rm C}\hspace{0.05cm}, \boldsymbol{\rm D}\hspace{0.05cm}, \boldsymbol{\rm E}\hspace{0.05cm}, \boldsymbol{\rm F}\hspace{0.05cm}, \boldsymbol{\rm G}\hspace{0.05cm}, \boldsymbol{\rm H}\hspace{0.05cm} \}\hspace{0.05cm}.$$

David A. Huffman hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen zur Informationstheorie – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben. Dieser Huffman–Algorithmus soll ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt: Für die Codesymbole gelte stets $c_ν ∈ \{$0, 1$\}$. Hier ist die Vorgehensweise:

Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
Man wiederhole (1) und (2), bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
Man codiert die wahrscheinlichere Symbolmenge mit 1 und die andere Menge mit 0.
Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen gemäß den Wahrscheinlichkeiten mit 1 bzw. 0.

$\text{Beispiel 1:}$ Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die $M = 6$ Symbole $\rm A$, ... , $\rm F$ schon nach ihren Wahrscheinlichkeiten geordnet sind:

$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm}.$$

Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen
(resultierende Wahrscheinlichkeiten in Klammern):

1. $\rm A$ (0.30), $\rm B$ (0.24), $\rm C$ (0.20), $\rm EF$ (0.14), $\rm D$ (0.12),

2. $\rm A$ (0.30), $\rm EFD$ (0.26), $\rm B$ (0.24), $\rm C$ (0.20),

3. $\rm BC$ (0.44), $\rm A$ (0.30), $\rm EFD$ (0.26),

4. $\rm AEFD$ (0.56), $\rm BC$ (0.44),

5. Root $\rm AEFDBC$ (1.00).

Rückwärts – alsogemäß den Schritten (5) bis (1) – erfolgt dann die Zuordnung zu Binärsymbolen. Ein x weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen:

5. $\rm AEFD$ → 1x, $\rm BC$ → 0x,

4. $\underline{\rm A}$ → 11, $\rm EFD$ → 10x,

3. $\underline{\rm B}$ → 01, $\underline{\rm C}$ → 00,

2. $\rm EF$ → 101x, $\underline{\rm D}$ → 100,

1. $\underline{\rm E}$ → 1011, $\underline{\rm F}$ → 1010.

Die Unterstreichungen markieren die endgültige Binärcodierung.

Zum Begriff „Entropiecodierung”

Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:

$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm};$$

$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$

Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole $(\rm E$ und $\rm F)$ mit vier Bit codiert.

Die mittlere Codewortlänge ergibt sich damit zu

$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2 + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Aus dem Vergleich mit der Quellenentropie

$$H = -\big [0.3 \cdot {\rm log_2}\hspace{0.1cm}(0.3) + 0.24 \cdot {\rm log_2}\hspace{0.1cm}(0.24) + 0.2 \cdot {\rm log_2}\hspace{0.1cm}(0.2)+ 0.12 \cdot {\rm log_2}\hspace{0.1cm}(0.12) + 0.1 \cdot {\rm log_2}\hspace{0.1cm}(0.1)+ 0.04 \cdot {\rm log_2}\hspace{0.1cm}(0.04) \big ]= 2.365 \ \rm bit/Quellensymbol$$

erkennt man die Effizienz der Huffman–Codierung.

$\text{Beispiel 2:}$ Wären die Symbolwahrscheinlichkeiten

$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16 \hspace{0.05cm},$$

so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:

$$H = 3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4) + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm},$$

$$L_{\rm M} = 3 \cdot 1/4 \cdot 2 + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Aus dieser Eigenschaft $L_{\rm M} = H +\varepsilon$ mit $\varepsilon = 0$ bei geeigneten Auftrittswahrscheinlichkeiten erklärt sich der Begriff Entropiecodierung:

Man versucht bei dieser Form von Quellencodierung, die Länge $L_μ$ der Binärfolge (bestehend aus Nullen und Einsen) für das Symbol $q_μ$ gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit $p_μ$ anzupassen:

$$L_{\mu} = {\rm log}_2\hspace{0.1cm}(1/p_{\mu} ) \hspace{0.05cm}.$$

Da $L_μ$ im Gegensatz zu $\log_2(1/ p_μ$) ganzzahlig ist, gelingt dies nicht immer.

Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten $p_μ$ in der Form $2^{–k}$ mit $k = 1, 2, 3,$ ... dargestellt werden können.

In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge $L_{\rm M}$ exakt mit der Quellenentropie $H$ überein $(\varepsilon = 0$, siehe $\text{Beispiel 2}$).
Nach dem Quellencodierungstheorem gibt es keinen (decodierbaren) Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt.

$\text{Merke:}$ Es gibt keinen präfixfreien (⇒ sofort decodierbaren) Code, der allein unter Ausnutzung der Auftrittswahrscheinlichkeiten zu einer kleineren mittleren Codewortlänge $L_{\rm M}$ führt als der Huffman–Code. In diesem Sinne ist der Huffman–Code optimal.

Darstellung des Huffman–Codes als Baumdiagramm

Häufig wird zur Konstruktion des Huffman–Codes eine Baumstruktur verwendet. Für das bisher betrachtete Beispiel zeigt diese die folgende Grafik:

Baumdarstellung der Huffman–Codierung für das $\text{Beispiel 1}$

Man erkennt:

Bei jedem Schritt des Huffman–Algorithmus werden die beiden Zweige mit den jeweils kleinsten Wahrscheinlichkeiten zusammengefasst.
Der Knoten im ersten Schritt fasst die zwei Symbole $\rm E$ und $\rm F$ mit den aktuell kleinsten Wahrscheinlichkeiten zusammen. Dieser Knoten ist mit $p_{\rm E} + p_{\rm F} = 0.14$ beschriftet.
Der vom Symbol mit der kleineren Wahrscheinlichkeit $($hier $\rm F)$ zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig $($für $\rm E)$ rot.

Nach fünf Schritten ist man bei der Baumwurzel („Root”) mit der Gesamtwahrscheinlichkeit $1.00$ angelangt.

Verfolgt man nun den Verlauf von der Wurzel (in obiger Grafik mit gelber Füllung) zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen. Mit den Zuordnungen „rot” → 1 und „blau” → 0 ergibt sich beispielsweise von der Wurzel zu Symbol

$\rm A$: rot, rot → 11,
$\rm B$: blau, rot → 01,
$\rm C$: blau, blau → 00,
$\rm D$: rot, blau, blau → 100,
$\rm E$: rot, blau, rot, rot → 1011,
$\rm F$: rot, blau, rot, blau → 1010.

Die (einheitliche) Zuordnung „rot” → 0 und „blau” → 1 würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen.

$\text{Beispiel 3:}$ Die folgende Grafik zeigt die Huffman–Codierung von $49$ Symbolen $q_ν ∈ \{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$, $\rm E$, $\rm F$ $\}$ mit der im letzten Abschnitt hergeleiteten Zuordnung. Die binäre Codesymbolfolge weist die mittlere Codewortlänge $L_{\rm M}\hspace{0.05cm}' = 125/49 = 2.551$ auf. Die Farben dienen ausschließlich zur besseren Orientierung.

Beispielfolgen bei Huffman–Codierung

Aufgrund der kurzen Quellensymbolfolge $(N = 49)$ weichen die Auftrittshäufigkeiten $h_{\rm A}$, ... , $h_{\rm F}$ der simulierten Folgen signifikant von den vorgegebenen Wahrscheinlichkeiten $p_{\rm A}$, ... , $p_{\rm F}$ ab:

$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},\hspace{0.4cm}p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$

$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx 0.184 \hspace{0.05cm},\hspace{0.6cm}p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx 0.143 \hspace{0.05cm},$$

$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},\hspace{0.6cm}p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm}.$$

Damit ergibt sich ein etwas größerer Entropiewert:

$$H \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \,{\rm bit/Quellensymbol}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} H\hspace{0.05cm}' \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}h_{\mu}) = 2.451 \,{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Würde man den Huffman–Code mit diesen „neuen” Wahrscheinlichkeiten $h_{\rm A}$, ... , $h_{\rm F}$ bilden, so ergäben sich folgende Zuordnungen:

$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$11$\hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$100$\hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$00$\hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$101$\hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$010$\hspace{0.05cm},\hspace{0.2cm} \boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$011$\hspace{0.05cm}.$

Nun würden nur $\rm A$ und $\rm C$ mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit.

Die Codesymbolfolge hätte dann eine Länge von $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$ Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.
Die mittlere Codewortlänge wäre dann $L_{\rm M}\hspace{0.05cm}' = 122/49 ≈ 2.49 \ \rm bit/Quellensymbol$ anstelle von $L_{\rm M}\hspace{0.05cm}'≈ 2.55 \ \rm bit/Quellensymbol$.

$\text{Fazit:}$ Dieses Beispiel lässt sich wie folgt interpretieren:

Die Huffman–Codierung lebt von der (genauen) Kenntnis der Symbolwahrscheinlichkeiten. Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge $L_{\rm M}$ oft nur unwesentlich größer als die Quellenentropie $H$.
Insbesondere aber bei kleinen Dateien kann es zu Abweichungen zwischen den (erwarteten) Symbolwahrscheinlichkeiten $p_μ$ und den (tatsächlichen) Häufigkeiten $h_μ$ kommen. Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten $(h_μ)$ basiert.
In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden. Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann. Bei kleinen Dateien lohnt sich dieser Aufwand nicht.

Der Shannon–Fano–Algorithmus

1949 – also bereits drei Jahre vor David A. Huffman – haben Claude E. Shannon und Robert Fano einen ähnlichen, auf Entropiecodierung basierenden Algorithmus angegeben, nämlich:

Man ordne die Quellensymbole nach fallenden Auftrittswahrscheinlichkeiten (identisch mit Huffman).
Man teile die sortierten Zeichen in zwei möglichst gleichwahrscheinliche Gruppen ein.
Der ersten Gruppe wird das Binärsymbol 1 zugeordnet, der zweiten die 0 (oder umgekehrt).
Sind in einer Gruppe mehr als ein Zeichen, so ist auf diese der Algorithmus rekursiv anzuwenden.

$\text{Beispiel 4:}$ Wir gehen wie im Einführungsbeispiel für den Huffman–Algorithmus von $M = 6$ Symbolen und den folgenden Wahrscheinlichkeiten aus:

$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm}.$$

Dann lautet der Shannon–Fano–Algorithmus:

$\rm AB$ → 1x (Wahrscheinlichkeit 0.54), $\rm CDEF$ → 0x (Wahrscheinlichkeit 0.46),
$\underline{\rm A}$ → 11 (Wahrscheinlichkeit 0.30), $\underline{\rm B}$ ⇒ 10 (Wahrscheinlichkeit 0.24),
$\underline{\rm C}$ → 01 (Wahrscheinlichkeit 0.20), $\rm DEF$ → 00x, (Wahrscheinlichkeit 0.26),
$\underline{\rm D}$ → 001 (Wahrscheinlichkeit 0.12), $\rm EF$ → 000x (Wahrscheinlichkeit 0.14),
$\underline{\rm E}$ → 0001 (Wahrscheinlichkeit 0.10), $\underline{\rm F}$ → 0000 (Wahrscheinlichkeit 0.04).

Anmerkungen:

Ein „$\rm x$” weist wieder darauf hin, dass in nachfolgenden Codierschritten noch Bits hinzugefügt werden müssen.
Es ergibt sich hier zwar eine andere Zuordnung als bei der Huffman–Codierung, aber genau die gleiche mittlere Codewortlänge:

$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

Mit den Wahrscheinlichkeiten entsprechend dem $\text{Beispiel 4}$ führt der Shannon–Fano–Algorithmus zur gleichen mittleren Codewortlänge wie die Huffman–Codierung. Ebenso sind bei vielen (eigentlich: den meisten) anderen Wahrscheinlichkeitsprofilen Huffman und Shannon–Fano aus informationstheoretischer Sicht äquivalent.

Es gibt aber durchaus Fälle, bei denen sich beide Verfahren hinsichtlich der (mittleren) Codewortlänge unterscheiden, wie das folgende Beispiel zeigt.

$\text{Beispiel 2:}$ Wir betrachten $M = 5$ Symbole mit folgenden Wahrscheinlichkeiten:

$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} H = 2.19\,{\rm bit/Quellensymbol} \hspace{0.05cm}. $$

Baumstrukturen nach Shannon–Fano bzw. Huffman

Die Grafik zeigt die jeweiligen Codebäume für Shannon–Fano (links) bzw. Huffman (rechts). Die Ergebnisse lassen sich wie folgt zusammenfassen:

Der Shannon–Fano–Algorithmus führt zum Code $\rm A$ → 11, $\rm B$ → 10, $\rm C$ → 01, $\rm D$ → 001, $\rm E$ → 000 und damit zur mittleren Codewortlänge

$$L_{\rm M} = (0.38 + 0.18 + 0.16) \cdot 2 + (0.15 + 0.13) \cdot 3 = 2.28\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

Mit "Huffman" erhält man $\rm A$ → 1, $\rm B$ → 001, $\rm C$ → 010, $\rm D$ → 001, $\rm E$ → 000 und eine etwas kleinere mittlere Codewortlänge:

$$L_{\rm M} = 0.38 \cdot 1 + (1-0.38) \cdot 3 = 2.24\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $$

Es gibt keinen Satz von Wahrscheinlichkeiten, bei denen Shannon–Fano ein besseres Ergebnis liefert als der Huffman–Algorithmus, der stets den bestmöglichen Entropiecodierer bereitstellt.
Die Grafik zeigt zudem, dass die Algorithmen im Baumdiagramm in unterschiedlichen Richtungen vorgehen, nämlich einmal von der Wurzel zu den Einzelsymbolen (Shannon–Fano), zum anderen von den Einzelsymbolen zur Wurzel (Huffman).

Versuchsdurchführung

Wählen Sie zunächst die Aufgabennummer.
Eine Aufgabenbeschreibung wird angezeigt.
Alle Parameter sind angepasst.
Alle Grafiken (Baumdiagramm, Symbolfolgen) sind aktualisiert.
Ebenso die Ergebnisse $H, \ L_{\rm M}$ sowie $H\hspace{0.05cm}', \ L_{\rm M}\hspace{0.05cm}'$.
Musterlösung nach Drücken von "Hide solution".
Nummer "0": Gleiche Einstellung wie beim Programmstart.

(1) Wählen Sie die Quelle gemäß der Voreinstellung mit $M=8$ ⇒ Entropie $H=2.278$ (bit/Quellensymbol), Huffman-Codierung und "Herleitung".

Interpretieren Sie die Ergebnisse. Wie werden die Quellensymbole $\rm C$, $\rm D$ und $\rm E$ codiert? Wie groß ist die mittlere Codewortlänge $L_{\rm M}$?

Es ergibt sich folgende Zuordnung: $\rm C \ \to 1$, $\rm D \ \to 01100$, $\rm E \ \to 0010$. Die mittlere Codewortlänge ist $L_{\rm M}= 2.29$ (bit/Quellensymbol) $>H$.
Erklärung: Im Baumdiagramm kommt man von der "Root" (gelber Kreis) zum Symbol $\rm E$ über Blau – Blau – Rot – Blau. "Blau" steht für $0$ und "Rot" für $1$.

(2) Wie unterscheiden sich bei sonst gleichen Einstellungen die Ergebnisse für "Shannon–Fano"?

Hier ergibt sich eine andere Zuordnung: $\rm C \ \to 1$, $\rm D \ \to 01010$, $\rm E \ \to 0100$. Trotzdem ist die mittlere Codewortlänge wieder $L_{\rm M}= 2.29$.
Erklärung: Im Graphen kommt man von der "Root" $\rm CAFBGEHD$ zu $\rm E$ über Blau – Rot – Blau – Blau. "Blau" steht wieder für $0$ und "Rot" für $1$.

(3) Warum ist bei "Huffman" und "Shannon–Fano" trotz unterschiedlicher Zuordnung die mittlere Codewortlänge gleich?

In beiden Fällen wird $\rm C$ mit einem Bit codiert, $\rm A$ und $\rm F$ mit drei Bit, $\rm B$, $\rm E$ und $\rm G$ mit vier Bit sowie $\rm D$ und $\rm H$ mit fünf Bit. Daraus folgt:
$L_{\rm M}= p_{\rm C} \cdot 1 + \big [p_{\rm A} + p_{\rm F}\big] \cdot 3 + \big [p_{\rm B} + p_{\rm E}+ p_{\rm G}\big] \cdot 4 + \big [p_{\rm D} + p_{\rm H}\big] \cdot 5 = 0.52 \cdot 1 + 0.22 \cdot 3 + 0.19 \cdot 4 + 0.07 \cdot 5 = 2.29$ (bit/Quellensymbol)

(4) Wählen Sie "Voreinstellung" und "Huffman". Wie ändern sich die Ergebnisse für "Simulation über 10000 Symbole" $(H', \ L_{\rm M}\hspace{0.05cm}')$ gegenüber $(H, \ L_{\rm M})$ für $N \to \infty$?

Starten Sie jeweils zehn Simulationen. Welche Aussagen stimmen mit diesen Wahrscheinlichkeiten immer: $L_{\rm M}\hspace{0.05cm}' > L_{\rm M}$, $L_{\rm M}\hspace{0.05cm}' > H$, $L_{\rm M}\hspace{0.05cm}' > H'$?

Für die theoretischen Werte (also für $N \to \infty)$ gilt immer $L_{\rm M} \ge H$. Außerdem wird für jede einzelne Simulation gelten: $L_{\rm M}\hspace{0.05cm}' \ge H'$.
Da bei jeder einzelnen Simulation $H'$ größer, kleiner oder gleich $H$ sein kann, ist aber $L_{\rm M}\hspace{0.05cm}' < H$ durchaus möglich.

(5) Wählen Sie nun die "Quelle 3" $(M=4, \ p_{\rm A}= p_{\rm B}=p_{\rm C}= p_{\rm D}=0.25)$ und "Huffman". Interpretieren Sie die Ergebnisse. Was wäre bei "Shannon–Fano"?

Jedes Symbol wird durch zwei Bit dargestellt, so dass $L_{\rm M} = H = 2$ (bit/Quellensymbol) ist. Die Simulation liefert auch immer $L_{\rm M}\hspace{0.05cm}' = 2$, auch für $H' < 2$.
Gleiches gilt für "Shannon–Fano" trotz anderer Zuordnung: $\rm A \ \to 00$, $\rm B \ \to 01$, $\rm C \ \to 10$, $\rm D \ \to 11$ statt $\rm A \ \to 01$, $\rm B \ \to 00$, $\rm C \ \to 11$, $\rm D \ \to 10$.
Aber ganz klar ist: Quellencodierung macht bei redundanzfreier Quelle keinen Sinn, weder "Huffman" noch "Shannon–Fano".

(6) Wählen Sie die "Quelle 4" $(M=4, \ p_{\rm A}= 0.5, \ p_{\rm B}= 0.25, \ p_{\rm C}= p_{\rm D}=0.125)$. Warum gilt hier $L_{\rm M} = H = 1.75$ (bit/Quellensymbol)? Interpretation.

Sowohl bei "Huffman" als auch bei "Shannon–Fano" wird $\rm A$ mit einem Bit codiert, $\rm B$ mit zwei Bit sowie $\rm C$ und $\rm D$ mit drei Bit.
Daraus folgt: $L_{\rm M}= 0.5 \cdot 1 + 0.25 \cdot 2 + 2 \cdot 0.125 \cdot 3 = H = 1.75$ (bit/Quellensymbol). Es sind "günstige Wahrscheinlichkeiten" der Form $p = 2^{-k}$.
Ohne eine "Entropiecodierung" nach Huffman oder Shannon–Fano würden alle vier Symbole mit zwei Bit dargestellt: $L_{\rm M}= 2$ (bit/Quellensymbol).

(7) Wählen Sie nun "Shannon–Fano" und die "Quelle 2" $(M=3, \ p_{\rm A}= 0.34, \ p_{\rm B}= p_{\rm C} =0.33)$. Mit welchen Wahrscheinlichkeiten ergäbe sich $L_{\rm M} = H $?

Die Ternärquelle ist nahezu redundanzfrei: $H \approx \log_2 \ 3 \approx 1.585$. Mit $\rm A \ \to 0$, $\rm B \ \to 10$, $\rm C \ \to 11$ ist $L_{\rm M}= 1.66 > H$.
"Günstige Wahrscheinlichkeiten" wären zum Beispiel $p_{\rm A}= 0.5, \ p_{\rm B}= p_{\rm C}= 0.25$ wie bei "Quelle 1". Dann ist $L_{\rm M}= H = 1.5$ (bit/Quellensymbol).

(8) Wählen Sie "Huffman" und die "Quelle 5" $(M=6, \ p_{\rm A}= p_{\rm B}= 0.25, \ p_{\rm C} = p_{\rm D} = p_{\rm E} = p_{\rm F} =0.125)$. Sind dies "günstige Wahrscheinlichkeiten"?

$\rm JA$. Alle Wahrscheinlichkeiten sind $2^{-2}$ oder $2^{-3}$ ⇒ Symbole werden mit zwei oder drei Bit dargestellt ⇒ $L_{\rm M}= H = 2.5$ (bit/Quellensymbol).

(9) Wie unterscheiden sich demgegenüber die Ergebnisse für "Quelle 6" $(M=6, \ p_{\rm A}= 0.26, \ p_{\rm B}= 0.24, \ p_{\rm C} = p_{\rm D} = 0.13, \ p_{\rm E} = p_{\rm F} =0.12)$?

Bereits durch geringfügige Wahrscheinlichkeitsabweichungen ergeben sich ein anderer Baum und damit auch andere Symbolzuordnungen.
$\rm A$ und $\rm B$ werden mit zwei Bit codiert, die anderen mit drei Bit. $L_{\rm M}= \big [p_{\rm A} + p_{\rm B}\big] \cdot 2 + \big [p_{\rm C} + p_{\rm D}+ p_{\E}+ p_{\F}\big] \cdot 3 = 2.5$ (bit/Quellensymbol).
Die geänderten $p_{\rm A}$, ... verändern hier nicht die mittlere Codewortlänge, aber $H=2.499$ wird (geringfügig) kleiner ⇒ $L_{\rm M} > H$ (bit/Quellensymbol).

(10) Betrachten Sie die "Quelle 9" $(M=8, \ p_{\rm A}= 0.8, \ p_{\rm B}= p_{\rm C}= p_{\rm D}=0.02, \ p_{\rm E} = 0.01$, ... , $p_{\rm H} = 0.01)$ ⇒ $H = 0.741$ (bit/Quellensymbol). Interpretation.

Es ergibt sich mit $L_{\rm M} = 1.28$ ein sehr viel größerer Wert als $H = 0.741$ – sowohl für "Huffman" als auch für "Shannon–Fano".
Beide Verfahren sind also zur Quellenkomprimierung nicht geeignet, wenn eine Symbolwahrscheinlichkeit deutlich größer ist als 50%.

(11) Die Komprimierung der "Quelle 9" $(M=8, H = 2.481)$ mit "Huffman" ergibt $L_{\rm M} = 2.58$. Welches Ergebnis liefert "Shannon–Fano"? Interpretation.

Bei "Huffman" wird ein Symbol mit einem Bit codiert, zwei mit drei Bit, drei mit vier Bit und zwei mit fünf Bit ⇒ $L_{\rm M} = 2.58$ (bit/Quellensymbol).
Entsprechend gilt für "Shannon–Fano": zweimal zwei Bit, dreimal drei Bit, einmal vier Bit, zweimal fünf Bit ⇒ $L_{\rm M} = 2.61$ (bit/Quellensymbol).
$\rm Fazit$: "Huffman" ist die optimale Entropiecodierung. "Shannon–Fano" erreicht meist das gleiche Ergebnis. $\text{Aber nicht immer!}$

Zur Handhabung des Applets

Bildschirmabzug "Herleitung"

(A) Bildschirmauswahl: Herleitung / Simulation

(B) Auswahl zwischen 8 Nachrichtenquellen mit $M=3$ bis $M=8$

(C) Ausgewählte Wahrscheinlichkeiten

(D) Entropie und mittlere Codewortlänge (Theorie, $N \to \infty$)

(E) Auswahl des Kompressionsverfahrens: Huffman / Shannon-Fano

(F) Ergebnisse der Codewortzuweisung

(G) Entropie und mittlere Codewortlänge (Simulation über $N \to \infty$)

(H) Grafikfeld zur Herleitung des Codes gemäß Baumdiagramm

(I) Bereich für die Versuchsdurchführung: Aufgabenauswahl

(J) Bereich für die Versuchsdurchführung: Aufgabenstellung

(K) Bereich für die Versuchsdurchführung: Musterlösung

Bildschirmabzug "Simulation"

(L) Ausgabe der aktuellen Quellensymbolfolge

(M) Ausgabe der aktuellen Codesymbolfolge

(N) Neue Folgen simulieren

Über die Autoren

Dieses interaktive Applet wurde am Lehrstuhl für Nachrichtentechnik der Technischen Universität München konzipiert und realisiert.

Die erste Version wurde 2011 von Eugen Mehlmann im Rahmen seiner Bachelorarbeit mit "FlashMX–Actionscript" erstellt (Betreuer: Günter Söder).
2019 wurde das Programm von Xiaohan Liu im Rahmen einer Werkstudententätigkeit auf "HTML5" umgesetzt und neu gestaltet (Betreuer: Tasnád Kernetzky).

Die Umsetzung dieses Applets auf HTML 5 wurde durch Studienzuschüsse der Fakultät EI der TU München finanziell unterstützt. Wir bedanken uns.

Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster

Open Applet in a new tab

@@ Line 1: / Line 1: @@
-{{LntAppletLink|entropie}}
+{{LntAppletLink|shannon-huffman}}
 ==Programmbeschreibung==
 <br>
-Dieses Applet verdeutlicht die Quellencodierverfahren nach Shannon&ndash;Fano bzw. Huffman. Diese Verfahren komprimieren redundante wertdiskrete Quellen ohne Gedächtnis mit Stufenzahl &nbsp;$M$, dem Symbolvorrat &nbsp;$\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \} = \{ \rm A, \hspace{0.1cm} B, \hspace{0.1cm}\text{ ...}\}$ und den Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A} \hspace{0.05cm},\hspace{0.1cm} p_{\rm B} \hspace{0.05cm}, \hspace{0.05cm}\text{ ...}$&nbsp;.
+Dieses Applet verdeutlicht die Quellencodierverfahren nach Huffman bzw. Shannon&ndash;Fano. Diese Verfahren komprimieren redundante wertdiskrete Quellen ohne Gedächtnis mit Stufenzahl &nbsp;$M$, dem Symbolvorrat &nbsp;$\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \} = \{ \rm A, \hspace{0.1cm} B, \hspace{0.1cm}\text{ ...}\}$ und den Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A} \hspace{0.05cm},\hspace{0.1cm} p_{\rm B} \hspace{0.05cm}, \hspace{0.05cm}\text{ ...}$&nbsp;.
-Ziel der Quellencodierung ist, dass die mittlere Codewortlänge &nbsp;$L_{\rm M}$&nbsp; des binären Codes &ndash; darstellbar durch unterschiedlich lange Folgen von Nullen und Einsen  &ndash; möglichst nahe an die Quellenentropie
+Ziel der Quellencodierung und insbesondere der Klasse der Entropiecodierung &ndash; zu der "Huffman" und "Shannon&ndash;Fano" gehören &ndash; ist, dass die mittlere Codewortlänge &nbsp;$L_{\rm M}$&nbsp; des binären Codes &ndash; darstellbar durch unterschiedlich lange Folgen von Nullen und Einsen  &ndash; möglichst nahe an die Quellenentropie
-:$$H = \sum_{\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} {\rm Pr}(q_{\mu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\mu})} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})$$
+:$$H = \sum_{\mu = 1}^{M} \hspace{0.2cm} {\rm Pr}(q_{\mu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\mu})} = -\sum_{\mu = 1}^{M} \hspace{0.2cm}  {\rm Pr}(q_{\mu}) \cdot {\rm log_2}\hspace{0.1cm}{\rm Pr}(q_{\mu})\hspace{0.5cm}\big[\hspace{0.05cm}{\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Quellensymbol}\hspace{0.05cm}\big]$$
 heranreicht. Allgemein gilt &nbsp;$L_{\rm M} \ge H$, wobei das Gleichheitszeichen nicht für alle Symbolwahrscheinlichkeiten erreicht werden kann.
+Dargestellt werden jeweils
+* das Baumdiagramm zur Herleitung des jeweiligen Binärcodes, und
+* eine simulierte Quellensymbolfolge der Länge &nbsp;$N = 10000$&nbsp; (Entropie &nbsp;$H\hspace{0.05cm}' \approx H)$&nbsp; und die dazugehörige Codesymbolfolge der Länge &nbsp;$L_{\rm M}\hspace{0.05cm}' \hspace{-0.03cm}\cdot \hspace{-0.03cm} N$.
-soll den Begriff &bdquo;Entropie&rdquo; am Beispiel einer binären Nachrichtenquelle verdeutlichen. Die Quellensymbolfolge lautet somit &nbsp;$〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}〉$&nbsp; mit &nbsp;$q_i \in \{A, B\}$&nbsp; für &nbsp;$i \ge 1$. Betrachtet werden sowohl eine gedächtnisfreie Quelle als auch eine Markovquelle erster Ordnung (also mit Gedächtnis &bdquo;1&rdquo;), deren Entropien &nbsp;$H$&nbsp; jeweils in geschlossener Form angegeben werden können.
-Ebenso werden für die unendlich lange Quellensymbolfolge so genannte Entropienäherungen &nbsp;$H_1$, &nbsp;$H_2$, ... , &nbsp;$H_k$, ... in geschlossener Form angegeben, wobei
+Auf die Einheiten "$\rm bit/Quellensymbol$" für die Entropie und die mittlere Codewortlänge wird im Programm verzichtet.
-*sich &nbsp;$H_1$&nbsp; allein auf die Symbolwahrscheinlichkeiten bezieht (das heißt: &nbsp; Abhängigkeiten der Symbole innerhalb der Folge bleiben unberücksichtigt),
-* zur Berechnung von &nbsp;$H_2$&nbsp; die Folge in Zweiertupel aufgeteilt und deren Entropie angegeben wird, und schließlich
-* durch Erweiterung die Entropie &nbsp;$H_k$&nbsp; von &nbsp;$k$&ndash;Tupeln angebbar ist.
-Hierbei besteht für jede beliebige Nachrichtenquelle (mit oder ohne Gedächtnis) folgende Größenrealationen:
-:$$ H <\text{...} \le H_k <\text{...} \le H_3 \le H_2 \le H_1 \le H_0 = \log_2 \ 2 = 1\text{ bit/Symbol} \hspace{0.05cm}.$$
+==Theoretischer Hintergrund==
-$H_0$&nbsp; bezeichnet den ''Entscheidungsgehalt'' von binären Nachrichtenquellen. Die ''Entropie'' &nbsp;$H$&nbsp; der Quelle ergibt sich als der Grenzwert der &nbsp;$H_k$&nbsp; für &nbsp;$k \to \infty$.
+<br>
+===Der Huffman–Algorithmus===
-Implizit vorausgesetzt ist bei allen diesen analytisch angebbaren Größen die Folgenlänge &nbsp;$N \to \infty$. Die Entropie &nbsp;$H$&nbsp; lässt sich aber auch aus einer begrenzten Quellensymbolfolge &nbsp;$〈 q_1 \hspace{0.05cm}〉 =〈 q_1 , \hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{N}\hspace{0.05cm}〉$&nbsp; annähern, also auch dann, wenn die statistischen Eigenschaften der Binärquelle unbekannt sind. Die entsprechenden  Entropienäherungen werden hier mit &nbsp;$\hat H_1$, &nbsp;$\hat H_2$, ... , &nbsp;$\hat H_k$, ... bezeichnet.
+Wir setzen voraus, dass die Quellensymbole&nbsp; $q_\nu$&nbsp; einem Alphabet&nbsp; $\{q_μ\} = \{$ $\rm A$, $\rm B$ , $\rm C$ , ...$\}$&nbsp; mit dem Symbolumfang&nbsp; $M$&nbsp; entstammen und statistisch voneinander unabhängig seien. Beispielsweise gelte für den Symbolumfang&nbsp; $M = 8$:
-Auch hierauf wird in der folgenden Beschreibung eingegangen mit dem Fazit:
-*Die Näherung &nbsp;$\hat H_k$&nbsp; ist natürlich um so genauer, je größer die Folgenlänge  &nbsp;$N$&nbsp; ist.
-*Ist über die Quelle nichts weiter bekannt als die beispielhafte Folge, so ist der Rechenaufwand enorm.
-==Theoretischer Hintergrund==
+:$$\{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm}, \boldsymbol{\rm B}\hspace{0.05cm}, \boldsymbol{\rm C}\hspace{0.05cm}, \boldsymbol{\rm D}\hspace{0.05cm}, \boldsymbol{\rm E}\hspace{0.05cm}, \boldsymbol{\rm F}\hspace{0.05cm}, \boldsymbol{\rm G}\hspace{0.05cm}, \boldsymbol{\rm H}\hspace{0.05cm}
-<br>
+\}\hspace{0.05cm}.$$
-Die Entropie spielt in vielen naturwissenschaftlichen Fachgebieten eine große Rolle. Beschränken wir uns auf unser Fachgebiet der Statistik und der Informationstechnik, so ist die Entropie nach der Definition von &nbsp;[https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; unter anderem ein Maß für die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses, für die „Zufälligkeit” dieses Ereignisses und für den mittleren Informationsgehalt einer Zufallsgröße.
+[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]&nbsp; hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen zur Informationstheorie – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.
+Dieser&nbsp; ''Huffman–Algorithmus''&nbsp; soll ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt:&nbsp; Für die Codesymbole gelte stets&nbsp; $c_ν ∈ \{$'''0''', '''1'''$\}$. Hier ist die Vorgehensweise:
-===Entropie einer gedächtnislosen Binärquelle ===
-[[File:Inf_T_1_1_S4_vers2.png|frame|Binäre Entropiefunktion als Funktion von $p$|right]]
+# &nbsp; Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
-Wir setzen zunächst voraus, dass die Auftrittwahrscheinlichkeiten der beiden Symbole &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; unabhängig von den vorherigen Symbolen innerhalb der Folge gleich &nbsp;$p_{\rm A} = p$&nbsp; und &nbsp;$p_{\rm B} = 1 – p$&nbsp; seien.
+# &nbsp; Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
+# &nbsp; Man wiederhole&nbsp; '''(1)'''&nbsp; und&nbsp; '''(2)''', bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
+# &nbsp; Man codiert die wahrscheinlichere Symbolmenge mit&nbsp; '''1'''&nbsp; und die andere Menge mit&nbsp; '''0'''.
+# &nbsp; Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen gemäß den Wahrscheinlichkeiten mit&nbsp; '''1'''&nbsp; bzw.&nbsp; '''0'''.
-Für die Entropie dieser &bdquo;gedächtnislosen&rdquo; Binärquelle gilt:
-:$$H = H_{\rm bin} (p) =  p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p} \hspace{0.5cm}{\rm (Einheit\hspace{-0.15cm}: \hspace{0.15cm}bit\hspace{0.15cm}oder\hspace{0.15cm}bit/Symbol)}
+{{GraueBox|TEXT=
+$\text{Beispiel 1:}$&nbsp; Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die&nbsp; $M = 6$&nbsp; Symbole &nbsp;$\rm A$, ... , &nbsp;$\rm F$&nbsp;  schon nach ihren Wahrscheinlichkeiten geordnet sind:
+:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
+p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
 \hspace{0.05cm}.$$
-Man bezeichnet die Funktion &nbsp;$H_\text{bin}(p)$&nbsp; als die '''binäre Entropiefunktion'''. Aus der Grafik erkennt man:
+Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen <br>(resultierende Wahrscheinlichkeiten in Klammern):
-*Der Maximalwert &nbsp;$H_\text{0} = 1\; \rm  bit/Symbol$&nbsp; ergibt sich für &nbsp;$p = 0.5$, also für gleichwahrscheinliche Binärsymbole. Dann liefern &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; jeweils den gleichen Beitrag zur Entropie. &nbsp;$H_\text{0}$ nennt man auch den ''Entscheidungsgehalt''.
+:1. &nbsp; $\rm A$ (0.30), $\rm B$ (0.24), $\rm C$ (0.20), $\rm EF$ (0.14), $\rm D$ (0.12),
-* $H_\text{bin}(p)$&nbsp; ist symmetrisch um &nbsp;$p = 0.5$. Eine Quelle mit &nbsp;$p_{\rm A} = 0.1$&nbsp; und &nbsp;$p_{\rm B} = 0.9$&nbsp; hat die gleiche Entropie  &nbsp;$H = 0.469 \; \rm   bit/Symbol$&nbsp; wie eine Quelle mit &nbsp;$p_{\rm A} = 0.9$&nbsp; und &nbsp;$p_{\rm B} = 0.1$.
+:2. &nbsp; $\rm A$ (0.30), $\rm EFD$ (0.26), $\rm B$ (0.24), $\rm C$ (0.20),
-*Die Differenz &nbsp;$ΔH = H_\text{0} - H$&nbsp; gibt die ''Redundanz'' der Quelle an und &nbsp;$r = ΔH/H_\text{0}$&nbsp; die ''relative Redundanz''. Im Beispiel ergeben sich &nbsp;$ΔH = 0.531\; \rm  bit/Symbol$&nbsp; bzw. &nbsp;$r = 53.1 \rm \%$.
+:3. &nbsp; $\rm BC$ (0.44), $\rm A$ (0.30), $\rm EFD$ (0.26),
-*Für &nbsp;$p = 0$&nbsp; ergibt sich &nbsp;$H = 0$, da hier die Symbolfolge &nbsp;$\rm B \ B \ B \text{...}$&nbsp; mit Sicherheit vorhergesagt werden kann. Eigentlich ist nun der Symbolumfang nur noch &nbsp;$M = 1$. Gleiches gilt für &nbsp;$p = 1$, also für die Symbolfolge &nbsp;$\rm A  A A \text{...}$&nbsp;
+:4. &nbsp; $\rm AEFD$ (0.56), $\rm BC$ (0.44),
+:5. &nbsp; Root $\rm AEFDBC$ (1.00).
+Rückwärts &ndash; alsogemäß den Schritten&nbsp; '''(5)'''&nbsp; bis&nbsp; '''(1)'''&nbsp; &ndash; erfolgt dann die Zuordnung zu Binärsymbolen. Ein&nbsp; '''x'''&nbsp; weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen:
+:5. &nbsp; $\rm AEFD$ → '''1x''', &nbsp; &nbsp;  $\rm BC$ → '''0x''',
+:4. &nbsp; $\underline{\rm A}$  → '''<u>11</u>''', &nbsp; &nbsp;  $\rm EFD$ → '''10x''',
+:3. &nbsp; $\underline{\rm B}$ → '''<u>01</u>''', &nbsp; &nbsp; $\underline{\rm C}$ → '''<u>00</u>''',
+:2. &nbsp; $\rm EF$ → '''101x''',  &nbsp; &nbsp; $\underline{\rm D}$ → '''<u>100</u>''',
+:1. &nbsp; $\underline{\rm E}$ → '''<u>1011</u>''',  &nbsp; &nbsp; $\underline{\rm F}$ → '''<u>1010</u>'''.
+Die Unterstreichungen markieren die endgültige Binärcodierung.}}
+===Zum Begriff „Entropiecodierung”===
+Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:
+:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
+p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
+\hspace{0.05cm};$$
-===Entropie hinsichtlich Zweiertupel===
+:$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$
-[[File:Inf_tupel.png|frame|Zur Verdeutlichung der Zweiertupel &nbsp;$\rm AA$, &nbsp;$\rm AB$, &nbsp;$\rm BA$, &nbsp;$\rm BB$|right]]
+Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole &nbsp;$(\rm E$ und $\rm F)$&nbsp; mit vier Bit codiert.
-Wir teilen nun die Quellensymbolfolge $〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}〉$ in Zweiertupel entsprechend der Grafik auf und betrachten dadurch die Entropie zweier aufeinanderfolgender Quellensymbole.
-Die Binärquelle wird weiterhin wie im letzten Abschnitt als ''gedächtnislos'' bzw. ''redundanzfrei'' vorausgesetzt. Für die Kombination  $(q_ν, \hspace{0.05cm}q_{ν+1})$ gibt es in diesem Fall &nbsp;$2^2 = 4$&nbsp; mögliche Symbolpaare (farblich markiert) mit folgenden &nbsp;[[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Verbundwahrscheinlichkeiten]]:
+Die mittlere Codewortlänge ergibt sich damit zu
-:$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1})
+:$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2  + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/Quellensymbol}
- \hspace{0.05cm}.$$
+\hspace{0.05cm}.$$
-Daraus ist die ''Verbundentropie'' eines Zweier–Tupels berechenbar (der Index &bdquo;2&rdquo; symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht):
+Aus dem Vergleich mit der Quellenentropie
+:$$H = -\big [0.3 \cdot {\rm log_2}\hspace{0.1cm}(0.3) + 0.24 \cdot {\rm log_2}\hspace{0.1cm}(0.24)
-:$$H_2\hspace{0.05cm}' = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} \sum_{q_{\nu+1}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm} q_{\mu}\hspace{0.01cm} \}}\hspace{-0.1cm}{\rm Pr}(q_{\nu}\cap q_{\nu+1}) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu}\cap q_{\nu+1})} \hspace{0.4cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Zweiertupel})
++ 0.2 \cdot {\rm log_2}\hspace{0.1cm}(0.2)+ 0.12 \cdot {\rm log_2}\hspace{0.1cm}(0.12)
- \hspace{0.05cm}.$$
++ 0.1 \cdot {\rm log_2}\hspace{0.1cm}(0.1)+ 0.04 \cdot {\rm log_2}\hspace{0.1cm}(0.04)
+\big ]= 2.365 \ \rm bit/Quellensymbol$$
-Um den mittleren Informationsgehalt pro Symbol zu erhalten, muss &nbsp;$H_2\hspace{0.05cm}'$&nbsp; noch halbiert werden:
+erkennt man die Effizienz der Huffman–Codierung.
-:$$H_2 = {H_2\hspace{0.05cm}'}/{2}  \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
- \hspace{0.05cm}.$$
-Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die im letzten Abschnitt definierte Entropie mit &nbsp;$H_1$:
-:$$H_1 = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu})} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
- \hspace{0.05cm}.$$
-Der Index &bdquo;1&rdquo; soll darauf hinweisen, dass &nbsp;$H_1$&nbsp; ausschließlich die Symbolwahrscheinlichkeiten berücksichtigt und nicht statistischen Bindungen zwischen Symbolen innerhalb der Folge. Mit dem Entscheidungsgehalt &nbsp;$H_0 = \log_2 2 = 1\text{ (bit)}$&nbsp; ergibt sich dann folgende Größenbeziehung:
+{{GraueBox|TEXT=
+$\text{Beispiel 2:}$&nbsp; Wären die Symbolwahrscheinlichkeiten
-:$$H_0 \ge H_1 \ge H_2
+:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm}
- \hspace{0.05cm}.$$
+p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16
+\hspace{0.05cm},$$
-Verdeutlichen wir uns nun die Berechnung der Entropienäherungen &nbsp;$H_1$&nbsp; und &nbsp;$H_2$&nbsp; an zwei Beispielen.
-{{GraueBox|TEXT=
+so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:
-$\text{Beispiel 1:}$&nbsp; Wir betrachten zunächst eine ''gedächtnislose Binärquelle'' mit gleichwahrscheinlichen Symbolen, das heißt es gelte &nbsp;$p_{\rm A} = p_{\rm B} = 1/2$. Die ersten zwanzig Folgenelemente lauten: &nbsp; $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABAB$ ...
-*Aufgrund der gleichwahrscheinlichen Binärsymbole ist &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
-*Die Verbundwahrscheinlichkeit &nbsp;$p_{\rm AB}$&nbsp; der Kombination &nbsp;$\rm AB$&nbsp; ist gleich &nbsp;$p_{\rm A} · p_{\rm B} = 1/4$. Ebenso gilt &nbsp;$p_{\rm AA} = p_{\rm BB} = p_{\rm BA} = 1/4$.
-*Damit erhält man für die zweite Entropienäherung
-:$$H_2 = {1}/{2} \cdot \big [ {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +  {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 \big ] = 1 \,{\rm bit/Symbol} = H_1 = H_0
+:$$H =   3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4)  + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
- \hspace{0.05cm}.$$}}
+:$$L_{\rm M}  =  3 \cdot 1/4 \cdot 2  + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/Quellensymbol}
+\hspace{0.05cm}.$$}}
-{{GraueBox|TEXT=
-$\text{Beispiel 2:}$&nbsp; Die zweite hier betrachtete Folge ergibt sich aus  der Folge von $\text{Beispiel 1}$ durch Anwendung eines einfachen Wiederholungscodes:
-:$$〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb \text{...} $$
-*Die wiederholten Symbole sind durch entsprechende Kleinbuchstaben dargestellt. Bitte beachten Sie: &nbsp; Es handelt sich trotzdem um eine Binärquelle.
-*Aufgrund der gleichwahrscheinlichen Binärsymbole ergibt sich auch hier  &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
-*Für die Verbundwahrscheinlichkeiten gilt nun &nbsp;$p_{\rm AA}=p_{\rm BB} = 3/8$&nbsp; und &nbsp;$p_{\rm ABA}=p_{\rm BAB} = 1/8$. Daraus folgt:
-:$$\begin{align*}H_2 ={1}/{2} \cdot \big [ 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm} {8}/{3} +
-\cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8\big ] = {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 - {3}/{8} \cdot{\rm log}_2\hspace{0.1cm}3 +   {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 \approx 0.906 \,{\rm bit/Symbol} < H_1 = H_0
- \hspace{0.05cm}.\end{align*}$$
-Betrachtet man sich die Aufgabenstellung genauer, so kommt man zu folgendem Schluss:
-*Die Entropie müsste eigentlich &nbsp;$H = 0.5 \hspace{0.05cm} \rm bit/Symbol$&nbsp; sein (jedes zweite Symbol liefert keine neue Information).
-*Die zweite Entropienäherung &nbsp;$H_2 = 0.906 \hspace{0.05cm} \rm bit/Symbol$&nbsp; ist aber deutlich größer als die Entropie &nbsp;$H$.
-*Zur Entropiebestimmung dieser redundanten Symbolfolge reicht also die Näherung zweiter Ordnung nicht aus.
-*Vielmehr muss man größere zusammenhängende Blöcke mit &nbsp;$k > 2$&nbsp; Symbolen betrachten. Einen solchen Block bezeichnen wir im Folgenden als $k$–Tupel.}}
+Aus dieser Eigenschaft&nbsp; $L_{\rm M} = H +\varepsilon$&nbsp; mit&nbsp; $\varepsilon = 0$&nbsp; bei geeigneten Auftrittswahrscheinlichkeiten erklärt sich der Begriff '''Entropiecodierung''':
+::Man versucht bei dieser Form von Quellencodierung, die Länge&nbsp; $L_μ$&nbsp; der Binärfolge (bestehend aus Nullen und Einsen) für das Symbol&nbsp; $q_μ$&nbsp; gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit&nbsp; $p_μ$&nbsp; anzupassen:
-===Verallgemeinerung auf $k$–Tupel und Grenzübergang ===
-Wir schreiben zur Abkürzung mit der Verbundwahrscheinlichkeit &nbsp;$p_i^{(k)}$&nbsp; eines $k$–Tupels allgemein:
-:$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{M^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{p_i^{(k)}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
+::$$L_{\mu} =  {\rm log}_2\hspace{0.1cm}(1/p_{\mu} )  \hspace{0.05cm}.$$
-  \hspace{0.05cm}.$$
-*Die Laufvariable &nbsp;$i$&nbsp; steht jeweils für eines der &nbsp;$M^k$ Tupel. Bei den hier betrachteten Binärquellen gilt &nbsp;$M=2$.
+Da $L_μ$ im Gegensatz zu $\log_2(1/ p_μ$) ganzzahlig ist, gelingt dies nicht immer.
-*Die vorher berechnete Näherung &nbsp;$H_2$&nbsp; ergibt sich mit &nbsp;$k = 2$.
-*Für die Entropienäherungen &nbsp;$H_k$&nbsp; gelten folgende Größenrelationen; $H_0 = 1\text{ (bit/Symbol)}$ ist wieder der Entscheidungsgehalt:
-:$$H \le \text{...} \le H_k \le \text{...} \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$
-*Die '''Entropie einer Nachrichtenquelle mit Gedächtnis''' ist der folgende Grenzwert:
-:$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$
-Der Rechenaufwand wird bis auf wenige Sonderfälle $($siehe nachfolgendes $\text{Beispiel 3)}$ mit zunehmendem &nbsp;$k$&nbsp; immer größer:
+Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten&nbsp; $p_μ$&nbsp; in der Form&nbsp; $2^{–k}$&nbsp; mit&nbsp; $k = 1, 2, 3,$ ...  dargestellt werden können.
-*Zur Berechnung von &nbsp;$H_{10}$&nbsp; einer Binärquelle ist über &nbsp;$2^{10} = 1024$&nbsp; Terme zu mitteln.
+*In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; exakt mit der Quellenentropie&nbsp; $H$&nbsp; überein &nbsp;$(\varepsilon = 0$, siehe&nbsp; $\text{Beispiel 2}$).
-*Mit jeder weiteren Erhöhung von &nbsp;$k$&nbsp; um &nbsp;$1$&nbsp; verdoppelt sich die Anzahl der Summenterme.
+*Nach dem [[Information_Theory/Allgemeine_Beschreibung#Quellencodierungstheorem|Quellencodierungstheorem]] gibt es keinen (decodierbaren) Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt.
-{{GraueBox|TEXT=
+{{BlaueBox|TEXT=
-$\text{Beispiel 3:}$&nbsp;
+$\text{Merke:}$&nbsp;
-Wir betrachten eine alternierende Binärfolge &nbsp; ⇒ &nbsp; $〈 q_ν 〉 =\rm ABABABAB$ ... &nbsp; . Entsprechend gilt &nbsp;$H_0 = H_1 = 1 \hspace{0.15cm} \rm bit/Symbol$.
+Es gibt keinen präfixfreien (⇒ sofort decodierbaren) Code, der allein unter Ausnutzung der Auftrittswahrscheinlichkeiten zu einer kleineren mittleren Codewortlänge&nbsp; $L_{\rm M}$&nbsp; führt als der Huffman–Code. &nbsp; '''In diesem Sinne ist der Huffman–Code optimal'''.}}
-In diesem Sonderfall muss zur Bestimmung der &nbsp;$H_k$–Näherung unabhängig von &nbsp;$k$&nbsp; stets nur über zwei Verbundwahrscheinlichkeiten gemittelt werden:
-* $k = 2$: &nbsp;&nbsp;   $p_{\rm AB} = p_{\rm BA} = 1/2$     &nbsp; &nbsp;       ⇒ &nbsp; &nbsp;  $H_2 =  1/2 \hspace{0.15cm} \rm bit/Symbol$,
+===Darstellung des Huffman–Codes als Baumdiagramm===
-* $k = 3$:  &nbsp;&nbsp;   $p_{\rm ABA} = p_{\rm BAB} = 1/2$    &nbsp; &nbsp;    ⇒  &nbsp; &nbsp; $H_3 =  1/3 \hspace{0.15cm} \rm bit/Symbol$,
+Häufig wird zur Konstruktion des Huffman–Codes eine&nbsp; '''Baumstruktur'''&nbsp; verwendet. Für das bisher betrachtete Beispiel zeigt diese die folgende Grafik:
-* $k = 4$:  &nbsp;&nbsp;  $p_{\rm ABAB} = p_{\rm BABA} = 1/2$  &nbsp; &nbsp; ⇒  &nbsp; &nbsp; $H_4 =  1/4 \hspace{0.15cm} \rm bit/Symbol$.
+[[File:P_ID2418__Inf_T_2_3_S3_neu.png|frame|Baumdarstellung  der Huffman–Codierung für das&nbsp; $\text{Beispiel 1}$]]
-Die (tatsächliche) Entropie dieser alternierenden Binärfolge ist demzufolge
+Man erkennt:
-:$$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$$
+*Bei jedem Schritt des Huffman–Algorithmus werden die beiden Zweige mit den jeweils kleinsten Wahrscheinlichkeiten zusammengefasst.
+*Der Knoten im ersten Schritt fasst die zwei Symbole&nbsp; $\rm E$&nbsp; und&nbsp; $\rm F$&nbsp; mit den aktuell kleinsten Wahrscheinlichkeiten zusammen. Dieser Knoten ist mit&nbsp; $p_{\rm E} + p_{\rm F} = 0.14$&nbsp; beschriftet.
+*Der vom Symbol mit der kleineren Wahrscheinlichkeit &nbsp;$($hier $\rm F)$&nbsp; zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  &nbsp;$($für $\rm E)$&nbsp; rot.
-Dieses Ergebnis war zu erwarten, da die betrachtete Folge nur minimale Information besitzt, die sich allerdings im Entropie–Endwert &nbsp;$H$&nbsp; nicht auswirkt, nämlich die Information:  &nbsp; „Tritt $\rm A$ zu den geraden oder ungeraden Zeitpunkten auf?”
-Man erkennt, dass &nbsp;$H_k$&nbsp; dem Endwert &nbsp;$H = 0$&nbsp; nur sehr langsam näher kommt: &nbsp; Die zwanzigste Entropienäherung  liefert immer noch &nbsp;$H_{20} = 0.05 \hspace{0.15cm} \rm bit/Symbol$. }}
+Nach fünf Schritten ist man bei der Baumwurzel („Root”) mit der Gesamtwahrscheinlichkeit&nbsp; $1.00$&nbsp; angelangt.
+Verfolgt man nun den Verlauf von der Wurzel (in obiger Grafik mit gelber Füllung) zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen. Mit den Zuordnungen „rot” &nbsp; → &nbsp; '''1''' und „blau” &nbsp; → &nbsp; '''0''' ergibt sich beispielsweise von der Wurzel zu Symbol
+* $\rm A$:  &nbsp;  rot, rot  →  '''11''',
+*$\rm B$:   &nbsp; blau, rot  →  '''01''',
+*$\rm C$:   &nbsp; blau, blau  →  '''00''',
+*$\rm D$:   &nbsp; rot, blau, blau  →  '''100''',
+*$\rm E$:   &nbsp; rot, blau, rot, rot  →  '''1011''',
+*$\rm F$:   &nbsp; rot, blau, rot, blau  →  '''1010'''.
+Die (einheitliche) Zuordnung „rot” &nbsp; → &nbsp; '''0''' und „blau” &nbsp; → &nbsp; '''1''' würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen.
+{{GraueBox|TEXT=
+$\text{Beispiel 3:}$&nbsp;
+Die folgende Grafik zeigt die Huffman–Codierung von &nbsp;$49$&nbsp; Symbolen&nbsp; $q_ν ∈ \{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$, $\rm E$, $\rm F$ $\}$&nbsp; mit der im letzten Abschnitt hergeleiteten Zuordnung. Die binäre Codesymbolfolge weist die mittlere Codewortlänge $L_{\rm M}\hspace{0.05cm}' = 125/49 = 2.551$ auf. Die Farben dienen ausschließlich zur besseren Orientierung.
+[[File:Inf_T_2_3_S3b_version2.png|center|frame|Beispielfolgen bei Huffman–Codierung]]
+Aufgrund der kurzen Quellensymbolfolge&nbsp; $(N = 49)$&nbsp; weichen die Auftrittshäufigkeiten&nbsp; $h_{\rm A}$, ... , $h_{\rm F}$&nbsp; der simulierten Folgen signifikant von den vorgegebenen Wahrscheinlichkeiten&nbsp; $p_{\rm A}$, ... , $p_{\rm F}$&nbsp; ab:
+:$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},\hspace{0.4cm}p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$
+:$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx  0.184 \hspace{0.05cm},\hspace{0.6cm}p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx  0.143 \hspace{0.05cm},$$
-===Binärquellen mit Markoveigenschaften  ===
+:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},\hspace{0.6cm}p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102
+\hspace{0.05cm}.$$
-[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]
+Damit ergibt sich ein etwas größerer Entropiewert:
-Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch [[Stochastische_Signaltheorie/Markovketten|Markovprozesse]] modelliert, wobei wir uns hier auf binäre Markovprozesse erster Ordnung mit den Zuständen (Symbolen) &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; beschränken.
+:$$H \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \,{\rm bit/Quellensymbol}\hspace{0.3cm}
+\Rightarrow \hspace{0.3cm}
-Rechts  sehen Sie das Übergangsdiagramm für einen binären Markovprozess erster Ordnung. Von den vier angegebenen Übertragungswahrscheinlichkeiten sind allerdings nur zwei frei wählbar, zum Beispiel
+H\hspace{0.05cm}' \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}h_{\mu}) = 2.451 \,{\rm bit/Quellensymbol}
-* $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$ &nbsp;  ⇒  &nbsp; bedingte Wahrscheinlichkeit, dass &nbsp;$\rm A$&nbsp; auf &nbsp;$\rm B$&nbsp; folgt.
+\hspace{0.05cm}.$$
-* $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = \rm Pr(B\hspace{0.01cm}|\hspace{0.01cm}A)$   &nbsp;  ⇒  &nbsp;   bedingte Wahrscheinlichkeit, dass &nbsp;$\rm B$&nbsp; auf &nbsp;$\rm A$&nbsp; folgt.
+Würde man den Huffman–Code mit diesen „neuen” Wahrscheinlichkeiten&nbsp; $h_{\rm A}$, ... , $h_{\rm F}$&nbsp; bilden, so ergäben sich folgende Zuordnungen:
-Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann &nbsp;$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$ &nbsp;und &nbsp; $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
- \hspace{0.05cm}.$
-Aufgrund der vorausgesetzten Eigenschaften [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Station.C3.A4re_Zufallsprozesse|Stationarität]] und [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Ergodische_Zufallsprozesse|Ergodizität]] gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:
-:$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
+:&nbsp; &nbsp; &nbsp;$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''11'''$\hspace{0.05cm},\hspace{0.2cm}
- \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
+\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}
- \hspace{0.05cm}.$$
+\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''00'''$\hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''101'''$\hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''010'''$\hspace{0.05cm},\hspace{0.2cm}
+\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''011'''$\hspace{0.05cm}.$
-Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:
+Nun würden nur&nbsp; $\rm A$&nbsp; und&nbsp; $\rm C$&nbsp; mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit.
-* Für &nbsp;$p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$&nbsp; sind die Symbole gleichwahrscheinlich &nbsp; ⇒ &nbsp; $p_{\text{A}} = p_{\text{B}}= 0.5$. Die erste Entropienäherung liefert demzufolge  &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm  bit/Symbol$, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten &nbsp;$p_{\text{A|B}}$ &nbsp;bzw.&nbsp; $p_{\text{B|A}}$.
+*Die Codesymbolfolge hätte dann eine Länge von&nbsp; $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$&nbsp; Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.
-*Die Quellenentropie &nbsp;$H$&nbsp; als der Grenzwert $($für &nbsp;$k \to \infty)$&nbsp; der [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Verallgemeinerung_auf_.7F.27.22.60UNIQ-MathJax108-QINU.60.22.27.7F.E2.80.93Tupel_und_Grenz.C3.BCbergang|Entropienäherung $k$–ter Ordnung]] &nbsp; &rArr; &nbsp; $H_k$&nbsp;   hängt aber sehr wohl von den tatsächlichen Werten von &nbsp;$p_{\text{A|B}}$ &nbsp;und&nbsp; $p_{\text{B|A}}$&nbsp; ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.
+*Die mittlere Codewortlänge wäre dann $L_{\rm M}\hspace{0.05cm}' = 122/49 ≈ 2.49 \ \rm  bit/Quellensymbol$ anstelle von $L_{\rm M}\hspace{0.05cm}'≈ 2.55 \ \rm  bit/Quellensymbol$.}}
-{{GraueBox|TEXT=
+{{BlaueBox|TEXT=
-$\text{Beispiel 4:}$&nbsp;
+$\text{Fazit:}$&nbsp;
-Wir betrachten drei Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$&nbsp; unterscheiden.
+Dieses Beispiel lässt sich wie folgt interpretieren:
-*Für die  Symbolwahrscheinlichkeiten gilt somit  &nbsp;$p_{\rm A} = p_{\rm B}= 0.5$.
+*Die Huffman–Codierung lebt von der (genauen) Kenntnis der Symbolwahrscheinlichkeiten. Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; oft nur unwesentlich größer als die Quellenentropie&nbsp; $H$.
-*Die  anderen Übergangswahrscheinlichkeiten haben dann die Werte &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =
+*Insbesondere aber bei kleinen Dateien kann es zu Abweichungen zwischen den (erwarteten) Symbolwahrscheinlichkeiten&nbsp; $p_μ$&nbsp; und den (tatsächlichen) Häufigkeiten&nbsp; $h_μ$&nbsp; kommen. Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten&nbsp; $(h_μ)$&nbsp; basiert.
-p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}B} }.$
+*In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden. Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann. Bei kleinen Dateien lohnt sich dieser Aufwand nicht.}}
-[[File:P_ID2242__Inf_T_1_2_S5b_neu.png|center|frame|Drei Beispiele binärer Markovquellen]]
-*Die mittlere (blaue) Symbolfolge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.5$&nbsp; besitzt die Entropie &nbsp;$H ≈ 1 \hspace{0.05cm}  \rm bit/Symbol$. Das heißt: &nbsp; In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge.
-*Die linke (rote) Folge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$&nbsp; weist weniger Wechsel zwischen &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun  &nbsp;$H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$&nbsp; kleiner.
-*Die rechte (grüne) Symbolfolge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$&nbsp; hat die genau gleiche Entropie &nbsp;$H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$&nbsp; wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... $\rm ABABAB$ ... ).}}
-Für den allgemeineren Fall &nbsp;$p_{\text{A}} \ne p_{\text{B}}$&nbsp; ist die  Entropieberechnung der Zweiertupel etwas komplizierter:
-*Mit den  Verbundwahrscheinlichkeiten, zum Beispiel &nbsp;$p_{\text{AB}} = p_{\text{A}} · p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$, kann geschrieben werden:
-:$$H_2\hspace{0.05cm}' = p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{  p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot  p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot  p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
- \hspace{0.05cm}.$$
-*Ersetzt man nun die Logarithmen der Produkte durch entsprechende Summen von Logarithmen, so erhält man das Ergebnis &nbsp;$H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$&nbsp; mit
+===Der Shannon&ndash;Fano–Algorithmus ===
-:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
- \hspace{0.05cm},$$
-:$$H_{\rm M}= p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
- \hspace{0.05cm}.$$
-*Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):
+&ndash; also bereits drei Jahre vor David A. Huffman &ndash; haben&nbsp; [https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; und &nbsp;[https://de.wikipedia.org/wiki/Robert_Fano Robert Fano]&nbsp; einen ähnlichen, auf ''Entropiecodierung'' basierenden Algorithmus angegeben, nämlich:
-:$$H_2 =  {1}/{2} \cdot {H_2\hspace{0.05cm}'} = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big]
+:# &nbsp; Man ordne die Quellensymbole nach fallenden Auftrittswahrscheinlichkeiten (identisch mit Huffman).
- \hspace{0.05cm}.$$
+:# &nbsp; Man teile die sortierten Zeichen in zwei möglichst gleichwahrscheinliche Gruppen ein.
+:# &nbsp; Der ersten Gruppe wird das Binärsymbol &nbsp;'''1'''&nbsp; zugeordnet, der zweiten die&nbsp; '''0'''&nbsp; (oder umgekehrt).
+:# &nbsp; Sind in einer Gruppe mehr als ein Zeichen, so ist auf diese der Algorithmus rekursiv anzuwenden.
-*Erweitert man dieses Ergebnis für &nbsp;$H_2$&nbsp; auf die $k$–te Entropienäherung, so erhält man:
+{{GraueBox|TEXT=
+$\text{Beispiel 4:}$&nbsp; Wir gehen wie im&nbsp; [https://en.lntwww.de/Applets:Huffman-_und_Shannon-Fano-Codierung#Der_Huffman.E2.80.93Algorithmus Einführungsbeispiel]&nbsp; für den Huffman–Algorithmus von $M = 6$ Symbolen und den folgenden Wahrscheinlichkeiten aus:
-:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ].$$
+:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
+p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
-*Die '''Entropie einer Markovquelle''' ergibt sich als der folgende Grenzwert und ist demzufolge einfach zu berechnen:
-:$$H = \lim_{k \rightarrow \infty }H_k  \hspace{0.5cm}\Rightarrow \hspace{0.5cm} H = H_{\rm M} = 2 \cdot  H_2 - H_1 \hspace{0.05cm}.$$
-== Zusammenfassung und Schlussfolgerungen ==
-<br>
-=== Unbekannte Binärquelle ===
-* Ist von der Nachrichtenquelle nicht mehr bekannt als der Symbolunfang &nbsp;$M=2$, so müssen die Entropienäherungen &nbsp;$\hat H_k$&nbsp; numerisch aus der Quellensymbolfolge &nbsp;$〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...}\hspace{0.05cm},\hspace{0.05cm}q_{N} \hspace{0.05cm}〉$&nbsp; ermittelt werden. Die Entropie &nbsp;$H$&nbsp;ergibt sich als der Grenzwert der &nbsp;$\hat H_k$&nbsp; für &nbsp;$k \to \infty$, wobei gilt:
-:$$ H <\text{...} <\hat  H_k <\text{...} < \hat H_3 < \hat H_2 < \hat H_1 \le H_0  \hspace{0.05cm}.$$
-*  Bei der numerischen Ermittlung werden alle Wahrscheinlichkeiten &nbsp;$(p_{\rm A}, \text{...})$&nbsp; und bedingten Wahrscheinlichkeiten &nbsp;$(p_{\rm A|B}, \text{...})$&nbsp; durch entsprechende relative Häufigkeiten &nbsp;$(h_{\rm A}, \text{...})$&nbsp; und bedingte Wahrscheinlichkeiten &nbsp;$(h_{\rm A|B}, \text{...})$&nbsp; angenähert.
-* Die Genauigkeit der numerischen Ermittlung nimmt bei gleichem &nbsp;$N$&nbsp; mit steigendem &nbsp;$k$&nbsp; ab. Das heißt: &nbsp; Die Folgenlänge &nbsp;$N$&nbsp; der Simulation muss an den größten &nbsp;$k$&ndash;Wert angepasst werden.
-=== Gedächtnislose Binärquelle ===
-* Eine gedächtnislose Binärquelle ist vollständig durch die Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A}$&nbsp; und &nbsp;$p_{\rm B} = 1- p_{\rm A}$&nbsp; charakterisiert. Für die Entropie gilt folgende Gleichung:
-:$$H = p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p} \hspace{0.5cm}{\rm (Einheit\hspace{-0.15cm}: \hspace{0.15cm}bit\hspace{0.15cm}oder\hspace{0.15cm}bit/Symbol)}
 \hspace{0.05cm}.$$
-* Der Maximalwert der Entropie ergibt sich für &nbsp;$p_{\rm A}= p_{\rm B} =0.5$; &nbsp;$H_0 = \log_2 \ M$&nbsp; bezeichnet man als den ''Entscheidungsgehalt'' der Quelle. Im binären Fall &nbsp;$(M = 2)$&nbsp; gilt:
+Dann lautet der Shannon–Fano–Algorithmus:
+:# &nbsp; $\rm AB$ → '''1'''x (Wahrscheinlichkeit 0.54), &nbsp; $\rm CDEF$ → '''0'''x (Wahrscheinlichkeit 0.46),
+:# &nbsp; $\underline{\rm A}$ → '''<u>11</u>''' (Wahrscheinlichkeit 0.30),  &nbsp;  $\underline{\rm B}$ ⇒ '''<u>10</u>''' (Wahrscheinlichkeit 0.24),
+:# &nbsp; $\underline{\rm C}$ → '''<u>01</u>''' (Wahrscheinlichkeit 0.20), &nbsp;   $\rm DEF$ → '''00'''x, (Wahrscheinlichkeit 0.26),
+:# &nbsp; $\underline{\rm D}$ → '''<u>001</u>''' (Wahrscheinlichkeit 0.12),  &nbsp;  $\rm EF$ → '''000'''x (Wahrscheinlichkeit 0.14),
+:# &nbsp; $\underline{\rm E}$ → '''<u>0001</u>''' (Wahrscheinlichkeit 0.10), &nbsp;  $\underline{\rm F}$ → '''<u>0000</u>'''  (Wahrscheinlichkeit 0.04).
-:$$H_{\rm max} = H_0 = \text{ 1 bit/Symbol}\hspace{0.05cm}.$$
+''Anmerkungen'':
+*Ein&nbsp; „$\rm x$”&nbsp; weist wieder darauf hin, dass in nachfolgenden Codierschritten noch Bits hinzugefügt werden müssen.
+*Es ergibt sich hier zwar eine andere Zuordnung als bei der&nbsp; [https://en.lntwww.de/Applets:Huffman-_und_Shannon-Fano-Codierung#Der_Huffman.E2.80.93Algorithmus Huffman–Codierung], aber genau die gleiche mittlere Codewortlänge:
+:$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$}}
-* In diesem Fall &nbsp;$(p_{\rm A}= p_{\rm B} =0.5)$&nbsp; ist die Symbolfolge redundanzfrei &nbsp; &rArr; &nbsp; die relative Redundanz ist gleich &nbsp;$r = (H - H_0)/H_0= 0$.
-* Im unsymmetrischen Fall &nbsp;$(p_{\rm A} \ne p_{\rm B})$&nbsp; ist die relative Redundanz &nbsp;$r > 0$&nbsp; und für die Entropie gilt mit den Entropienäherung &nbsp;$H_k$:
+Mit den Wahrscheinlichkeiten entsprechend dem $\text{Beispiel 4}$ führt der Shannon–Fano–Algorithmus zur gleichen mittleren Codewortlänge wie die Huffman–Codierung. Ebenso sind bei vielen (eigentlich: den meisten) anderen Wahrscheinlichkeitsprofilen Huffman und Shannon–Fano aus informationstheoretischer Sicht äquivalent.
-:$$H = H_1 < H_0, \hspace{0.5cm}H_1 = H_2 = H_3 = \text{...} .$$
+Es gibt aber durchaus Fälle, bei denen sich beide Verfahren hinsichtlich der (mittleren) Codewortlänge unterscheiden, wie das folgende Beispiel zeigt.
-* Bei einer gedächtnislosen Quelle sind also alle (analytisch berechneten) Entropienäherungen &nbsp;$H_k$&nbsp; exakt gleich. Für die durch Simulation aus der Symbolfolge &nbsp;$〈 q_ν〉$&nbsp; der Länge &nbsp;$N$&nbsp; gewonnenen Näherungen &nbsp;$\hat  H_k$&nbsp; gilt dieser Zusammenhang bestenfalls näherungsweise
+{{GraueBox|TEXT=
+$\text{Beispiel 2:}$&nbsp; Wir betrachten $M = 5$ Symbole mit folgenden Wahrscheinlichkeiten:
+:$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm}
+p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13 \hspace{0.3cm}
+\Rightarrow\hspace{0.3cm}  H = 2.19\,{\rm bit/Quellensymbol}
+\hspace{0.05cm}. $$
-:$$\hat  H_1 \approx \hat  H_2 \approx \hat  H_3 \approx \text{...} .$$
+[[File:P_ID2461__Inf_T_2_4_S1_ganz_neu.png|center|frame|Baumstrukturen nach Shannon–Fano bzw. Huffman]]
-* Als Ergebnis sollte man &nbsp;$H \approx \hat  H_1$&nbsp; verwenden. Bei gegebenem &nbsp;$N$&nbsp; sind die auf der Zeitmittelung basierenden Fehler für &nbsp;$\hat  H_2$ &nbsp;$\hat  H_3$, ... deutlich größer. Oder anders ausgedrückt: &nbsp; Um die gleiche statistische Sicherheit für die Ermittlung von &nbsp;$\hat  H_{k+1}$&nbsp; wie bei &nbsp;$\hat  H_k$&nbsp; zu erzielen, muss man &nbsp;$N$&nbsp; verdoppeln.
+Die Grafik zeigt die jeweiligen Codebäume für Shannon–Fano (links) bzw. Huffman (rechts). Die Ergebnisse lassen sich wie folgt zusammenfassen:
+* Der Shannon–Fano–Algorithmus führt zum Code $\rm A$ → '''11''', &nbsp; $\rm B$ → '''10''', &nbsp; $\rm C$ → '''01''', &nbsp; $\rm D$ → '''001''', &nbsp; $\rm E$ → '''000''' und damit zur mittleren Codewortlänge
+:$$L_{\rm M} = (0.38 + 0.18 + 0.16) \cdot 2 + (0.15 + 0.13) \cdot 3 = 2.28\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
+*Mit "Huffman" erhält man $\rm A$ → '''1''', &nbsp; $\rm B$ → '''001''', &nbsp; $\rm C$ → '''010''', &nbsp; $\rm D$ → '''001''', &nbsp; $\rm E$ → '''000''' und eine etwas kleinere mittlere Codewortlänge:
+:$$L_{\rm M} = 0.38 \cdot 1 + (1-0.38) \cdot 3 = 2.24\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $$
-=== Binäre Markovquelle ===
+*Es gibt keinen Satz von Wahrscheinlichkeiten, bei denen Shannon–Fano ein besseres Ergebnis liefert als der Huffman–Algorithmus, der stets den bestmöglichen Entropiecodierer bereitstellt.
+*Die Grafik zeigt zudem, dass die Algorithmen im Baumdiagramm in unterschiedlichen Richtungen vorgehen, nämlich einmal von der Wurzel zu den Einzelsymbolen (Shannon–Fano), zum anderen von den Einzelsymbolen zur Wurzel (Huffman).}}
-[[File:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]
-*Folgen mit statistischen Bindungen zwischen den Folgenelementen werden oft durch Markovprozesse modelliert, wobei wir uns hier auf binäre Markovprozesse erster Ordnung mit den Symbolen &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; beschränken.
-*Für die Entropie &nbsp;$H = H_{\text{M}}$&nbsp; und die erste Entropienäherung &nbsp;$H_1$&nbsp; einer solchen Markovquelle gelten die folgenden  Gleichungen:
+==Versuchsdurchführung==
-:$$H_{\text{M}} =  p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
- \hspace{0.05cm},$$
-:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} $$
-:$$\Rightarrow \hspace{0.3cm}H_1  = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
- \hspace{0.05cm}.$$
-*Die Entropienäherungen &nbsp;$H_k$&nbsp; für &nbsp;$k$–Tupel hängen mit der ersten Näherung &nbsp;$H_1$&nbsp; und dem Endwert &nbsp;$H = H_{\text{M}}$&nbsp; wie folgt zusammen:
-:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
- H_2 = {1}/{2} \cdot \big [ H_{\rm 1} +  H_{\rm M} \big ]\hspace{0.05cm}, \hspace{0.3cm}
- H_3 ={1}/{3} \cdot \big [ H_{\rm 1} + 2 \cdot H_{\rm M}\big ] \hspace{0.05cm},\hspace{0.3cm}
- H_4 =  {1}/{4} \cdot \big [ H_{\rm 1} + 3 \cdot H_{\rm M}\big ]
- \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}$$
-* Daraus folgt direkt: &nbsp; Ist über die Nachrichtenquelle nicht mehr bekannt, als dass es sich um eine Markovquelle erster Ordnung handelt, so kann der Endwert &nbsp;$H = H_{\rm M}$&nbsp; allein aus den Entropienäherungen &nbsp;$H_1$&nbsp; und &nbsp;$H_2$&nbsp; ermittelt werden:
-:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm}.$$
-{{BlaueBox|TEXT=
+[[File:5.png|right]]
-Bei einem '''symmetrischen Markovprozess'''   &nbsp; ⇒  &nbsp;   Übergangswahrscheinlichkeiten   &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } $ &nbsp; ⇒  &nbsp;   Symbolwahrscheinlichkeiten   &nbsp;$p_{\rm A } = p_{\rm B } = 0.5 $&nbsp; erhält man
-:$$H_{\text{M} } = H_{\text{bin} }(p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} })=  p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } } + (1 - p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1 - p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } },\hspace{0.5cm}H_1 = 1\text{ bit/Symbol} .$$}}
-==Versuchsdurchführung==
-[[File:Exercises_Entropie.png|right]]
 *Wählen Sie zunächst die Aufgabennummer.
 *Eine Aufgabenbeschreibung wird angezeigt.
-*Alle Parameterwerte sind angepasst.
+*Alle Parameter sind angepasst.
-*Alle Entropiewerte werden berechnet und eine Symbolfolge ausgegeben.
+*Alle Grafiken (Baumdiagramm, Symbolfolgen) sind aktualisiert.
-*Musterlösung nach Drücken von &bdquo;Hide solution&rdquo;.
+*Ebenso die Ergebnisse &nbsp;$H, \ L_{\rm  M}$&nbsp; sowie&nbsp;$H\hspace{0.05cm}', \ L_{\rm  M}\hspace{0.05cm}'$.
-*Mit der Nummer &bdquo;0&rdquo; wird auf die gleichen Einstellung wie beim Programmstart zurückgesetzt.
+*Musterlösung nach Drücken von "Hide solution".
+*Nummer "0": &nbsp; Gleiche Einstellung wie beim Programmstart.
 <br clear=all>
 {{BlaueBox|TEXT=
-'''(1)''' &nbsp; Wählen Sie die gedächtnislose Binärquelle mit &nbsp;$p_{\rm A} = p_{\rm B} = 0.5$. Wie lauten die analytisch berechneten Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$?
+'''(1)''' &nbsp; Wählen Sie die Quelle gemäß der Voreinstellung mit &nbsp;$M=8$ &nbsp; &rArr; &nbsp; Entropie $H=2.278$  (bit/Quellensymbol), Huffman-Codierung und "Herleitung".
+:Interpretieren Sie die Ergebnisse. Wie werden die Quellensymbole &nbsp;$\rm C$, &nbsp;$\rm D$&nbsp; und &nbsp;$\rm E$&nbsp; codiert? Wie groß ist die mittlere Codewortlänge &nbsp;$L_{\rm M}$? }}
-:Wie unterscheiden sich die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$&nbsp; mit &nbsp;$N=10^5$&nbsp; von &nbsp;$H_1$, ... , &nbsp;$H_6$? &nbsp; Machen Sie jeweils zehn Versuche.  }}
+::*&nbsp;Es ergibt sich folgende Zuordnung:&nbsp; $\rm C \ \to 1$,&nbsp; $\rm D \ \to 01100$,&nbsp; $\rm E \ \to 0010$. Die mittlere Codewortlänge ist &nbsp;$L_{\rm M}= 2.29$&nbsp; (bit/Quellensymbol)&nbsp;$>H$.
+::*&nbsp;Erklärung:&nbsp; Im Baumdiagramm kommt man von der "Root" (gelber Kreis) zum Symbol &nbsp;$\rm E$&nbsp; über Blau &ndash; Blau &ndash; Rot &ndash; Blau. "Blau" steht für &nbsp;$0$&nbsp; und "Rot" für &nbsp;$1$.
-::*&nbsp;Es handelt sich um eine redundanzfreie Binärquelle &nbsp; &rArr; &nbsp; $H = H_{\rm bin}(0.5) = H_1 =$ ... $=H_6 = 1\text{ bit/Symbol}$.
+{{BlaueBox|TEXT=
-::*&nbsp;Auch die Simulation mit &nbsp;$N=10^5$&nbsp; liefert bei (fast) allen Versuchsreihen &nbsp;$\hat H_1 =$ ... &nbsp;$=\hat H_6 = 1.000$ &nbsp; &rArr; &nbsp; das auf drei Nachkommastellen richtige Ergebnis.
+'''(2)''' &nbsp; Wie unterscheiden sich bei sonst gleichen Einstellungen die Ergebnisse für  "Shannon&ndash;Fano"? }}
+::*&nbsp;Hier ergibt sich eine andere Zuordnung:&nbsp; $\rm C \ \to 1$,&nbsp; $\rm D \ \to 01010$,&nbsp; $\rm E \ \to 0100$. Trotzdem ist die mittlere Codewortlänge wieder &nbsp;$L_{\rm M}= 2.29$.
+::*&nbsp;Erklärung:&nbsp; Im Graphen kommt man von der "Root" &nbsp;$\rm CAFBGEHD$&nbsp; zu &nbsp;$\rm E$&nbsp; über Blau &ndash; Rot &ndash; Blau &ndash; Blau. "Blau" steht wieder für &nbsp;$0$&nbsp; und "Rot" für &nbsp;$1$.
 {{BlaueBox|TEXT=
-'''(2)''' &nbsp; Wie unterscheiden sich bei sonst gleichen Einstellungen die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$ mit $N=10^3$? &nbsp; Wieder jeweils zehn Versuche.  }}
+'''(3)''' &nbsp; Warum ist bei "Huffman" und "Shannon&ndash;Fano" trotz unterschiedlicher Zuordnung die mittlere Codewortlänge gleich?}}
-::*&nbsp;Die Entropienäherungen $H_k$ werden nun durch $\hat H_k$ ungenauer nachgebildet als mit $N=10^5$ &nbsp; &rArr; &nbsp; die Statistik ist nicht ausreichend.
+::*&nbsp;In beiden Fällen wird &nbsp;$\rm C$&nbsp; mit einem Bit codiert, &nbsp;$\rm A$&nbsp; und &nbsp;$\rm F$&nbsp; mit drei Bit, &nbsp;$\rm B$, &nbsp;$\rm E$&nbsp; und &nbsp;$\rm G$&nbsp; mit vier Bit sowie &nbsp;$\rm D$&nbsp; und &nbsp;$\rm H$&nbsp; mit fünf Bit. Daraus folgt:&nbsp;
-::*&nbsp;Die Simulation mit $N=10^3$ liefert bei zehn Versuchsreihen für $\hat H_1$ entweder $1.000$ oder $0.999$ und für $\hat H_6$ Werte zwischen $0.982$ und $0.995$ &nbsp;
+::*&nbsp;$L_{\rm M}= p_{\rm C} \cdot 1 + \big [p_{\rm A} + p_{\rm F}\big] \cdot 3 + \big [p_{\rm B} + p_{\rm E}+ p_{\rm G}\big] \cdot 4 + \big [p_{\rm D} + p_{\rm H}\big] \cdot 5 = 0.52 \cdot 1 + 0.22 \cdot 3 + 0.19 \cdot 4 + 0.07 \cdot 5 = 2.29$&nbsp; (bit/Quellensymbol)
-::*&nbsp; &rArr; &nbsp; Simulationsgenauigkeit nimmt mit steigendem $k$ ab. Die simulierten Werte $\hat H_k$ sind stets kleiner als $H_k = 1.000$. Beides gilt auch für noch kleineres &nbsp;$N$.
 {{BlaueBox|TEXT=
-'''(3)''' &nbsp; Wählen Sie nun die gedächtnislose Binärquelle mit &nbsp;$p_{\rm A} =  0.2$&nbsp; und &nbsp;$p_{\rm B} =  0.8$. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$?
+'''(4)''' &nbsp; Wählen Sie "Voreinstellung" und "Huffman". Wie ändern sich  die Ergebnisse für "Simulation über 10000 Symbole" &nbsp;$(H', \ L_{\rm M}\hspace{0.05cm}')$&nbsp; gegenüber &nbsp;$(H, \ L_{\rm M})$&nbsp; für $N \to \infty$?
-:Wie unterscheiden sich die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$&nbsp; mit &nbsp;$N=10^5$&nbsp; von &nbsp;$H_1$, ... , &nbsp;$H_6$? &nbsp; Wieder jeweils zehn Versuche.}}
+:Starten Sie jeweils zehn Simulationen. Welche Aussagen stimmen mit diesen Wahrscheinlichkeiten immer: &nbsp;$L_{\rm M}\hspace{0.05cm}' > L_{\rm M}$, &nbsp; &nbsp; $L_{\rm M}\hspace{0.05cm}' > H$,&nbsp; &nbsp; $L_{\rm M}\hspace{0.05cm}' > H'$?}}
-::*&nbsp;Es gilt &nbsp;$H = H_{\rm bin}(0.2) = 0.722\text{ bit/Symbol}$. Wie bei jeder gedächtnislosen Nachrichtenquelle gilt auch hier &nbsp;$H_1 =$ ... $=H_6 = H$.
+::*&nbsp;Für die theoretischen Werte &nbsp;(also für &nbsp;$N \to \infty)$&nbsp; gilt immer &nbsp;$L_{\rm M} \ge H$. Außerdem wird für jede einzelne Simulation gelten:&nbsp; $L_{\rm M}\hspace{0.05cm}' \ge H'$.
-::*&nbsp;Die Simulation mit &nbsp;$N=10^5$&nbsp; liefert bei zehn Versuchsreihen für &nbsp;$\hat H_1$&nbsp; Werte zwischen $0.719$ und $0.727$. Es gilt aber stets &nbsp;$\hat H_1 =$ ... $= \hat H_6$.
+::*&nbsp;Da bei jeder einzelnen Simulation &nbsp;$H'$&nbsp; größer, kleiner oder gleich &nbsp;$H$&nbsp; sein kann, ist aber &nbsp;$L_{\rm M}\hspace{0.05cm}' < H$&nbsp; durchaus möglich.
-::*&nbsp;In solchen Fällen weicht die relative Häufigkeit &nbsp;$h_{\rm A}$&nbsp; von der Wahrscheinlichkeit &nbsp;$p_{\rm A}$&nbsp; ab. Ist &nbsp;$\hat H_1 > 0.722$, so ist &nbsp;$h_{\rm A} > 0.2$.
 {{BlaueBox|TEXT=
-'''(4)''' &nbsp; Was ändert sich gegenüber '''(3)''' mit den Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A} =  0.8$&nbsp; und &nbsp;$p_{\rm B} =  0.2$?}}
+'''(5)''' &nbsp; Wählen Sie nun die  "Quelle 3" &nbsp;$(M=4, \ p_{\rm A}= p_{\rm B}=p_{\rm C}= p_{\rm D}=0.25)$&nbsp; und "Huffman". Interpretieren Sie die Ergebnisse. Was wäre bei "Shannon&ndash;Fano"?}}
-::&nbsp;'''Nichts'''. Die binäre Entropiefunktion ist symmetrisch um &nbsp;$p=0.5$.
+::*&nbsp;Jedes Symbol wird durch zwei Bit dargestellt, so dass &nbsp;$L_{\rm M} = H = 2$&nbsp; (bit/Quellensymbol) ist. Die Simulation liefert auch immer &nbsp;$L_{\rm M}\hspace{0.05cm}' = 2$, auch für &nbsp;$H' < 2$.
-::&nbsp;'''Ist nun &nbsp;$\hat H_1 > 0.722$, so ist &nbsp;$h_{\rm A} < 0.8$.'''
+::*&nbsp;Gleiches gilt für "Shannon&ndash;Fano" trotz anderer Zuordnung:&nbsp; $\rm A \ \to 00$,&nbsp; $\rm B \ \to 01$,&nbsp; $\rm C \ \to 10$,&nbsp; $\rm D \ \to 11$ statt&nbsp; $\rm A \ \to 01$,&nbsp; $\rm B \ \to 00$,&nbsp; $\rm C \ \to 11$,&nbsp; $\rm D \ \to 10$.
+::*&nbsp;Aber ganz klar ist: &nbsp; Quellencodierung macht bei redundanzfreier Quelle keinen Sinn, weder "Huffman" noch "Shannon&ndash;Fano".
 {{BlaueBox|TEXT=
-'''(5)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.8$&nbsp;. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}
+'''(6)''' &nbsp; Wählen Sie die  "Quelle 4" &nbsp;$(M=4, \ p_{\rm A}= 0.5, \ p_{\rm B}= 0.25, \ p_{\rm C}= p_{\rm D}=0.125)$. Warum gilt hier &nbsp;$L_{\rm M} = H = 1.75$&nbsp; (bit/Quellensymbol)? Interpretation. }}
-::*&nbsp;Bei dieser &bdquo;Markovquelle&rdquo; ist &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$&nbsp;. Deshalb ist auch die unbedingte Wahrscheinlichkeit &nbsp;$p_{\rm A} = 0.2$ &nbsp; &rArr; &nbsp; $p_{\rm B} = 0.8$.
+::*&nbsp;Sowohl bei "Huffman" als auch bei "Shannon&ndash;Fano" wird &nbsp;$\rm A$&nbsp; mit einem Bit codiert, &nbsp;$\rm B$&nbsp;  mit zwei Bit sowie &nbsp;$\rm C$&nbsp; und &nbsp;$\rm D$&nbsp; mit drei Bit.
-::*Es handelt sich also um die gleiche gedächtnislose Quelle wie bei '''(4)''' &nbsp; &rArr; &nbsp;$H = H_1 =$ ... $=H_6 =  0.722\text{ bit/Symbol}$.
+::*&nbsp;Daraus folgt: &nbsp; $L_{\rm M}= 0.5 \cdot 1 + 0.25 \cdot 2 + 2 \cdot 0.125 \cdot 3 = H = 1.75$&nbsp; (bit/Quellensymbol). Es sind "günstige Wahrscheinlichkeiten" der Form &nbsp;$p = 2^{-k}$.
+::*&nbsp;Ohne eine "Entropiecodierung" nach Huffman oder Shannon&ndash;Fano würden alle vier Symbole mit zwei Bit dargestellt: &nbsp; $L_{\rm M}= 2$&nbsp; (bit/Quellensymbol).
 {{BlaueBox|TEXT=
-'''(6)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.2$&nbsp;. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}
+'''(7)''' &nbsp; Wählen Sie nun "Shannon&ndash;Fano" und die  "Quelle 2" &nbsp;$(M=3, \ p_{\rm A}= 0.34, \ p_{\rm B}= p_{\rm C} =0.33)$. Mit welchen Wahrscheinlichkeiten ergäbe sich &nbsp;$L_{\rm M} = H $? }}
-::*&nbsp;Hier handelt es sich um eine &bdquo;echte Markovquelle&rdquo;, da sich &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$&nbsp; unterscheiden.
+::*&nbsp;Die Ternärquelle ist nahezu redundanzfrei: &nbsp;$H \approx \log_2 \ 3 \approx 1.585$. Mit &nbsp; $\rm A \ \to 0$,&nbsp; $\rm B \ \to 10$,&nbsp;$\rm C \ \to 11$&nbsp; ist $L_{\rm M}= 1.66 > H$.
-::*Wegen &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}}$ sind die beiden unbedingten Symbolwahrscheinlichkeiten gleich: &nbsp;$p_{\rm A} = p_{\rm B} = 0.5$&nbsp; &rArr; &nbsp; $H_1 = 1$.
+::*&nbsp;"Günstige Wahrscheinlichkeiten" wären zum Beispiel &nbsp;$p_{\rm A}= 0.5, \ p_{\rm B}= p_{\rm C}= 0.25$&nbsp; wie bei "Quelle 1". Dann ist&nbsp; $L_{\rm M}= H = 1.5$&nbsp; (bit/Quellensymbol).
-::*Die Entropienäherungen $H_k$ werden mit steigendem $k$ kleiner: &nbsp;$H_2 = 0.861$, &nbsp;$H_3 = 0.815$, ... , &nbsp;$H_6 = 0.768$.  Der Endwert ist wieder &nbsp;$H = H_\infty = 0.722\text{ bit/Symbol}$.
 {{BlaueBox|TEXT=
-'''(7)''' &nbsp; Welche Unterschiede gegenüber '''(6)''' ergeben sich mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.8$? }}
+'''(8)''' &nbsp; Wählen Sie "Huffman" und die  "Quelle 5" &nbsp;$(M=6, \ p_{\rm A}= p_{\rm B}= 0.25, \ p_{\rm C} = p_{\rm D} = p_{\rm E} = p_{\rm F} =0.125)$. Sind dies "günstige Wahrscheinlichkeiten"? }}
-::*&nbsp;Die Entropienäherung &nbsp;$H = H_{\rm bin}(0.8) = H_{\rm bin}(0.2)= 0.722\text{ bit/Symbol}$&nbsp; bleibt gleich, ebenso alle Entropienäherungen &nbsp;$H_k$.
+::*&nbsp;$\rm JA$. Alle Wahrscheinlichkeiten sind&nbsp; $2^{-2}$&nbsp; oder&nbsp; $2^{-3}$ &nbsp; &rArr; &nbsp; Symbole werden mit zwei oder drei Bit dargestellt &nbsp; &rArr; &nbsp; $L_{\rm M}= H = 2.5$&nbsp; (bit/Quellensymbol).
-::* Wegen den größeren Übergangswahrscheinlichkeiten &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}} = 0.8$&nbsp; erkennt man jetzt deutlich mehr Übergänge in der ausgegebenen Symbolfolge.
 {{BlaueBox|TEXT=
-'''(8)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.9$. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}
+'''(9)''' &nbsp; Wie unterscheiden sich demgegenüber die Ergebnisse für "Quelle 6" &nbsp;$(M=6, \ p_{\rm A}= 0.26, \ p_{\rm B}= 0.24, \ p_{\rm C} = p_{\rm D} = 0.13, \ p_{\rm E} = p_{\rm F} =0.12)$? }}
-::*Wegen &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} \ne p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}}$ sind nun die beiden unbedingten Symbolwahrscheinlichkeiten unterschiedlich: &nbsp;$p_{\rm A} = 0.471$&nbsp; und &nbsp;$p_{\rm B} = 0.529$&nbsp; &rArr; &nbsp; $H_1 = 0.998 \ne 1$.
+::*&nbsp;Bereits durch geringfügige Wahrscheinlichkeitsabweichungen ergeben sich ein anderer Baum und damit auch andere Symbolzuordnungen.
-::*Die Entropienäherungen $H_k$ werden wieder kontinuierlich kleiner: &nbsp;$H_2 = 0.800$, &nbsp;$H_3 = 0.734$, ... , &nbsp;$H_6 = 0.669$.  Endwert: &nbsp; $H = H_\infty = 0.603\text{ bit/Symbol}$.
+::*&nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; werden mit zwei Bit codiert, die anderen mit drei Bit. &nbsp;$L_{\rm M}=  \big [p_{\rm A} + p_{\rm B}\big] \cdot 2 + \big [p_{\rm C} + p_{\rm D}+ p_{\E}+ p_{\F}\big] \cdot 3 = 2.5$&nbsp; (bit/Quellensymbol).
-::*&nbsp;Aus der Symbolfolge erkennt man, dass zwei Symbole &nbsp;$\rm A$&nbsp; ganz selten aufeinanderfolgen.
+::*&nbsp;Die geänderten&nbsp; $p_{\rm A}$, ... &nbsp; verändern hier nicht die mittlere Codewortlänge, aber &nbsp;$H=2.499$ wird (geringfügig) kleiner &nbsp; &rArr; &nbsp; $L_{\rm M} > H$&nbsp; (bit/Quellensymbol).
 {{BlaueBox|TEXT=
-'''(9)''' &nbsp; Es gelte weiterhin &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.9$. Für welches &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }$&nbsp; ergibt sich die maximale Entropie? }}
+'''(10)''' &nbsp; Betrachten Sie die "Quelle 9" &nbsp;$(M=8, \ p_{\rm A}= 0.8, \ p_{\rm B}= p_{\rm C}= p_{\rm D}=0.02, \ p_{\rm E} = 0.01$,&nbsp; ...&nbsp; , $p_{\rm H} = 0.01)$&nbsp; &rArr; &nbsp; $H = 0.741$&nbsp; (bit/Quellensymbol). Interpretation. }}
-::*Anhand der roten Kurve in der Grafik zu '''(8)''' lässt sich bereits das Ergebnis  &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }\approx 0.45$&nbsp; abschätzen.
+::*&nbsp;Es ergibt sich mit &nbsp;$L_{\rm M} = 1.28$&nbsp; ein sehr viel größerer Wert als &nbsp;$H = 0.741$&nbsp; &ndash; sowohl für "Huffman" als auch für "Shannon&ndash;Fano".
-::* Der dazugehörige Entropie&ndash;Endwert ist &nbsp; $H = H_\infty = 0.818\text{ bit/Symbol}$.
+::*&nbsp;Beide Verfahren sind also zur Quellenkomprimierung nicht geeignet, wenn eine Symbolwahrscheinlichkeit deutlich größer ist als 50%.
 {{BlaueBox|TEXT=
-'''(10)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1.0$. Interpretieren Sie die dargestellten Ergebnisse. }}
+'''(11)''' &nbsp; Die Komprimierung der "Quelle 9" &nbsp;$(M=8, H = 2.481)$&nbsp; mit "Huffman" ergibt &nbsp;$L_{\rm M} = 2.58$. Welches Ergebnis liefert "Shannon&ndash;Fano"?&nbsp; Interpretation. }}
-::*Die unbedingten Symbolwahrscheinlichkeiten sind &nbsp;$p_{\rm A} = 0.444$&nbsp; und &nbsp;$p_{\rm B} = 0.556$&nbsp; &rArr; &nbsp; $H_1 = 0.991 \ne 1$. Der Entropie&ndash;Endwert ist &nbsp;$H = H_\infty = 0.401\text{ bit/Symbol}$.
+::*&nbsp;Bei "Huffman" wird ein Symbol mit einem Bit codiert, zwei mit drei Bit, drei mit vier Bit und zwei mit fünf Bit &nbsp; &rArr; &nbsp; $L_{\rm M} = 2.58$&nbsp;  (bit/Quellensymbol).
-::*&nbsp;Aus der Symbolfolge erkennt man, dass das Symbol &nbsp;$\rm A$&nbsp; im Gegensatz zum Symbol &nbsp;$\rm B$&nbsp; stets isoliert auftritt.
+::*&nbsp;Entsprechend gilt für "Shannon&ndash;Fano":&nbsp; zweimal zwei  Bit, dreimal drei Bit, einmal vier Bit,  zweimal fünf Bit &nbsp; &rArr; &nbsp; $L_{\rm M} = 2.61$&nbsp;  (bit/Quellensymbol).
+::*&nbsp;$\rm Fazit$:&nbsp; "Huffman" ist die optimale Entropiecodierung. "Shannon&ndash;Fano" erreicht meist das gleiche Ergebnis. &nbsp;$\text{Aber nicht immer!}$
-{{BlaueBox|TEXT=
-'''(11)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0$. Interpretieren Sie die dargestellten Ergebnisse. }}
-::*Die unbedingten Symbolwahrscheinlichkeiten sind &nbsp;$p_{\rm A} = 1$&nbsp; und &nbsp;$p_{\rm B} = 0$&nbsp; &rArr; &nbsp; die Symbolfolge besteht nur aus &nbsp;$\rm A$&nbsp; &nbsp; &rArr; &nbsp; Entropienäherung &nbsp;$H_1 = 0 $.
-::*&nbsp;Alle weiteren Entropienäherungen $H_k$ und auch der Entropie&ndash;Endwert sind ebenfalls Null.
+==Zur Handhabung des Applets==
+[[File:Anleitung_Huffman_1.png|left|frame|Bildschirmabzug "Herleitung"]]
+<br>
+&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Bildschirmauswahl: &nbsp; Herleitung / Simulation
+&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; Auswahl zwischen 8 Nachrichtenquellen mit &nbsp;$M=3$&nbsp; bis &nbsp;$M=8$
-==Zur Handhabung des Applets==
+&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; Ausgewählte Wahrscheinlichkeiten
-[[File:Anleitung_Entropie.png|left]]
+&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; Entropie und mittlere Codewortlänge (Theorie, &nbsp; $N \to \infty$)
-<br>
-&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Auswahl: &nbsp; Gedächtnislose Quelle / Markovquelle
-&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; Parametereingabe per Slider (Beispiel Markovquelle)
+&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Auswahl des Kompressionsverfahrens: &nbsp; Huffman / Shannon-Fano
-&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; Markovdiagramm (falls Markovquelle)
+&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Ergebnisse der Codewortzuweisung
-&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; Eingabe der Folgenlänge &nbsp;$N$&nbsp; zur Berechnung der&nbsp; $\hat H_k$
+&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Entropie und mittlere Codewortlänge (Simulation über &nbsp;$N \to \infty$)
-&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Ausgabe einer simulierten Symbolfolge
+&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Grafikfeld zur Herleitung des Codes gemäß Baumdiagramm
-&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Ausgabe des Entropiewertes&nbsp; $H$
+&nbsp; &nbsp; '''(I)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung: &nbsp;  Aufgabenauswahl
-&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Ausgabe der Entropienäherungen&nbsp; $H_k$
+&nbsp; &nbsp; '''(J)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Aufgabenstellung
-&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Ausgabe der numerisch ermittelten Entropienäherungen&nbsp; $\hat H_k$
+&nbsp; &nbsp; '''(K)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Musterlösung
-&nbsp; &nbsp; '''(I)''' &nbsp; &nbsp; Grafikfeld zur Darstellung der Funktion&nbsp; $H(p_{\rm A})$&nbsp; bzw.&nbsp; $H(p_{\rm A}|p_{\rm B})$
+[[File:Anleitung_Huffman_2.png|right|frame|Bildschirmabzug "Simulation"]]
+<br> <br> <br> <br> <br> <br> <br>
+&nbsp; &nbsp; '''(L)''' &nbsp; &nbsp; Ausgabe der aktuellen Quellensymbolfolge
-&nbsp; &nbsp; '''(J)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung: &nbsp;  Aufgabenauswahl
+&nbsp; &nbsp; '''(M)''' &nbsp; &nbsp; Ausgabe der aktuellen Codesymbolfolge
-&nbsp; &nbsp; '''(K)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Aufgabenstellung
+&nbsp; &nbsp; '''(N)''' &nbsp; &nbsp; Neue Folgen simulieren
-&nbsp; &nbsp; '''(L)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Musterlösung
 <br clear=all>
 ==Über die Autoren==
 Dieses interaktive Applet  wurde am [http://www.lnt.ei.tum.de/startseite Lehrstuhl für Nachrichtentechnik] der [https://www.tum.de/ Technischen Universität München] konzipiert und realisiert.
-*Die erste Version wurde 2011 von [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Eugen_Mehlmann_.28Bachelorarbeit_EI_2011.29|Eugen Mehlmann]] im Rahmen seiner Bachelorarbeit mit &bdquo;FlashMX&ndash;Actionscript&rdquo; erstellt (Betreuer: [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Mitarbeiter_und_Dozenten#Prof._Dr.-Ing._habil._G.C3.BCnter_S.C3.B6der_.28am_LNT_seit_1974.29|Günter Söder]]).
+*Die erste Version wurde 2011 von&nbsp; [[Biographies_and_Bibliographies/An_LNTwww_beteiligte_Studierende#Eugen_Mehlmann_.28Bachelorarbeit_EI_2011.29|Eugen Mehlmann]]&nbsp; im Rahmen seiner Bachelorarbeit mit "FlashMX&ndash;Actionscript" erstellt (Betreuer: [[Biographies_and_Bibliographies/An_LNTwww_beteiligte_Mitarbeiter_und_Dozenten#Prof._Dr.-Ing._habil._G.C3.BCnter_S.C3.B6der_.28am_LNT_seit_1974.29|Günter Söder]]).
-*2019 wurde das Programm  von  [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Xiaohan_Liu_.28Bachelorarbeit_2018.29|Xiaohan Liu]] (Bachelorarbeit, Betreuer: [[Biografien_und_Bibliografien/Beteiligte_der_Professur_Leitungsgebundene_%C3%9Cbertragungstechnik#Tasn.C3.A1d_Kernetzky.2C_M.Sc._.28bei_L.C3.9CT_seit_2014.29|Tasnád Kernetzky]] ) auf  &bdquo;HTML5&rdquo; umgesetzt und neu gestaltet.
+*2019 wurde das Programm  von&nbsp;  [[Biographies_and_Bibliographies/An_LNTwww_beteiligte_Studierende#Xiaohan_Liu_.28Bachelorarbeit_2018.2C_danach_Werkstudentin.29|Xiaohan Liu]]&nbsp; im Rahmen einer Werkstudententätigkeit auf  "HTML5" umgesetzt und neu gestaltet (Betreuer: [[Biographies_and_Bibliographies/Beteiligte_der_Professur_Leitungsgebundene_%C3%9Cbertragungstechnik#Tasn.C3.A1d_Kernetzky.2C_M.Sc._.28bei_L.C3.9CT_seit_2014.29|Tasnád Kernetzky]]).
+Die Umsetzung dieses Applets auf HTML 5 wurde durch&nbsp; [https://www.ei.tum.de/studium/studienzuschuesse/ Studienzuschüsse]&nbsp; der Fakultät EI der TU München finanziell unterstützt. Wir bedanken uns.
 ==Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster==
-{{LntAppletLink|entropie}}
+{{LntAppletLink|shannon-huffman}}