Zur Verdeutlichung der grafischen Faltung

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(t)$ 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 digitalen Nachrichtenübertragungssystem hätte dies stärkere Impulsinterenzen (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(t)$ 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(t)$ beschreibt ein kausales System, da $h(t) \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(t)$ 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 der Kausalität ändert sich nichts.

(5) Wählen Sie nun den (unsymetrischen) $\text{Rechteckimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0.5$ und die $\text{ Impulsantwort eines Tiefpasses 1. Ordnung: }\Delta t_h= 1$.
Interpretieren Sie die Ergebnisse. Wie groß ist der maximale Ausgangswert $y_{\rm max}$? Zu welchen Zeiten ist $y(t)>0$? Beschreibt $h(t)$ ein kausales System?

Die Impulsantwort $h(t)$ hat für $t > 0$ einen exponentiell abfallenden Verlauf. Füt $t > 0$ gilt stets $y(t) > 0$, aber die Signalwerte können sehr klein werden.
Das Impulsmaximum $y_{\rm max} = 0.63$ tritt bei $t_{\rm max} = +1$ auf. Für $ t < t_{\rm max}$ ist der Verlauf exponentiell ansteigend, für $ t > t_{\rm max}$ exponentiell abfallend.
Der Tiefpass 1. Ordnung kann mit einem Widerstand und einer Kapazität realisiert werden. Jedes realisierbare System ist per se kausal.

(6) Wählen Sie wie in (3) die rechteckförmige Impulsantwort $\text{(Spalt–Tiefpass; }\Delta t_h= 1)$. Mit welchem Eingang $x(t)$ ergibt sich das gleiche $y(t)$ wie bei (5)?

Das Signal $y(t)$ in (5) ergab sich als Faltung zwischen dem rechteckigen Eingang $x(t)$ und der Exponentialfunktion $h(t)$.
Da die Faltungsoperation kommutativ ist, ergibt sich das gleiche Ergebnis mit der Exponentialfunktion $x(t)$ und der Rechteckfunktion $h(t)$.
Die richtige Einstellung für das Eingangssignal $x(t)$ ist $\text{Gaußimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0$ .

(7) Für den Rest dieser Versuchsdurchführung betrachten wir stets den Gauß–Tiefpass. Die äquivalente Dauer der Impulsantwort $h(t)$ sei zunächst $\Delta t_h= 0.8$.
Analsyieren und interpretieren Sie dieses „System” im Hinblick auf Kausalität und die entstehenden Verzerrungen für ein Rechtecksignal.

Der Tiefpass ist nicht kausal / nicht realisierbar: für $t < 0$ gilt nicht $h(t) \equiv 0$ gilt. Als Modell geeignet, wenn man die unendliche Laufzeit außer Acht lässt.
Je größer $\Delta t_h$ ist, desto breiter wird der Ausgangsimpuls und um so stärker die Degradation eines Digitalsystems durch Impulsinterferenzen.
Der Tiefpass–Frequenzgang $H(f)$ ist die Fouriertransformierte von $h(t)$. Je größer $\Delta t_h$ ist, desto schmalbandiger ist das System $\Delta f_h = 1/\Delta t_h$.

(8) Wählen Sie nun den $\text{Gaußimpuls: }A_x = 1, \ \Delta t_x= 1.5, \ \tau_x = 0$ und den $\text{Gauß–Tiefpass: }\Delta t_h= 2$. Welche Form hat der Ausgangsimpuls $y(t)$?
Wie groß ist die äquivalente Dauer $\Delta t_y$ des Ausgangsimpulses und der maximale Ausgangswert $y_{\rm max}$? Zu welcher Zeit $t_{\rm max}$ tritt dieser auf?

$y(t)$ ist ebenfalls (exakt) gaußförmig. Merksatz: Gauß gefaltet mit Gauß ergibt immer Gauß.
Äquivalente Dauer des Ausgangsimpules: $\Delta t_y =\sqrt{\Delta t_x^2+ \Delta t_h^2} = 2.5$. Impulsmaximum $($bei $t=0)$: $y_{\rm max} = A_x \cdot \Delta t_x/\Delta t_y = 1 \cdot 1.5/2.5 = 0.6$.

(9) Wählen Sie nun den $\text{Dreieckimpuls: }A_x = 1, \ \Delta t_x= 1.5, \ \tau_x = 0$ und den $\text{Gauß–Tiefpass: }\Delta t_h= 2$. Welche Form hat der Ausgangsimpuls $y(t)$?
Wie groß ist die äquivalente Dauer $\Delta t_y$ des Ausgangsimpulses und der maximale Ausgangswert $y_{\rm max}$? Zu welcher Zeit $t_{\rm max}$ tritt dieser auf?

$y(t)$ ist gaußähnlich, aber nicht exakt gaußförmig. Merksatz: Gauß gefaltet mit Nicht–Gauß ergibt niemals exakt Gauß.
Die abgefragten Kenngrößen des Ausgangsimpules $y(t)$ unterscheiden sich nur geringfügig gegenüber (8): $\Delta t_y \approx 2.???$, $y_{\rm max} \approx 0.59$.

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 2006 von Markus Elsberger im Rahmen seiner Bachelorarbeit mit „FlashMX–Actionscript” erstellt (Betreuer: Günter Söder).
2019 wurde das Programm von Carolin Mirschina im Rahmen einer Werkstudententätigkei , Betreuer: Tasnád Kernetzky ) auf „HTML5” umgesetzt und neu gestaltet.

Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster

Open Applet in a new tab