Applets:Zur Verdeutlichung der grafischen Faltung

Applet in neuem Tab öffnen

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

Noch überarbeiten!

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

Ende Überarbeitung!

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

    (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