Applets:Zur Verdeutlichung der grafischen Faltung

Open Applet in a new tab

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.

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).

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