Applets:Zur Verdeutlichung der grafischen Faltung: Unterschied zwischen den Versionen
Zeile 54: | Zeile 54: | ||
::* 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. | ::* 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. | + | ::* Bei einem Nachrichtenübertragungssystem hätte dies stärkere Verzerrungen (''Intersymbol Interference '') zur Folge. |
{{BlaueBox|TEXT= | {{BlaueBox|TEXT= | ||
− | '''(3)''' | + | '''(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$. |
+ | <br> Interpretieren Sie das Faltungsergebnis. Wie groß ist der maximale Ausgangswert $y_{\rm max}$? Zu welchen Zeiten ist $y(t)>0$? }} | ||
+ | |||
::* 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: | ::* 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: |
Version vom 25. Juni 2019, 17:13 Uhr
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
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) 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$?
- 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.