Zur Verdeutlichung der grafischen Faltung

Inhaltsverzeichnis

1 Programmbeschreibung
2 Theoretischer Hintergrund
- 2.1 Der Huffman–Algorithmus
3 Versuchsdurchführung
4 Zur Handhabung des Applets
5 Über die Autoren
6 Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster

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

Versuchsdurchführung

Wählen Sie zunächst die Aufgabennummer.
Eine Aufgabenbeschreibung wird angezeigt.
Alle Parameter sind angepasst.
Alle Grafiken und Ergebniswerte sind aktualisiert.
Musterlösung nach Drücken von „Hide solution”.
Nummer „0”: Gleiche Einstellung wie beim Programmstart.

(1) Wählen Sie die Parameter gemäß Voreinstellung $\text{(Gaußimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 1; \text{ Impulsantwort gemäß Tiefpass 2. Ordnung: }\Delta t_h= 1)$.
Interpretieren Sie die dargestellten Grafiken. Wie groß ist der maximale Ausgangswert $y_{\rm max}$? Zu welcher Zeit $t_{\rm max}$ tritt dieser auf?

Dargestellt sind nach Umbenennung: Eingangssignal $x(\tau)$ ⇒ rote Kurve, Impulsantwort $h(\tau)$ ⇒ blaue Kurve, nach Spiegelung $h(-\tau)$ ⇒ grüne Kurve.
Verschiebt man die grüne Kurve um $t$ nach rechts, so erhält man $h(t-\tau)$. Der Ausgangswert $y(t)$ ergibt sich durch Multiplikation und Integration bzgl. $\tau$:

$$y (t) = \int_{ - \infty }^{ +\infty } {x ( \tau ) } \cdot h ( {t - \tau } ) \hspace{0.1cm}{\rm d}\tau = \int_{ - \infty }^{ t } {x ( \tau ) } \cdot h ( {t - \tau } ) \hspace{0.1cm}{\rm d}\tau .$$

Der Ausgangsimpuls $y_{\rm max}$ ist im vorliegenden Fall unsymmetrisch; der maximale Ausgangswert $y_{\rm max}\approx 0.67$ tritt bei $t_{\rm max}\approx 1.5$ auf.

(2) Was ändert sich, wenn man die äquivalente Impulsdauer von $h(\tau)$ auf $\Delta t_h= 1.5$ erhöht?

Der maximale Ausgangswert $y_{\rm max}\approx 0.53$ tritt nun bei $t_{\rm max}\approx 1.75$ auf. Durch die ungünstigere Impulsantwort wird der Eingangsimpuls stärker verformt.
Bei einem Nachrichtenübertragungssystem hätte dies stärkere Verzerrungen (Intersymbol Interference ) zur Folge.

(3) Wählen Sie nun den symetrischen $\text{Rechteckimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0$ und die $\text{ Impulsantwort gemäß Spalt–Tiefpass: }\Delta t_h= 1$.
Interpretieren Sie das Faltungsergebnis. Wie groß ist der maximale Ausgangswert $y_{\rm max}$? Zu welchen Zeiten ist $y(t)>0$? Beschreibt $h(\tau)$ ein kausales System?

Die Faltung zweier Rechtecke mit jeweiliger Dauer $1$ ergibt ein Dreieck mit absoluter Dauer $2$ ⇒ äquivalente Impulsdauer $\Delta t_y= 1$.
$y(t)$ ist im Bereich von $-0.5$ bis $+1.5$ von Null verschieden. Impulsmaximum $y_{\rm max} = 1$ bei $t_{\rm max} = +0.5$.
$h(\tau)$ beschreibt ein kausales System, da $h(\tau) \equiv 0$ für $t < 0$ ⇒ die „Wirkung” $y(t)$ kommt nicht vor der „Ursache” $x(t)$.

(4) Was ändert sich, wenn man die äquivalente Impulsdauer von $h(\tau)$ auf $\Delta t_h= 2$ erhöht?

Die Faltung zweier unterschiedlich breiten Rechtecke ergibt ein Trapez, im vorliegenden Fall zwischen $-0.5$ und $+2.5$ ⇒ äquivalente Impulsdauer $\Delta t_y= 2$.
Das Maximum $y_{\rm max} = 0.5$ tritt im Bereich $0.5 \le t \le 1.5$ auf. Bezüglich Kausalität ändert sich nichts.

(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

(A) Auswahl: Gedächtnislose Quelle / Markovquelle

(B) Parametereingabe per Slider (Beispiel Markovquelle)

(C) Markovdiagramm (falls Markovquelle)

(D) Eingabe der Folgenlänge $N$ zur Berechnung der $\hat H_k$

(E) Ausgabe einer simulierten Symbolfolge

(F) Ausgabe des Entropiewertes $H$

(G) Ausgabe der Entropienäherungen $H_k$

(H) Ausgabe der numerisch ermittelten Entropienäherungen $\hat H_k$

(I) Grafikfeld zur Darstellung der Funktion $H(p_{\rm A})$ bzw. $H(p_{\rm A}|p_{\rm B})$

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

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

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

Ü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 (Bachelorarbeit, Betreuer: Tasnád Kernetzky ) auf „HTML5” umgesetzt und neu gestaltet.

Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster

Applet in neuem Tab öffnen