Zur Verdeutlichung der grafischen Faltung
Inhaltsverzeichnis
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 des entsprechenden Buttons.
- 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?
- 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)$. $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_(t)$ 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?
- $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, hier 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 $y_{\rm max}$? Zu welchen Zeiten ist $y(t)>0$ ? Beschreibt $h(t)$ ein kausales System?
- $h(t)$ hat für $t > 0$ einen exponentiell abfallenden Verlauf. Für $t > 0$ gilt stets $y(t) > 0$, aber die Signalwerte können sehr klein werden.
- $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 $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 somit $\text{Exponentialimpuls: }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 (realisierbar): für $t < 0$ gilt nicht $h(t) \equiv 0$ gilt. Geeignetes Modell, 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 kleiner ist $\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: $\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.55$, $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ätigkeit auf „HTML5” umgesetzt und neu gestaltet (Betreuer: Tasnád Kernetzky).
