Applets:Zur Verdeutlichung der grafischen Faltung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „{{LntAppletLink|shannon-huffman}} ==Programmbeschreibung== <br> Dieses Applet verdeutlicht die Quellencodierverfahren nach Huffman bzw. Shannon–Fano. D…“)
 
 
(38 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{LntAppletLink|shannon-huffman}}  
+
{{LntAppletLinkDeEn|convolution|convolution_en}}
 +
 
 +
 
  
 
==Programmbeschreibung==
 
==Programmbeschreibung==
 
<br>
 
<br>
Dieses Applet verdeutlicht die Quellencodierverfahren nach Huffman bzw. Shannon&ndash;Fano. Diese Verfahren komprimieren redundante wertdiskrete Quellen ohne Gedächtnis mit Stufenzahl &nbsp;$M$, dem Symbolvorrat &nbsp;$\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \} = \{ \rm A, \hspace{0.1cm} B, \hspace{0.1cm}\text{ ...}\}$ und den Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A} \hspace{0.05cm},\hspace{0.1cm} p_{\rm B} \hspace{0.05cm}, \hspace{0.05cm}\text{ ...}$&nbsp;.
+
Dieses Applet verdeutlicht die Faltungsoperation im Zeitbereich
 
+
*zwischen einem Eingangsimpuls &nbsp;$x(t)$ &nbsp; &rArr; &nbsp; Rechteck, Dreieck, Gauß, Exponentialfunktion
Ziel der Quellencodierung und insbesondere der Klasse der Entropiecodierung &ndash; zu der &bdquo;Huffman&rdquo; und &bdquo;Shannon&ndash;Fano&rdquo; gehören &ndash; ist, dass die mittlere Codewortlänge &nbsp;$L_{\rm M}$&nbsp; des binären Codes &ndash; darstellbar durch unterschiedlich lange Folgen von Nullen und Einsen  &ndash; möglichst nahe an die Quellenentropie
+
*und der Impulsantwort &nbsp;$h(t)$&nbsp; eines LZI&ndash;Systems mit Tiefpass&ndash;Charakter&nbsp; &rArr; &nbsp; Spalt&ndash;Tiefpass, Tiefpass erster bzw. zweiter Ordnung, Gauß&ndash;Tiefpass.
 
 
:$$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 &nbsp;$L_{\rm M} \ge H$, wobei das Gleichheitszeichen nicht für alle Symbolwahrscheinlichkeiten erreicht werden kann.
 
  
Dargestellt werden jeweils
+
Für das Ausgangssignal &nbsp;$y(t)$&nbsp; entsprechend dem Blockschaltbild im &nbsp;$\text{Beispiel 1}$&nbsp; gilt dann, wie im Kapitel&nbsp; [[Applets:Zur_Verdeutlichung_der_grafischen_Faltung#Grafische_Faltung|Grafische Faltung]]&nbsp; dargelegt:
* das Baumdiagramm zur Herleitung des jeweiligen Binärcodes, und
+
:$$y( t ) = x(t) * h( t ) = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm}{x( \tau  )}  \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau .$$
* eine simulierte Quellensymbolfolge der Länge &nbsp;$N = 10000$&nbsp; (Entropie &nbsp;$H\hspace{0.05cm}' \approx H)$&nbsp; und die dazugehörige Codesymbolfolge der Länge &nbsp;$L_{\rm M}\hspace{0.05cm}' \hspace{-0.03cm}\cdot \hspace{-0.03cm} N$.
 
  
 +
Bei kausalen Systemen &nbsp; &rArr; &nbsp; &nbsp;$h(t) \equiv 0$&nbsp; für &nbsp;$t < 0$&nbsp; (Beispiele: Spalt&ndash;Tiefpass sowie Tiefpass erster und zweiter Ordnung) &nbsp; kann hierfür auch geschrieben werden:
  
Auf die Einheiten &bdquo;$\rm bit/Quellensymbol$&rdquo; für die Entropie und die mittlere Codewortlänge wird im Programm verzichtet.
+
:$$y( t ) =  \int_{ - \infty }^{ t } \hspace{-0.15cm}{x( \tau  )}  \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau .$$  
 
 
  
 +
Bitte beachten Sie:
 +
*Alle Größen &ndash; auch die Zeit $t$ &ndash; sind normiert (dimensionslos) zu verstehen.
 +
*Die Zeitfunktionen &nbsp;$x(t)$,&nbsp; $h(t)$&nbsp; und &nbsp;$y(t)$&nbsp; können im Programm keine negativen Signalwerte annehmen.
 +
*Die ''absolute Dauer''&nbsp; eines Impulses &nbsp;$y(t)$&nbsp; ist der (zusammenhängende) Zeitbereich, für den &nbsp;$y(t) > 0$&nbsp; gilt.
 +
*Die ''äquivalente Dauer''&nbsp; eines Impulses ist über das flächengleiche Rechteck berechenbar.
 
   
 
   
 
==Theoretischer Hintergrund==
 
==Theoretischer Hintergrund==
 
<br>
 
<br>
===Der Huffman–Algorithmus===
+
===Faltung im Zeitbereich===
  
Wir setzen voraus, dass die Quellensymbole&nbsp; $q_\nu$&nbsp; einem Alphabet&nbsp; $\{q_μ\} = \{$ $\rm A$, $\rm B$ , $\rm C$ , ...$\}$&nbsp; mit dem Symbolumfang&nbsp; $M$&nbsp; entstammen und statistisch voneinander unabhängig seien. Beispielsweise gelte für den Symbolumfang&nbsp; $M = 8$:
+
Der&nbsp; [[Signaldarstellung/Faltungssatz_und_Faltungsoperation|Faltungssatz]]&nbsp; ist mit das wichtigste Gesetz der Fouriertransformation. Wir betrachten zunächst den Faltungssatz im Zeitbereich und setzen voraus, dass die Spektren zweier Zeitfunktionen&nbsp; $x_1(t)$&nbsp; und&nbsp; $x_2(t)$&nbsp; bekannt sind:
 
   
 
   
:$$\{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm}, \boldsymbol{\rm B}\hspace{0.05cm}, \boldsymbol{\rm C}\hspace{0.05cm}, \boldsymbol{\rm D}\hspace{0.05cm}, \boldsymbol{\rm E}\hspace{0.05cm}, \boldsymbol{\rm F}\hspace{0.05cm}, \boldsymbol{\rm G}\hspace{0.05cm}, \boldsymbol{\rm H}\hspace{0.05cm}
+
:$$X_1 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}x_1( t ),\quad X_2 ( f )\hspace{0.1cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.1cm}x_2 ( t ).$$
\}\hspace{0.05cm}.$$
 
  
[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]&nbsp; hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen zur Informationstheorie – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.
+
Dann gilt für die Zeitfunktion des Produktes&nbsp; $X_1(f) \cdot X_2(f)$:
Dieser&nbsp; ''Huffman–Algorithmus''&nbsp; soll ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt:&nbsp; Für die Codesymbole gelte stets&nbsp; $c_ν ∈ \{$'''0''', '''1'''$\}$. Hier ist die Vorgehensweise:
 
  
 +
:$$X_1 ( f ) \cdot X_2 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}\int_{ - \infty }^{ + \infty } {x_1 ( \tau  )}  \cdot x_2 ( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$
 +
 +
Hierbei ist&nbsp; $\tau$&nbsp; eine formale Integrationsvariable mit der Dimension einer Zeit.
  
# &nbsp; Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
+
{{BlaueBox|TEXT= 
# &nbsp; Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
+
$\text{Definition:}$&nbsp; Die obige Verknüpfung der Zeitfunktion&nbsp; $x_1(t)$&nbsp; und&nbsp; $x_2(t)$&nbsp; bezeichnet man als&nbsp; '''Faltung'''&nbsp; und stellt diesen Funktionalzusammenhang mit einem Stern dar:
# &nbsp; Man wiederhole&nbsp; '''(1)'''&nbsp; und&nbsp; '''(2)''', bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
+
# &nbsp; Man codiert die wahrscheinlichere Symbolmenge mit&nbsp; '''1'''&nbsp; und die andere Menge mit&nbsp; '''0'''.
+
:$$x_{\rm{1} } (t) * x_{\rm{2} } (t) = \int_{ - \infty }^{ + \infty } {x_1 ( \tau  ) }  \cdot x_2 ( {t - \tau } ) \hspace{0.1cm}{\rm d}\tau.$$
# &nbsp; Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen gemäß den Wahrscheinlichkeiten mit&nbsp; '''1'''&nbsp; bzw.&nbsp; '''0'''.
 
  
 +
Damit lässt sich obige Fourierkorrespondenz auch wie folgt schreiben:
  
{{GraueBox|TEXT=
+
:$$X_1 ( f ) \cdot X_2 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}{ {x} }_{\rm{1} } ( t ) * { {x} }_{\rm{2} } (t ).$$
$\text{Beispiel 1:}$&nbsp; Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die&nbsp; $M = 6$&nbsp; Symbole &nbsp;$\rm A$, ... , &nbsp;$\rm F$&nbsp;  schon nach ihren Wahrscheinlichkeiten geordnet sind:
 
 
:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
 
p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
 
\hspace{0.05cm}.$$
 
  
Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen <br>(resultierende Wahrscheinlichkeiten in Klammern):
+
[[Signaldarstellung/Faltungssatz_und_Faltungsoperation#Beweis_des_Faltungssatzes|$\text{Beweis}$]]}}
:1. &nbsp; $\rm A$ (0.30), $\rm B$ (0.24), $\rm C$ (0.20), $\rm EF$ (0.14), $\rm D$ (0.12),
 
:2. &nbsp; $\rm A$ (0.30), $\rm EFD$ (0.26), $\rm B$ (0.24), $\rm C$ (0.20),
 
:3. &nbsp; $\rm BC$ (0.44), $\rm A$ (0.30), $\rm EFD$ (0.26),
 
:4. &nbsp; $\rm AEFD$ (0.56), $\rm BC$ (0.44),
 
:5. &nbsp; Root $\rm AEFDBC$ (1.00).
 
Rückwärts &ndash; alsogemäß den Schritten&nbsp; '''(5)'''&nbsp; bis&nbsp; '''(1)'''&nbsp; &ndash; erfolgt dann die Zuordnung zu Binärsymbolen. Ein&nbsp; '''x'''&nbsp; weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen:
 
:5. &nbsp; $\rm AEFD$ → '''1x''', &nbsp; &nbsp;  $\rm BC$ → '''0x''',
 
:4. &nbsp; $\underline{\rm A}$  → '''<u>11</u>''', &nbsp; &nbsp;  $\rm EFD$ → '''10x''',
 
:3. &nbsp; $\underline{\rm B}$ → '''<u>01</u>''', &nbsp; &nbsp; $\underline{\rm C}$ → '''<u>00</u>''',
 
:2. &nbsp; $\rm EF$ → '''101x''',  &nbsp; &nbsp; $\underline{\rm D}$ → '''<u>100</u>''',
 
:1. &nbsp; $\underline{\rm E}$ → '''<u>1011</u>''',  &nbsp; &nbsp; $\underline{\rm F}$ → '''<u>1010</u>'''.
 
Die Unterstreichungen markieren die endgültige Binärcodierung.}}
 
  
  
+
''Anmerkung'': &nbsp; Die Faltung ist&nbsp; '''kommutativ'''  &nbsp; ⇒  &nbsp; Die Reihenfolge der Operanden ist vertauschbar: &nbsp;  ${ {x}}_{\rm{1}} ( t ) * { {x}}_{\rm{2}} (t ) ={ {x}}_{\rm{2}} ( t ) * { {x}}_{\rm{1}} (t ) $.
===Zum Begriff „Entropiecodierung”=== 
 
  
Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:
 
 
 
:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
 
p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
 
\hspace{0.05cm};$$
 
  
:$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm}
+
[[Datei:P_ID579__Sig_T_3_4_S1_neu.png|right|frame|Zur Berechnung von Signal und Spektrum am LZI&ndash;Ausgang]]
\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm}
+
{{GraueBox|TEXT= 
\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm}
+
$\text{Beispiel 1:}$&nbsp; Ein jedes lineare zeitinvariante (LZI-) System kann sowohl durch den Frequenzgang&nbsp; $H(f)$&nbsp; als auch durch die Impulsantwort&nbsp; $h(t)$&nbsp; beschrieben werden, wobei der Zusammenhang zwischen diesen beiden Systemgrößen ebenfalls durch die Fouriertransformation gegeben ist.
\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$
 
  
Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole &nbsp;$(\rm E$ und $\rm F)$&nbsp; mit vier Bit codiert.
+
Legt man an den Eingang ein Signal&nbsp; $x(t)$&nbsp; mit dem Spektrum&nbsp; $X(f)$&nbsp; an, so gilt für das Spektrum des Ausgangssignals:
 
 
Die mittlere Codewortlänge ergibt sich damit zu
 
 
   
 
   
:$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2  + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/Quellensymbol}
+
:$$Y(f) = X(f) \cdot H(f)\hspace{0.05cm}.$$
\hspace{0.05cm}.$$
 
 
 
Aus dem Vergleich mit der Quellenentropie
 
:$$H = -\big [0.3 \cdot {\rm log_2}\hspace{0.1cm}(0.3) + 0.24 \cdot {\rm log_2}\hspace{0.1cm}(0.24)
 
+ 0.2 \cdot {\rm log_2}\hspace{0.1cm}(0.2)+ 0.12 \cdot {\rm log_2}\hspace{0.1cm}(0.12)
 
+ 0.1 \cdot {\rm log_2}\hspace{0.1cm}(0.1)+ 0.04 \cdot {\rm log_2}\hspace{0.1cm}(0.04)
 
\big ]= 2.365 \ \rm bit/Quellensymbol$$
 
erkennt man die Effizienz der Huffman–Codierung.
 
 
 
  
{{GraueBox|TEXT=
+
Mit dem Faltungssatz ist es nun möglich, das Ausgangssignal auch direkt im Zeitbereich zu berechnen:
$\text{Beispiel 2:}$&nbsp; Wären die Symbolwahrscheinlichkeiten
 
 
   
 
   
:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm}
+
:$$y( t ) = x(t) * h( t ) = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm}{x( \tau  )}  \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm} {h( \tau  )} \cdot x( {t - \tau } )\hspace{0.1cm}{\rm d}\tau = h(t) * x( t ).$$
p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16
 
\hspace{0.05cm},$$
 
  
so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:
+
Aus dieser Gleichung geht nochmals hervor, dass die Faltungsoperation&nbsp; ''kommutativ''&nbsp; ist.}}
 
:$$H =  3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4)  + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
 
:$$L_{\rm M}  =  3 \cdot 1/4 \cdot 2  + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/Quellensymbol}
 
\hspace{0.05cm}.$$}}
 
  
  
Aus dieser Eigenschaft&nbsp; $L_{\rm M} = H +\varepsilon$&nbsp; mit&nbsp; $\varepsilon = 0$&nbsp; bei geeigneten Auftrittswahrscheinlichkeiten erklärt sich der Begriff '''Entropiecodierung''':
+
===Faltung im Frequenzbereich===
  
::Man versucht bei dieser Form von Quellencodierung, die Länge&nbsp; $L_μ$&nbsp; der Binärfolge (bestehend aus Nullen und Einsen) für das Symbol&nbsp; $q_μ$&nbsp; gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit&nbsp; $p_μ$&nbsp; anzupassen:
+
Die Dualität zwischen Zeit– und Frequenzbereich erlaubt auch Aussagen hinsichtlich des Spektrums eines Produktsignals:
 
   
 
   
::$$L_{\mu} =  {\rm log}_2\hspace{0.1cm}(1/p_{\mu} ) \hspace{0.05cm}.$$
+
:$$x_1 ( t ) \cdot x_2 ( t )\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\,X_1 (f) * X_2 (f) \int_{ - \infty }^{ + \infty } {X_1 ( \nu  )} \cdot X_2 ( {f - \nu })\hspace{0.1cm}{\rm d}\nu.$$
  
Da $L_μ$ im Gegensatz zu $\log_2(1/ p_μ$) ganzzahlig ist, gelingt dies nicht immer.
+
Dieses Resultat lässt sich ähnlich wie der&nbsp; [[Applets:Zur_Verdeutlichung_der_grafischen_Faltung#Faltung_im_Zeitbereich|Faltungssatz im Zeitbereich]]&nbsp; beweisen. Die Integrationsvariable&nbsp; $\nu$&nbsp; hat aber nun die Dimension einer Frequenz.
  
Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten&nbsp; $p_μ$&nbsp; in der Form&nbsp; $2^{–k}$&nbsp; mit&nbsp; $k = 1, 2, 3,$ ...  dargestellt werden können.  
+
[[Datei:P_ID580__Sig_T_3_4_S2_neu.png|right|frame|Faltung im Frequenzbereich]]
*In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; exakt mit der Quellenentropie&nbsp; $H$&nbsp; überein &nbsp;$(\varepsilon = 0$, siehe&nbsp; $\text{Beispiel 2}$).
+
{{GraueBox|TEXT= 
*Nach dem [[Informationstheorie/Allgemeine_Beschreibung#Quellencodierungstheorem|Quellencodierungstheorem]] gibt es keinen (decodierbaren) Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt.
+
$\text{Beispiel 2:}$&nbsp; Die&nbsp; [[Modulationsverfahren/Zweiseitenband-Amplitudenmodulation#Beschreibung_im_Zeitbereich|Zweiseitenband-Amplitudenmodulation]]&nbsp; (ZSB-AM) ohne Träger wird durch das skizzierte Modell beschrieben.
 +
*Bei der Zeitbereichsdarstellung (blau) ergibt sich das modulierte Signal&nbsp; $s(t)$&nbsp; als das Produkt aus dem Nachrichtensignal&nbsp; $q(t)$&nbsp; und dem (normierten) Trägersignal&nbsp; $z(t)$.
 +
*Nach dem Faltungssatz folgt daraus für den Frequenzbereich (rot), dass das Ausgangsspektrum&nbsp; $S(f)$&nbsp; gleich dem Faltungsprodukt aus&nbsp; $Q(f)$&nbsp; und&nbsp; $Z(f)$&nbsp; ist.}}
  
  
{{BlaueBox|TEXT=
+
===Faltung einer Funktion mit einer Diracfunktion===
$\text{Merke:}$&nbsp;
 
Es gibt keinen präfixfreien (⇒ sofort decodierbaren) Code, der allein unter Ausnutzung der Auftrittswahrscheinlichkeiten zu einer kleineren mittleren Codewortlänge&nbsp; $L_{\rm M}$&nbsp; führt als der Huffman–Code. &nbsp; '''In diesem Sinne ist der Huffman–Code optimal'''.}}
 
  
+
Sehr einfach wird die Faltungsoperation, wenn einer der beiden Operanden eine&nbsp; [[Signaldarstellung/Gleichsignal_-_Grenzfall_eines_periodischen_Signals#Diracfunktion_im_Frequenzbereich|Diracfunktion]]&nbsp; ist. Dies gilt für die Faltung im Zeit– und im Frequenzbereich gleichermaßen.
===Darstellung des Huffman–Codes als Baumdiagramm===
 
Häufig wird zur Konstruktion des Huffman–Codes eine&nbsp; '''Baumstruktur'''&nbsp; verwendet. Für das bisher betrachtete Beispiel zeigt diese die folgende Grafik:
 
  
[[Datei:P_ID2418__Inf_T_2_3_S3_neu.png|frame|Baumdarstellung  der Huffman–Codierung für das&nbsp; $\text{Beispiel 1}$]]
+
Wir betrachten beispielhaft die Faltung einer Funktion&nbsp; $x_1(t)$&nbsp; mit der Funktion
 +
 +
:$$x_2 ( t ) = \alpha  \cdot \delta ( {t - T} ) \quad \circ\,\!\!\!-\!\!\!-\!\!\!-\!\!\bullet \quad X_2 ( f )= \alpha \cdot  {\rm{e}}^{ - {\rm{j}}\hspace{0.03cm}2\hspace{0.03cm}{\rm{\pi }}\hspace{0.01cm}f\hspace{0.01cm}T}.$$
  
Man erkennt:
+
Für die Spektralfunktion des Signals&nbsp; $y(t) = x_1(t) \ast x_2(t)$&nbsp; gilt dann:
*Bei jedem Schritt des Huffman–Algorithmus werden die beiden Zweige mit den jeweils kleinsten Wahrscheinlichkeiten zusammengefasst.
+
*Der Knoten im ersten Schritt fasst die zwei Symbole&nbsp; $\rm E$&nbsp; und&nbsp; $\rm F$&nbsp; mit den aktuell kleinsten Wahrscheinlichkeiten zusammen. Dieser Knoten ist mit&nbsp; $p_{\rm E} + p_{\rm F} = 0.14$&nbsp; beschriftet.
+
:$$Y( f ) = X_1 ( f ) \cdot X_2 ( f ) = X_1 ( f ) \cdot  \alpha  \cdot {\rm{e}}^{ - {\rm{j}}\hspace{0.03cm}2\hspace{0.03cm}{\rm{\pi }}\hspace{0.01cm}f\hspace{0.01cm}T} .$$
*Der vom Symbol mit der kleineren Wahrscheinlichkeit &nbsp;$($hier $\rm F)$&nbsp; zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  &nbsp;$($für $\rm E)$&nbsp; rot.
 
  
 
+
Die komplexe Exponentialfunktion führt zur Verschiebung um&nbsp; $T$ &nbsp; &rArr; &nbsp; [[Signaldarstellung/Gesetzm%C3%A4%C3%9Figkeiten_der_Fouriertransformation#Verschiebungssatz|Verschiebungssatz]], der Faktor&nbsp; $\alpha$&nbsp; zu einer Dämpfung&nbsp; $(\alpha < 1)$&nbsp; bzw. einer Verstärkung &nbsp;$(\alpha > 1)$. Daraus folgt:
Nach fünf Schritten ist man bei der Baumwurzel („Root”) mit der Gesamtwahrscheinlichkeit&nbsp; $1.00$&nbsp; angelangt.
 
 
 
Verfolgt man nun den Verlauf von der Wurzel (in obiger Grafik mit gelber Füllung) zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen. Mit den Zuordnungen „rot” &nbsp; → &nbsp; '''1''' und „blau” &nbsp; → &nbsp; '''0''' ergibt sich beispielsweise von der Wurzel zu Symbol
 
* $\rm A$:  &nbsp;  rot, rot  →  '''11''',
 
*$\rm B$:  &nbsp; blau, rot  →  '''01''',
 
*$\rm C$:  &nbsp; blau, blau  →  '''00''',
 
*$\rm D$:  &nbsp; rot, blau, blau  →  '''100''',
 
*$\rm E$:  &nbsp; rot, blau, rot, rot  →  '''1011''',
 
*$\rm F$:  &nbsp; rot, blau, rot, blau  →  '''1010'''.
 
 
 
 
 
Die (einheitliche) Zuordnung „rot” &nbsp; → &nbsp; '''0''' und „blau” &nbsp; → &nbsp; '''1''' würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen.
 
 
 
{{GraueBox|TEXT=
 
$\text{Beispiel 3:}$&nbsp;
 
Die folgende Grafik zeigt die Huffman–Codierung von &nbsp;$49$&nbsp; Symbolen&nbsp; $q_ν ∈ \{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$, $\rm E$, $\rm F$ $\}$&nbsp; mit der im letzten Abschnitt hergeleiteten Zuordnung. Die binäre Codesymbolfolge weist die mittlere Codewortlänge $L_{\rm M}\hspace{0.05cm}' = 125/49 = 2.551$ auf. Die Farben dienen ausschließlich zur besseren Orientierung.
 
 
 
[[Datei:Inf_T_2_3_S3b_version2.png|center|frame|Beispielfolgen bei Huffman–Codierung]]
 
 
 
Aufgrund der kurzen Quellensymbolfolge&nbsp; $(N = 49)$&nbsp; weichen die Auftrittshäufigkeiten&nbsp; $h_{\rm A}$, ... , $h_{\rm F}$&nbsp; der simulierten Folgen signifikant von den vorgegebenen Wahrscheinlichkeiten&nbsp; $p_{\rm A}$, ... , $p_{\rm F}$&nbsp; ab:
 
 
 
:$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},\hspace{0.4cm}p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$
 
 
   
 
   
:$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx 0.184 \hspace{0.05cm},\hspace{0.6cm}p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx  0.143 \hspace{0.05cm},$$
+
:$$x_1 (t) * x_2 (t) = \alpha \cdot x_1 ( {t - T} ).$$
  
:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},\hspace{0.6cm}p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102
+
{{BlaueBox|TEXT=
\hspace{0.05cm}.$$
+
$\text{In Worten: }$&nbsp; Die Faltung einer beliebigen Funktion mit einer Diracfunktion bei&nbsp;  $t = T$&nbsp; ergibt die um&nbsp; $T$&nbsp; nach rechts verschobene Funktion, wobei noch die Gewichtung der Diracfunktion durch den Faktor&nbsp; $\alpha$&nbsp; zu berücksichtigen ist.}}
  
Damit ergibt sich ein etwas größerer Entropiewert:
 
 
 
:$$H \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \,{\rm bit/Quellensymbol}\hspace{0.3cm}
 
\Rightarrow \hspace{0.3cm}
 
H\hspace{0.05cm}' \ ({\rm bez\ddot{u}glich }\hspace{0.15cm}h_{\mu}) = 2.451 \,{\rm bit/Quellensymbol}
 
\hspace{0.05cm}.$$
 
  
Würde man den Huffman–Code mit diesen „neuen” Wahrscheinlichkeiten&nbsp; $h_{\rm A}$, ... , $h_{\rm F}$&nbsp; bilden, so ergäben sich folgende Zuordnungen:
+
{{GraueBox|TEXT= 
+
$\text{Beispiel 3:}$&nbsp; Ein Rechtecksignal&nbsp; $x(t)$&nbsp; wird durch ein LZI-System um eine Laufzeit&nbsp; $\tau = 3\,\text{ ms}$&nbsp; verzögert und um den Faktor&nbsp; $\alpha = 0.5$&nbsp; gedämpft.
:&nbsp; &nbsp; &nbsp;$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''11'''$\hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''00'''$\hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''101'''$\hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''010'''$\hspace{0.05cm},\hspace{0.2cm}
 
\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm}$'''011'''$\hspace{0.05cm}.$
 
  
Nun würden nur&nbsp; $\rm A$&nbsp; und&nbsp; $\rm C$&nbsp; mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit.
+
[[Datei:P_ID522__Sig_T_3_4_S3_neu.png|center|frame|Faltung eines Rechtecks mit einer Diracfunktion]]
*Die Codesymbolfolge hätte dann eine Länge von&nbsp; $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$&nbsp; Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.
 
*Die mittlere Codewortlänge wäre dann $L_{\rm M}\hspace{0.05cm}' = 122/49 ≈ 2.49 \ \rm  bit/Quellensymbol$ anstelle von $L_{\rm M}\hspace{0.05cm}'≈ 2.55 \ \rm  bit/Quellensymbol$.}}
 
  
 +
Verschiebung und Dämpfung erkennt man sowohl am Ausgangssignal&nbsp; $y(t)$&nbsp; als auch an der Impulsantwort&nbsp; $h(t)$.}}
  
{{BlaueBox|TEXT=
 
$\text{Fazit:}$&nbsp;
 
Dieses Beispiel lässt sich wie folgt interpretieren:
 
*Die Huffman–Codierung lebt von der (genauen) Kenntnis der Symbolwahrscheinlichkeiten. Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; oft nur unwesentlich größer als die Quellenentropie&nbsp; $H$.
 
*Insbesondere aber bei kleinen Dateien kann es zu Abweichungen zwischen den (erwarteten) Symbolwahrscheinlichkeiten&nbsp; $p_μ$&nbsp; und den (tatsächlichen) Häufigkeiten&nbsp; $h_μ$&nbsp; kommen. Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten&nbsp; $(h_μ)$&nbsp; basiert.
 
*In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden. Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann. Bei kleinen Dateien lohnt sich dieser Aufwand nicht.}}
 
  
 +
===Grafische Faltung===
  
 +
In diesem Applet wird von folgender Faltungsoperation ausgegangen:
 +
[[Datei:P_ID2723__Sig_T_3_4_programm.png|right|frame|Bildschirmabzug des Programms „Grafische Faltung” (frühere Version)]]
 +
:$$y(t) = x (t) * h (t) = \int_{ - \infty }^{ + \infty } {x ( \tau  )}  \cdot h ( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$
  
===Der Shannon&ndash;Fano–Algorithmus ===
+
Die Lösung des Faltungsintegrals soll auf grafischem Wege erfolgen. Es wird vorausgesetzt, dass&nbsp; $x(t)$&nbsp; und&nbsp; $h(t)$&nbsp; zeitkontinuierliche Signale sind.
  
1949 &ndash; also bereits drei Jahre vor David A. Huffman &ndash; haben&nbsp; [https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; und &nbsp;[https://de.wikipedia.org/wiki/Robert_Fano Robert Fano]&nbsp; einen ähnlichen, auf ''Entropiecodierung'' basierenden Algorithmus angegeben, nämlich:
 
:# &nbsp; Man ordne die Quellensymbole nach fallenden Auftrittswahrscheinlichkeiten (identisch mit Huffman).
 
:# &nbsp; Man teile die sortierten Zeichen in zwei möglichst gleichwahrscheinliche Gruppen ein.
 
:# &nbsp; Der ersten Gruppe wird das Binärsymbol &nbsp;'''1'''&nbsp; zugeordnet, der zweiten die&nbsp; '''0'''&nbsp; (oder umgekehrt).
 
:# &nbsp; Sind in einer Gruppe mehr als ein Zeichen, so ist auf diese der Algorithmus rekursiv anzuwenden.
 
  
{{GraueBox|TEXT=
+
Dann sind die folgenden Schritte erforderlich:
$\text{Beispiel 4:}$&nbsp; Wir gehen wie im&nbsp; [https://www.lntwww.de/Applets:Huffman-_und_Shannon-Fano-Codierung#Der_Huffman.E2.80.93Algorithmus Einführungsbeispiel]&nbsp; für den Huffman–Algorithmus von $M = 6$ Symbolen und den folgenden Wahrscheinlichkeiten aus:
+
#&nbsp; Die&nbsp; '''Zeitvariablen'''&nbsp; der beiden Funktionen&nbsp; '''ändern''': &nbsp; <br>&nbsp; &nbsp; $x(t) \to x(\tau)$, &nbsp; $h(t) \to h(\tau)$.
+
#&nbsp; Zweite '''Funktion spiegeln''': &nbsp; $h(\tau) \to h(-\tau)$.
:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
+
#&nbsp; Gespiegelte '''Funktion''' um&nbsp; $t$&nbsp; '''verschieben''': &nbsp; $h(-\tau) \to h(t-\tau)$.
p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
+
#&nbsp; '''Multiplikation''' der beiden Funktionen&nbsp; $x(\tau)$&nbsp; und&nbsp; $h(t-\tau)$.
\hspace{0.05cm}.$$
+
#&nbsp; '''Integration'''&nbsp; über das Produkt bezüglich&nbsp; $\tau$&nbsp; in den Grenzen von&nbsp; $-\infty$&nbsp; bis&nbsp; $+\infty$.
  
Dann lautet der Shannon–Fano–Algorithmus:
 
:# &nbsp; $\rm AB$ → '''1'''x (Wahrscheinlichkeit 0.54), &nbsp; $\rm CDEF$ → '''0'''x (Wahrscheinlichkeit 0.46),
 
:# &nbsp; $\underline{\rm A}$ → '''<u>11</u>''' (Wahrscheinlichkeit 0.30),  &nbsp;  $\underline{\rm B}$ ⇒ '''<u>10</u>''' (Wahrscheinlichkeit 0.24),
 
:# &nbsp; $\underline{\rm C}$ → '''<u>01</u>''' (Wahrscheinlichkeit 0.20), &nbsp;  $\rm DEF$ → '''00'''x, (Wahrscheinlichkeit 0.26),
 
:# &nbsp; $\underline{\rm D}$ → '''<u>001</u>''' (Wahrscheinlichkeit 0.12),  &nbsp;  $\rm EF$ → '''000'''x (Wahrscheinlichkeit 0.14),
 
:# &nbsp; $\underline{\rm E}$ → '''<u>0001</u>''' (Wahrscheinlichkeit 0.10), &nbsp;  $\underline{\rm F}$ → '''<u>0000</u>'''  (Wahrscheinlichkeit 0.04).
 
  
''Anmerkungen'':
+
Da die Faltung kommutativ ist, kann anstelle von&nbsp; $h(\tau)$&nbsp; auch&nbsp; $x(\tau)$&nbsp; gespiegelt werden.
*Ein&nbsp; $\rm x$&nbsp; weist wieder darauf hin, dass in nachfolgenden Codierschritten noch Bits hinzugefügt werden müssen.
 
*Es ergibt sich hier zwar eine andere Zuordnung als bei der&nbsp; [https://www.lntwww.de/Applets:Huffman-_und_Shannon-Fano-Codierung#Der_Huffman.E2.80.93Algorithmus Huffman–Codierung], aber genau die gleiche mittlere Codewortlänge:
 
 
 
:$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$}}
 
  
 +
<br><br>
 +
Nebenstehende Grafik zeigt einen Bildschirmabzug einer älteren Version des vorliegenden Applets.
 +
<br><br>
  
Mit den Wahrscheinlichkeiten entsprechend dem $\text{Beispiel 4}$ führt der Shannon–Fano–Algorithmus zur gleichen mittleren Codewortlänge wie die Huffman–Codierung. Ebenso sind bei vielen (eigentlich: den meisten) anderen Wahrscheinlichkeitsprofilen Huffman und Shannon–Fano aus informationstheoretischer Sicht äquivalent.
 
  
Es gibt aber durchaus Fälle, bei denen sich beide Verfahren hinsichtlich der (mittleren) Codewortlänge unterscheiden, wie das folgende Beispiel zeigt.
+
[[Datei:P_ID582__Sig_T_3_4_S4_neu.png|right|frame|Beispiel einer Faltungsoperation: <br>Sprungfunktion gefaltet mit Exponentialfunktion]]
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 4:}$&nbsp;
 +
Die Vorgehensweise bei der grafischen Faltung wird nun anhand eines ausführlichen Beispiels erklärt:
 +
*Am Eingang eines Filters liege eine Sprungfunktion&nbsp; $x(t) = \gamma(t)$&nbsp; an.
 +
*Die Impulsantwort des RC-Tiefpasses sei&nbsp; $h( t ) = {1}/{T} \cdot {\rm{e} }^{ - t/T}.$
  
{{GraueBox|TEXT=
 
$\text{Beispiel 2:}$&nbsp; Wir betrachten $M = 5$ Symbole mit folgenden Wahrscheinlichkeiten:
 
 
 
:$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm}
 
p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13 \hspace{0.3cm}
 
\Rightarrow\hspace{0.3cm}  H = 2.19\,{\rm bit/Quellensymbol}
 
\hspace{0.05cm}. $$
 
  
[[Datei:P_ID2461__Inf_T_2_4_S1_ganz_neu.png|center|frame|Baumstrukturen nach Shannon–Fano bzw. Huffman]]
+
Die Grafik zeigt rot das Eingangssignal&nbsp;  $x(\tau)$, blau die Impulsantwort&nbsp; $h(\tau)$ und grau das Ausgangssignal&nbsp; $y(\tau)$.  
 +
Die Zeitachse ist bereits in&nbsp; $\tau$&nbsp; umbenannt.
  
Die Grafik zeigt die jeweiligen Codebäume für Shannon–Fano (links) bzw. Huffman (rechts). Die Ergebnisse lassen sich wie folgt zusammenfassen:
+
Das Ausgangssignal kann zum Beispiel nach folgender Gleichung berechnet werden:
* Der Shannon–Fano–Algorithmus führt zum Code $\rm A$ → '''11''', &nbsp; $\rm B$ → '''10''', &nbsp; $\rm C$ → '''01''', &nbsp; $\rm D$ → '''001''', &nbsp; $\rm E$ → '''000''' und damit zur mittleren Codewortlänge
 
 
   
 
   
:$$L_{\rm M} = (0.38 + 0.18 + 0.16) \cdot 2 + (0.15 + 0.13) \cdot 3 = 2.28\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
+
:$$y(t) = h(t) * x(t) = \int_{ - \infty }^{ + \infty } {h( \tau  )\cdot x( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$
  
*Mit &bdquo;Huffman&rdquo; erhält man $\rm A$ → '''1''', &nbsp; $\rm B$ → '''001''', &nbsp; $\rm C$ → '''010''', &nbsp; $\rm D$ → '''001''', &nbsp; $\rm E$ → '''000''' und eine etwas kleinere mittlere Codewortlänge:
+
Noch einige Anmerkungen zur grafischen Faltung:
+
*Der Ausgangswert bei&nbsp; $t = 0$&nbsp; ergibt sich, indem man das Eingangssignal&nbsp; $x(\tau)$&nbsp; spiegelt, dieses gespiegelte Signal&nbsp; $x(-\tau)$&nbsp; mit der Impulsantwort&nbsp; $h(\tau)$&nbsp; multipliziert und darüber integriert.
:$$L_{\rm M} = 0.38 \cdot 1 + (1-0.38) \cdot 3 = 2.24\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $$
+
*Da es hier kein Zeitintervall gibt, bei dem sowohl die blaue Kurve&nbsp; $h(\tau)$&nbsp; und gleichzeitig auch die rot gestrichelte Spiegelung&nbsp; $x(-\tau)$&nbsp; ungleich Null ist, folgt daraus&nbsp; $y(t=0)=0$.
 +
*Für jeden anderen Zeitpunkt&nbsp; $t$&nbsp; muss das Eingangssignal verschoben werden  &nbsp; ⇒  &nbsp; $x(t-\tau)$, beispielsweise entsprechend der grün gestrichelten Kurve für&nbsp; $t=T$.
 +
*Da in diesem Beispiel auch&nbsp; $x(t-\tau)$&nbsp; nur die Werte&nbsp; $0$&nbsp; oder&nbsp; $1$&nbsp; annehmen kann, wird die Integration &nbsp;$($allgemein von&nbsp; $\tau_1$&nbsp; bis&nbsp; $\tau_2)$&nbsp; einfach und man erhält mit&nbsp; $\tau_1 = 0$&nbsp;  und&nbsp; $\tau_2 = t$&nbsp;:
 +
:$$y( t) = \int_0^{\hspace{0.05cm} t} {h( \tau)}\hspace{0.1cm} {\rm d}\tau = \frac{1}{T}\cdot\int_0^{\hspace{0.05cm} t} {{\rm{e}}^{ - \tau /T } }\hspace{0.1cm} {\rm d}\tau = 1 - {{\rm{e}}^{ - t /T } }.$$
  
*Es gibt keinen Satz von Wahrscheinlichkeiten, bei denen Shannon–Fano ein besseres Ergebnis liefert als der Huffman–Algorithmus, der stets den bestmöglichen Entropiecodierer bereitstellt.
+
Die Skizze gilt für&nbsp; $t=T$&nbsp; und führt zum Ausgangswert&nbsp; $y(t=T) = 1 – 1/\text{e} \approx 0.632$.}}  
*Die Grafik zeigt zudem, dass die Algorithmen im Baumdiagramm in unterschiedlichen Richtungen vorgehen, nämlich einmal von der Wurzel zu den Einzelsymbolen (Shannon–Fano), zum anderen von den Einzelsymbolen zur Wurzel (Huffman).}}  
 
  
 +
 +
==Versuchsdurchführung==
 +
<br>
 +
*Wählen Sie zunächst die Nummer&nbsp; $(1,\ 2, \text{...})$&nbsp; der zu bearbeitenden Aufgabe. Die Nummer&nbsp; $0$&nbsp; entspricht einem &bdquo;Reset&rdquo;:&nbsp; Gleiche Einstellung wie beim Programmstart.
 +
*Eine Aufgabenbeschreibung wird angezeigt.&nbsp; Die Parameterwerte sind angepasst.&nbsp; Lösung nach Drücken von &bdquo;Musterlösung&rdquo;.
 +
*Sowohl das Eingangssignal sind normiert auf&nbsp; $\pm 1$&nbsp; zu verstehen.&nbsp; Auch die ausgegebenen Leistungen sind normierte Größen.
  
  
==Versuchsdurchführung==
 
 
[[Datei:Exercises_Entropie.png|right]]
 
*Wählen Sie zunächst die Aufgabennummer.
 
*Eine Aufgabenbeschreibung wird angezeigt.
 
*Alle Parameter sind angepasst.
 
*Alle Grafiken (Baumdiagramm, Symbolfolgen) sind aktualisiert.
 
*Ebenso die Ergebnisse &nbsp;$H, \ L_{\rm  M}$&nbsp; sowie&nbsp;$H\hspace{0.05cm}', \ L_{\rm  M}\hspace{0.05cm}'$.
 
*Musterlösung nach Drücken von &bdquo;Hide solution&rdquo;.
 
*Nummer &bdquo;0&rdquo;: &nbsp; Gleiche Einstellung wie beim Programmstart.
 
<br clear=all>
 
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(1)''' &nbsp; Wählen Sie die Quelle gemäß der Voreinstellung mit &nbsp;$M=8$ &nbsp; &rArr; &nbsp; Entropie $H=2.278$  (bit/Quellensymbol), Huffman-Codierung und &bdquo;Herleitung&rdquo;.
+
'''(1)''' &nbsp; Wählen Sie die Parameter gemäß Voreinstellung &nbsp;$\text{(Gaußimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 1;  \text{  Impulsantwort gemäß Tiefpass 2. Ordnung: }\Delta t_h= 1)$.
   
+
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  Interpretieren Sie die dargestellten Grafiken. Wie groß ist der maximale Ausgangswert &nbsp;$y_{\rm max}$? Zu welcher Zeit &nbsp;$t_{\rm max}$&nbsp; tritt dieser auf? }}
:Interpretieren Sie die Ergebnisse. Wie werden die Quellensymbole &nbsp;$\rm C$, &nbsp;$\rm D$&nbsp; und &nbsp;$\rm E$&nbsp; codiert? Wie groß ist die mittlere Codewortlänge &nbsp;$L_{\rm M}$? }}
 
  
::*&nbsp;Es ergibt sich folgende Zuordnung:&nbsp; $\rm C \ \to 1$,&nbsp; $\rm D \ \to 01100$,&nbsp; $\rm E \ \to 0010$. Die mittlere Codewortlänge ist &nbsp;$L_{\rm M}= 2.29$&nbsp; (bit/Quellensymbol)&nbsp;$>H$.
+
::*&nbsp;Nach Umbenennung: &nbsp;Eingangssignal&nbsp; $x(\tau)$ &nbsp; &rArr; &nbsp; rote Kurve,  &nbsp;Impulsantwort&nbsp; $h(\tau)$ &nbsp; &rArr; &nbsp; blaue Kurve, nach Spiegelung&nbsp; $h(-\tau)$ &nbsp; &rArr; &nbsp; grüne Kurve.
::*&nbsp;Erklärung:&nbsp; Im Baumdiagramm kommt man von der &bdquo;Root&rdquo; (gelber Kreis) zum Symbol &nbsp;$\rm E$&nbsp; über Blau &ndash; Blau &ndash; Rot &ndash; Blau. &bdquo;Blau&rdquo; steht für &nbsp;$0$&nbsp; und &bdquo;Rot&rdquo; für &nbsp;$1$.
+
::*&nbsp;Verschiebt man die grüne Kurve um&nbsp; $t$&nbsp; nach rechts, so erhält man $h(t-\tau)$. Das Ausgangssignal&nbsp; $y(t)$&nbsp; ergibt sich durch Multiplikation und Integration bzgl. $\tau$:
  
{{BlaueBox|TEXT=
+
:::$$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 .$$
'''(2)''' &nbsp; Wie unterscheiden sich bei sonst gleichen Einstellungen die Ergebnisse für &bdquo;Shannon&ndash;Fano&rdquo;? }}
+
::*&nbsp;Der Ausgangsimpuls &nbsp;$y(t)$&nbsp; ist im vorliegenden Fall unsymmetrisch;&nbsp; der maximale Ausgangswert &nbsp;$y_{\rm max}\approx 0.67$&nbsp; tritt bei &nbsp;$t_{\rm max}\approx 1.56$&nbsp; auf.  
 
 
::*&nbsp;Hier ergibt sich eine andere Zuordnung:&nbsp; $\rm C \ \to 1$,&nbsp; $\rm D \ \to 01010$,&nbsp; $\rm E \ \to 0100$. Trotzdem ist die mittlere Codewortlänge wieder &nbsp;$L_{\rm M}= 2.29$.
 
::*&nbsp;Erklärung:&nbsp; Im Graphen kommt man von der &bdquo;Root&rdquo; &nbsp;$\rm CAFBGEHD$&nbsp; zu &nbsp;$\rm E$&nbsp; über Blau &ndash; Rot &ndash; Blau &ndash; Blau. &bdquo;Blau&rdquo; steht wieder für &nbsp;$0$&nbsp; und &bdquo;Rot&rdquo; für &nbsp;$1$.  
 
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(3)''' &nbsp; Warum ist bei &bdquo;Huffman&rdquo; und &bdquo;Shannon&ndash;Fano&rdquo; trotz unterschiedlicher Zuordnung die mittlere Codewortlänge gleich?}}  
+
'''(2)''' &nbsp; Was ändert sich, wenn man die äquivalente Impulsdauer von&nbsp; $h(t)$&nbsp; auf &nbsp;$\Delta t_h= 1.5$&nbsp; erhöht? }}
  
::*&nbsp;In beiden Fällen wird &nbsp;$\rm C$&nbsp; mit einem Bit codiert, &nbsp;$\rm A$&nbsp; und &nbsp;$\rm F$&nbsp; mit drei Bit, &nbsp;$\rm B$, &nbsp;$\rm E$&nbsp; und &nbsp;$\rm G$&nbsp; mit vier Bit sowie &nbsp;$\rm D$&nbsp; und &nbsp;$\rm H$&nbsp; mit fünf Bit. Daraus folgt:&nbsp;  
+
::*&nbsp;$y_{\rm max}\approx 0.53$&nbsp; tritt nun bei &nbsp;$t_{\rm max}\approx 1.75$&nbsp; auf. Durch die ungünstigere (breitere) Impulsantwort wird der Eingangsimpuls stärker verformt.
::*&nbsp;$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$&nbsp; (bit/Quellensymbol)
+
::*&nbsp;Bei einem digitalen Nachrichtenübertragungssystem hätte dies stärkere Impulsinterenzen (&bdquo;Intersymbol Interference&rdquo;) zur Folge.
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(4)''' &nbsp; Wählen Sie &bdquo;Voreinstellung&rdquo; und &bdquo;Huffman&rdquo;. Wie ändern sich  die Ergebnisse für &bdquo;Simulation über 10000 Symbole&rdquo; &nbsp;$(H', \ L_{\rm M}\hspace{0.05cm}')$&nbsp; gegenüber &nbsp;$(H, \ L_{\rm M})$&nbsp; für $N \to \infty$?
+
'''(3)''' &nbsp; Wählen Sie nun den symetrischen &nbsp;$\text{Rechteckimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0$&nbsp; und die  &nbsp;$\text{Impulsantwort gemäß Spalt&ndash;Tiefpass: }\Delta t_h= 1$.  
 +
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp; Interpretieren Sie das Faltungsergebnis. Wie groß ist der maximale Ausgangswert &nbsp;$y_{\rm max}$? Zu welchen Zeiten ist &nbsp;$y(t)>0$? Beschreibt &nbsp;$h(t)$&nbsp; ein kausales System? }}
  
:Starten Sie jeweils zehn Simulationen. Welche Aussagen stimmen mit diesen Wahrscheinlichkeiten immer: &nbsp;$L_{\rm M}\hspace{0.05cm}' > L_{\rm M}$, &nbsp; &nbsp; $L_{\rm M}\hspace{0.05cm}' > H$,&nbsp; &nbsp; $L_{\rm M}\hspace{0.05cm}' > H'$?}}
+
::*&nbsp;Die Faltung zweier Rechtecke mit jeweiliger Dauer &nbsp;$1$&nbsp; ergibt ein Dreieck mit absoluter Dauer &nbsp;$2$&nbsp; &rArr; &nbsp; äquivalente Impulsdauer &nbsp;$\Delta t_y= 1$.  
 
+
::*&nbsp;$y(t)$&nbsp; ist im Bereich von &nbsp;$-0.5$&nbsp; bis &nbsp;$+1.5$&nbsp; von Null verschieden. Impulsmaximum &nbsp;$y_{\rm max} = 1$&nbsp; bei &nbsp;$t_{\rm max} = +0.5$.
::*&nbsp;Für die theoretischen Werte &nbsp;(also für &nbsp;$N \to \infty)$&nbsp; gilt immer &nbsp;$L_{\rm M} \ge H$. Außerdem wird für jede einzelne Simulation gelten:&nbsp; $L_{\rm M}\hspace{0.05cm}' \ge H'$.
+
::*&nbsp;$h(t)$&nbsp; beschreibt ein kausales System, da &nbsp;$h(t) \equiv 0$&nbsp; für &nbsp;$t < 0$&nbsp; &rArr; &nbsp; die &bdquo;Wirkung&rdquo; &nbsp;$y(t)$&nbsp; kommt nicht vor der &bdquo;Ursache&rdquo; &nbsp;$x(t)$.
::*&nbsp;Da bei jeder einzelnen Simulation &nbsp;$H'$&nbsp; größer, kleiner oder gleich &nbsp;$H$&nbsp; sein kann, ist aber &nbsp;$L_{\rm M}\hspace{0.05cm}' < H$&nbsp; durchaus möglich.
 
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(5)''' &nbsp; Wählen Sie nun die &bdquo;Quelle 3&rdquo; &nbsp;$(M=4, \ p_{\rm A}= p_{\rm B}=p_{\rm C}= p_{\rm D}=0.25)$&nbsp; und &bdquo;Huffman&rdquo;. Interpretieren Sie die Ergebnisse. Was wäre bei &bdquo;Shannon&ndash;Fano&rdquo;?}}
+
'''(4)''' &nbsp; Was ändert sich, wenn man die äquivalente Impulsdauer von&nbsp; $h(t)$&nbsp; auf &nbsp;$\Delta t_h= 2$&nbsp; erhöht? }}
  
::*&nbsp;Jedes Symbol wird durch zwei Bit dargestellt, so dass &nbsp;$L_{\rm M} = H = 2$&nbsp; (bit/Quellensymbol) ist. Die Simulation liefert auch immer &nbsp;$L_{\rm M}\hspace{0.05cm}' = 2$, auch für &nbsp;$H' < 2$.
+
::*&nbsp;Die Faltung zweier unterschiedlich breiter Rechtecke ergibt ein Trapez, hier zwischen &nbsp;$-0.5$&nbsp; und &nbsp;$+2.5$ &rArr; &nbsp; äquivalente Impulsdauer &nbsp;$\Delta t_y= 2$.
::*&nbsp;Gleiches gilt für &bdquo;Shannon&ndash;Fano&rdquo; trotz anderer Zuordnung:&nbsp; $\rm A \ \to 00$,&nbsp; $\rm B \ \to 01$,&nbsp; $\rm C \ \to 10$,&nbsp; $\rm D \ \to 11$ statt&nbsp; $\rm A \ \to 01$,&nbsp; $\rm B \ \to 00$,&nbsp; $\rm C \ \to 11$,&nbsp; $\rm D \ \to 10$.
+
::*&nbsp;Das Maximum &nbsp;$y_{\rm max} = 0.5$&nbsp; tritt im Bereich &nbsp;$0.5 \le t \le 1.5$ auf. Bezüglich der Kausalität ändert sich nichts.
::*&nbsp;Aber ganz klar ist: &nbsp; Quellencodierung macht bei redundanzfreier Quelle keinen Sinn, weder &bdquo;Huffman&rdquo; noch &bdquo;Shannon&ndash;Fano&rdquo;.  
 
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(6)''' &nbsp; Wählen Sie die  &bdquo;Quelle 4&rdquo; &nbsp;$(M=4, \ p_{\rm A}= 0.5, \ p_{\rm B}= 0.25, \ p_{\rm C}= p_{\rm D}=0.125)$. Warum gilt hier &nbsp;$L_{\rm M} = H = 1.75$&nbsp; (bit/Quellensymbol)? Interpretation. }}
+
'''(5)''' &nbsp; Wählen Sie nun den (unsymetrischen) &nbsp;$\text{Rechteckimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0.5$&nbsp; und die  &nbsp;$\text{ Impulsantwort eines Tiefpasses 1. Ordnung: }\Delta t_h= 1$.  
 +
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  Interpretieren Sie die Ergebnisse. Wie groß ist &nbsp;$y_{\rm max}$? Zu welchen Zeiten ist &nbsp;$y(t)>0$&nbsp;? Beschreibt &nbsp;$h(t)$&nbsp; ein kausales System? }}  
  
::*&nbsp;Sowohl bei &bdquo;Huffman&rdquo; als auch bei &bdquo;Shannon&ndash;Fano&rdquo; wird &nbsp;$\rm A$&nbsp; mit einem Bit codiert, &nbsp;$\rm B$&nbsp; mit zwei Bit sowie &nbsp;$\rm C$&nbsp; und &nbsp;$\rm D$&nbsp; mit drei Bit.  
+
::*&nbsp;$h(t)$&nbsp; hat für &nbsp;$t > 0$&nbsp; einen exponentiell abfallenden Verlauf. Für &nbsp;$t > 0$&nbsp; gilt stets &nbsp;$y(t) > 0$, aber die Signalwerte können sehr klein werden.  
::*&nbsp;Daraus folgt: &nbsp; $L_{\rm M}= 0.5 \cdot 1 + 0.25 \cdot 2 + 2 \cdot 0.125 \cdot 3 = H = 1.75$&nbsp; (bit/Quellensymbol). Es sind &bdquo;günstige Wahrscheinlichkeiten&rdquo; der Form &nbsp;$p = 2^{-k}$.
+
::*&nbsp;$y_{\rm max} = 0.63$&nbsp; tritt bei &nbsp;$t_{\rm max} = +1$ auf. Für &nbsp;$ t < t_{\rm max}$ ist der Verlauf exponentiell ansteigend, für &nbsp;$ t > t_{\rm max}$&nbsp; exponentiell abfallend.
::*&nbsp;Ohne eine &bdquo;Entropiecodierung&rdquo; nach Huffman oder Shannon&ndash;Fano würden alle vier Symbole mit zwei Bit dargestellt: &nbsp; $L_{\rm M}= 2$&nbsp; (bit/Quellensymbol).
+
::*&nbsp;Der Tiefpass 1. Ordnung kann mit einem Widerstand und einer Kapazität realisiert werden. Jedes realisierbare System  ist per se kausal.  
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(7)''' &nbsp; Wählen Sie nun &bdquo;Shannon&ndash;Fano&rdquo; und die &bdquo;Quelle 2&rdquo; &nbsp;$(M=3, \ p_{\rm A}= 0.34, \ p_{\rm B}= p_{\rm C} =0.33)$. Mit welchen Wahrscheinlichkeiten ergäbe sich &nbsp;$L_{\rm M} = H $? }}
+
'''(6)''' &nbsp; Wählen Sie wie in &nbsp;'''(3)'''&nbsp; die rechteckförmige Impulsantwort &nbsp;$\text{(Spalt&ndash;Tiefpass; }\Delta t_h= 1)$. Mit welchem &nbsp;$x(t)$&nbsp; ergibt sich das gleiche &nbsp;$y(t)$&nbsp; wie bei&nbsp; '''(5)'''?}}  
  
::*&nbsp;Die Ternärquelle ist nahezu redundanzfrei: &nbsp;$H \approx \log_2 \ 3 \approx 1.585$. Mit &nbsp; $\rm A \ \to 0$,&nbsp; $\rm B \ \to 10$,&nbsp;$\rm C \ \to 11$&nbsp; ist $L_{\rm M}= 1.66 > H$.  
+
::*&nbsp;Das Signal &nbsp;$y(t)$&nbsp; in &nbsp;'''(5)'''&nbsp; ergab sich als Faltung zwischen dem rechteckigen Eingang &nbsp;$x(t)$&nbsp; und der Exponentialfunktion &nbsp;$h(t)$.  
::*&nbsp;&bdquo;Günstige Wahrscheinlichkeiten&rdquo; wären zum Beispiel &nbsp;$p_{\rm A}= 0.5, \ p_{\rm B}= p_{\rm C}= 0.25$&nbsp; wie bei &bdquo;Quelle 1&rdquo;. Dann ist&nbsp; $L_{\rm M}= H = 1.5$&nbsp; (bit/Quellensymbol).
+
::*&nbsp;Da die Faltungsoperation kommutativ ist, ergibt sich das gleiche Ergebnis mit der Exponentialfunktion &nbsp;$x(t)$ und der Rechteckfunktion &nbsp;$h(t)$.
 +
::*&nbsp;Die richtige Einstellung für das Eingangssignal &nbsp;$x(t)$&nbsp; ist somit der  &nbsp;$\text{Exponentialimpuls: }A_x = 1, \ \Delta t_x= 1, \ \tau_x = 0$&nbsp;.
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(8)''' &nbsp; Wählen Sie &bdquo;Huffman&rdquo; und die  &bdquo;Quelle 5&rdquo; &nbsp;$(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 &bdquo;günstige Wahrscheinlichkeiten&rdquo;? }}
+
'''(7)''' &nbsp; Für den Rest dieser Versuchsdurchführung betrachten wir stets den Gauß&ndash;Tiefpass. Die äquivalente Dauer der Impulsantwort &nbsp;$h(t)$&nbsp; sei zunächst  &nbsp;$\Delta t_h= 0.8$.
 +
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  Analsyieren und interpretieren Sie dieses &bdquo;System&rdquo; im Hinblick auf Kausalität und die entstehenden Verzerrungen für ein Rechtecksignal. }}
  
::*&nbsp;$\rm JA$. Alle Wahrscheinlichkeiten sind&nbsp; $2^{-2}$&nbsp; oder&nbsp; $2^{-3}$ &nbsp; &rArr; &nbsp; Symbole werden mit zwei oder drei Bit dargestellt &nbsp; &rArr; &nbsp; $L_{\rm M}= H = 2.5$&nbsp; (bit/Quellensymbol).
+
::*&nbsp;Der Tiefpass ist nicht kausal (realisierbar): für &nbsp;$t < 0$&nbsp; gilt nicht &nbsp;$h(t) \equiv 0$&nbsp; gilt. Geeignetes Modell, wenn man die unendliche Laufzeit außer Acht lässt.
 +
::*&nbsp;Je größer &nbsp;$\Delta t_h$&nbsp; ist, desto breiter wird der Ausgangsimpuls und um so stärker die Degradation eines Digitalsystems durch Impulsinterferenzen.
 +
::*&nbsp;Der Tiefpass&ndash;Frequenzgang &nbsp;$H(f)$&nbsp; ist die Fouriertransformierte von &nbsp;$h(t)$. Je größer &nbsp;$\Delta t_h$&nbsp; ist, desto kleiner ist &nbsp;$\Delta f_h = 1/\Delta t_h$ &nbsp; &rArr; &nbsp; System schmalbandiger.
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(9)''' &nbsp; Wie unterscheiden sich demgegenüber die Ergebnisse für &bdquo;Quelle 6&rdquo; &nbsp;$(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)$? }}
+
'''(8)''' &nbsp; Wählen Sie nun den &nbsp;$\text{Gaußimpuls: }A_x = 1, \ \Delta t_x= 1.5, \ \tau_x = 0$&nbsp; und den &nbsp;$\text{Gauß&ndash;Tiefpass: }\Delta t_h= 2$. Welche Form hat der Ausgangsimpuls &nbsp;$y(t)$?
 +
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  Wie groß ist die äquivalente Dauer &nbsp;$\Delta t_y$&nbsp; des Ausgangsimpulses und der maximale Ausgangswert &nbsp;$y_{\rm max}$? Zu welcher Zeit &nbsp;$t_{\rm max}$&nbsp;  tritt dieser auf? }}
  
::*&nbsp;Bereits durch geringfügige Wahrscheinlichkeitsabweichungen ergeben sich ein anderer Baum und damit auch andere Symbolzuordnungen. 
+
::*&nbsp;$y(t)$&nbsp; ist ebenfalls (exakt) gaußförmig. Merksatz:&nbsp; '''Gauß gefaltet mit Gauß ergibt immer Gauß'''.
::*&nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; werden mit zwei Bit codiert, die anderen mit drei Bit. &nbsp;$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$&nbsp; (bit/Quellensymbol).
+
::*&nbsp;Äquivalente Dauer: &nbsp;$\Delta t_y =\sqrt{\Delta t_x^2+ \Delta t_h^2} = 2.5$.  Impulsmaximum $($bei $t=0)$: &nbsp;$y_{\rm max} = A_x \cdot \Delta t_x/\Delta t_y = 1 \cdot 1.5/2.5 = 0.6$.
::*&nbsp;Die geänderten&nbsp; $p_{\rm A}$, ... &nbsp; verändern hier nicht die mittlere Codewortlänge, aber &nbsp;$H=2.499$ wird (geringfügig) kleiner &nbsp; &rArr; &nbsp; $L_{\rm M} > H$&nbsp; (bit/Quellensymbol).
 
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
'''(10)''' &nbsp; Betrachten Sie die &bdquo;Quelle 9&rdquo; &nbsp;$(M=8, \ p_{\rm A}= 0.8, \ p_{\rm B}= p_{\rm C}= p_{\rm D}=0.02, \ p_{\rm E} = 0.01$,&nbsp; ...&nbsp; , $p_{\rm H} = 0.01)$&nbsp; &rArr; &nbsp; $H = 0.741$&nbsp; (bit/Quellensymbol). Interpretation. }}
+
'''(9)''' &nbsp; Wählen Sie nun den &nbsp;$\text{Dreieckimpuls: }A_x = 1, \ \Delta t_x= 1.5, \ \tau_x = 0$&nbsp; und den &nbsp;$\text{Gauß&ndash;Tiefpass: }\Delta t_h= 2$. Welche Form hat der Ausgangsimpuls &nbsp;$y(t)$?
 +
<br>&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  Wie groß ist die äquivalente Dauer &nbsp;$\Delta t_y$&nbsp; des Ausgangsimpulses und der maximale Ausgangswert &nbsp;$y_{\rm max}$? Zu welcher Zeit &nbsp;$t_{\rm max}$&nbsp; tritt dieser auf? }}
  
::*&nbsp;Es ergibt sich mit &nbsp;$L_{\rm M} = 1.28$&nbsp; ein sehr viel größerer Wert als &nbsp;$H = 0.741$&nbsp; &ndash; sowohl für &bdquo;Huffman&rdquo; als auch für &bdquo;Shannon&ndash;Fano&rdquo;.
+
::*&nbsp;$y(t)$&nbsp; ist gaußähnlich, aber nicht exakt gaußförmig. Merksatz:&nbsp; '''Gauß gefaltet mit Nicht&ndash;Gauß ergibt niemals exakt Gauß'''.
::*&nbsp;Beide Verfahren sind also zur Quellenkomprimierung nicht geeignet, wenn eine Symbolwahrscheinlichkeit deutlich größer ist als 50%.    
+
::*&nbsp;Die abgefragten Kenngrößen des Ausgangsimpules &nbsp;$y(t)$&nbsp; unterscheiden sich nur geringfügig gegenüber &nbsp;$(8)$: &nbsp;$\Delta t_y \approx 2.551$,  &nbsp;$y_{\rm max} \approx 0.588$.  
  
{{BlaueBox|TEXT=
+
==Zur Handhabung des Applets==
'''(11)''' &nbsp; Die Komprimierung der &bdquo;Quelle 9&rdquo; &nbsp;$(M=8, H = 2.481)$&nbsp; mit &bdquo;Huffman&rdquo; ergibt &nbsp;$L_{\rm M} = 2.58$. Welches Ergebnis liefert &bdquo;Shannon&ndash;Fano&rdquo;?&nbsp; Interpretation. }}
+
<br>
 +
[[Datei:Anleitung_Faltung_2.png|right]]
  
::*&nbsp;Bei &bdquo;Huffman&rdquo; wird ein Symbol mit einem Bit codiert, zwei mit drei Bit, drei mit vier Bit und zwei mit fünf Bit &nbsp; &rArr; &nbsp; $L_{\rm M} = 2.58$&nbsp;  (bit/Quellensymbol).
+
&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Auswahl: &nbsp; Form des Eingangsimpulses&nbsp; $x(t)$
::*&nbsp;Entsprechend gilt für &bdquo;Shannon&ndash;Fano&rdquo;:&nbsp; zweimal zwei  Bit, dreimal drei Bit, einmal vier Bit,  zweimal fünf Bit &nbsp; &rArr; &nbsp; $L_{\rm M} = 2.61$&nbsp;  (bit/Quellensymbol).
 
::*&nbsp;$\rm Fazit$:&nbsp; &bdquo;Huffman&rdquo; ist die optimale Entropiecodierung. &bdquo;Shannon&ndash;Fano&rdquo; erreicht meist das gleiche Ergebnis. &nbsp;$\text{Aber nicht immer!}$
 
  
 +
&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; Parametereingabe für den Eingangsimpuls&nbsp; $x(t)$
  
==Zur Handhabung des Applets==
+
&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; Auswahl: &nbsp; Form der Impulsantwort&nbsp; $h(t)$&nbsp; des Tiefpass&ndash;Systems
  
[[Datei:Anleitung_Entropie.png|left]]
+
&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; Parametereingabe für die Impulsantwort&nbsp; $h(t)$
<br>
 
&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Auswahl: &nbsp; Gedächtnislose Quelle / Markovquelle
 
  
&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; Parametereingabe per Slider (Beispiel Markovquelle)  
+
&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Bedienfeld (Start; &nbsp; Pause/Weiter &nbsp; ;&nbsp;  Step > &nbsp; ;&nbsp;  Step <&nbsp;  ;&nbsp;  Reset)
  
&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; Markovdiagramm (falls Markovquelle)
+
&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Ausgabe des Ausgangswertes&nbsp; $y(t)$&nbsp; zur fortlaufenden Zeit&nbsp; $t$
  
&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; Eingabe der Folgenlänge &nbsp;$N$&nbsp; zur Berechnung der&nbsp; $\hat H_k$
+
&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Maximalwert&nbsp; $y_{\rm max} = y(t_{\rm max})$&nbsp; und äquivalente Breite $\Delta\hspace{0.03cm} t_y$
  
&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Ausgabe einer simulierten Symbolfolge
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Nach Umbenennung der Abszisse: &nbsp; $t  \ \to  \ \tau$:
  
&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Ausgabe des Entropiewertes&nbsp; $H$
+
&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Darstellung von &nbsp;$x(\tau)$&nbsp; &rArr; &nbsp; rote statische Kurve
  
&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Ausgabe der Entropienäherungen&nbsp; $H_k$
+
&nbsp; &nbsp; '''(I)''' &nbsp; &nbsp; &nbsp; Darstellung von&nbsp; $h(\tau)$&nbsp; &rArr; &nbsp;blaue Kurve&nbsp; und &nbsp; $h(t-\tau)$&nbsp; &rArr; &nbsp; grüne Kurve <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (diese wird mit dem Bewegungsparameter &nbsp; $t$&nbsp; nach rechts verschoben)
  
&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Ausgabe der numerisch ermittelten Entropienäherungen&nbsp; $\hat H_k$
+
&nbsp; &nbsp; '''(J)''' &nbsp; &nbsp; &nbsp; Darstellung von&nbsp; $x(\tau) \cdot h(t - \tau)$&nbsp; &rArr; &nbsp; violette Kurve, dynamisch mit&nbsp; $t$
  
&nbsp; &nbsp; '''(I)''' &nbsp; &nbsp; Grafikfeld zur Darstellung der Funktion&nbsp; $H(p_{\rm A})$&nbsp; bzw.&nbsp; $H(p_{\rm A}|p_{\rm B})$
+
&nbsp; &nbsp; '''(K)''' &nbsp; &nbsp; &nbsp;Sukzessive Darstellung des Ausgangssignals &nbsp;$y(t)$&nbsp; &rArr; &nbsp; braune Kurve
  
&nbsp; &nbsp; '''(J)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung: &nbsp;  Aufgabenauswahl
+
&nbsp; &nbsp; '''(L)''' &nbsp; &nbsp; &nbsp;Bereich für die Versuchsdurchführung: &nbsp;  Aufgabenauswahl
  
&nbsp; &nbsp; '''(K)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Aufgabenstellung
+
&nbsp; &nbsp; '''(M)''' &nbsp; &nbsp; Versuchsdurchführung:  &nbsp; Bereich für die Aufgabenstellung
  
&nbsp; &nbsp; '''(L)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Musterlösung
+
&nbsp; &nbsp; '''(N)''' &nbsp; &nbsp; Versuchsdurchführung:  &nbsp; Bereich für die Musterlösung
 
<br clear=all>
 
<br clear=all>
 
==Über die Autoren==
 
==Über die Autoren==
 
Dieses interaktive Applet  wurde am [http://www.lnt.ei.tum.de/startseite Lehrstuhl für Nachrichtentechnik] der [https://www.tum.de/ Technischen Universität München] konzipiert und realisiert.  
 
Dieses interaktive Applet  wurde am [http://www.lnt.ei.tum.de/startseite Lehrstuhl für Nachrichtentechnik] der [https://www.tum.de/ Technischen Universität München] konzipiert und realisiert.  
*Die erste Version wurde 2011 von [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Eugen_Mehlmann_.28Bachelorarbeit_EI_2011.29|Eugen Mehlmann]] im Rahmen seiner Bachelorarbeit mit &bdquo;FlashMX&ndash;Actionscript&rdquo; erstellt (Betreuer: [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Mitarbeiter_und_Dozenten#Prof._Dr.-Ing._habil._G.C3.BCnter_S.C3.B6der_.28am_LNT_seit_1974.29|Günter Söder]]).  
+
*Die erste Version wurde 2006 von&nbsp; [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Markus_Elsberger_.28Diplomarbeit_LB_2006.29|Markus Elsberger]]&nbsp; im Rahmen seiner Bachelorarbeit mit &bdquo;FlashMX&ndash;Actionscript&rdquo; erstellt (Betreuer: [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Mitarbeiter_und_Dozenten#Prof._Dr.-Ing._habil._G.C3.BCnter_S.C3.B6der_.28am_LNT_seit_1974.29|Günter Söder]]).  
*2019 wurde das Programm  von  [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Xiaohan_Liu_.28Bachelorarbeit_2018.29|Xiaohan Liu]] (Bachelorarbeit, Betreuer: [[Biografien_und_Bibliografien/Beteiligte_der_Professur_Leitungsgebundene_%C3%9Cbertragungstechnik#Tasn.C3.A1d_Kernetzky.2C_M.Sc._.28bei_L.C3.9CT_seit_2014.29|Tasnád Kernetzky]] ) auf &bdquo;HTML5&rdquo; umgesetzt und neu gestaltet.
+
*2019 wurde das Programm  von&nbsp; [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Carolin_Mirschina_.28Ingenieurspraxis_Math_2019.2C_danach_Werkstudentin.29|Carolin Mirschina]]&nbsp; im Rahmen einer Werkstudententätigkeit auf  &bdquo;HTML5&rdquo; umgesetzt und neu gestaltet (Betreuer: [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_LÜT-Angehörige#Dr.-Ing._Tasn.C3.A1d_Kernetzky_.28bei_L.C3.9CT_von_2014-2022.29|Tasnád Kernetzky]]).
 +
 
 +
 
 +
Die Umsetzung dieses Applets auf HTML 5 wurde durch&nbsp; [https://www.ei.tum.de/studium/studienzuschuesse/ Studienzuschüsse]&nbsp; der Fakultät EI der TU München finanziell unterstützt. Wir bedanken uns.
  
 
==Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster==
 
==Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster==
  
{{LntAppletLink|shannon-huffman}}
+
{{LntAppletLinkDeEn|convolution|convolution_en}}

Aktuelle Version vom 26. Oktober 2023, 11:07 Uhr

Applet in neuem Tab öffnen   Open English Version


Programmbeschreibung


Dieses Applet verdeutlicht die Faltungsoperation im Zeitbereich

  • zwischen einem Eingangsimpuls  $x(t)$   ⇒   Rechteck, Dreieck, Gauß, Exponentialfunktion
  • und der Impulsantwort  $h(t)$  eines LZI–Systems mit Tiefpass–Charakter  ⇒   Spalt–Tiefpass, Tiefpass erster bzw. zweiter Ordnung, Gauß–Tiefpass.


Für das Ausgangssignal  $y(t)$  entsprechend dem Blockschaltbild im  $\text{Beispiel 1}$  gilt dann, wie im Kapitel  Grafische Faltung  dargelegt:

$$y( t ) = x(t) * h( t ) = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm}{x( \tau )} \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau .$$

Bei kausalen Systemen   ⇒    $h(t) \equiv 0$  für  $t < 0$  (Beispiele: Spalt–Tiefpass sowie Tiefpass erster und zweiter Ordnung)   kann hierfür auch geschrieben werden:

$$y( t ) = \int_{ - \infty }^{ t } \hspace{-0.15cm}{x( \tau )} \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau .$$

Bitte beachten Sie:

  • Alle Größen – auch die Zeit $t$ – sind normiert (dimensionslos) zu verstehen.
  • Die Zeitfunktionen  $x(t)$,  $h(t)$  und  $y(t)$  können im Programm keine negativen Signalwerte annehmen.
  • Die absolute Dauer  eines Impulses  $y(t)$  ist der (zusammenhängende) Zeitbereich, für den  $y(t) > 0$  gilt.
  • Die äquivalente Dauer  eines Impulses ist über das flächengleiche Rechteck berechenbar.

Theoretischer Hintergrund


Faltung im Zeitbereich

Der  Faltungssatz  ist mit das wichtigste Gesetz der Fouriertransformation. Wir betrachten zunächst den Faltungssatz im Zeitbereich und setzen voraus, dass die Spektren zweier Zeitfunktionen  $x_1(t)$  und  $x_2(t)$  bekannt sind:

$$X_1 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}x_1( t ),\quad X_2 ( f )\hspace{0.1cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.1cm}x_2 ( t ).$$

Dann gilt für die Zeitfunktion des Produktes  $X_1(f) \cdot X_2(f)$:

$$X_1 ( f ) \cdot X_2 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}\int_{ - \infty }^{ + \infty } {x_1 ( \tau )} \cdot x_2 ( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$

Hierbei ist  $\tau$  eine formale Integrationsvariable mit der Dimension einer Zeit.

$\text{Definition:}$  Die obige Verknüpfung der Zeitfunktion  $x_1(t)$  und  $x_2(t)$  bezeichnet man als  Faltung  und stellt diesen Funktionalzusammenhang mit einem Stern dar:

$$x_{\rm{1} } (t) * x_{\rm{2} } (t) = \int_{ - \infty }^{ + \infty } {x_1 ( \tau ) } \cdot x_2 ( {t - \tau } ) \hspace{0.1cm}{\rm d}\tau.$$

Damit lässt sich obige Fourierkorrespondenz auch wie folgt schreiben:

$$X_1 ( f ) \cdot X_2 ( f )\hspace{0.15cm}\bullet\!\!\!-\!\!\!-\!\!\!-\!\!\circ\hspace{0.15cm}{ {x} }_{\rm{1} } ( t ) * { {x} }_{\rm{2} } (t ).$$

$\text{Beweis}$


Anmerkung:   Die Faltung ist  kommutativ   ⇒   Die Reihenfolge der Operanden ist vertauschbar:   ${ {x}}_{\rm{1}} ( t ) * { {x}}_{\rm{2}} (t ) ={ {x}}_{\rm{2}} ( t ) * { {x}}_{\rm{1}} (t ) $.


Zur Berechnung von Signal und Spektrum am LZI–Ausgang

$\text{Beispiel 1:}$  Ein jedes lineare zeitinvariante (LZI-) System kann sowohl durch den Frequenzgang  $H(f)$  als auch durch die Impulsantwort  $h(t)$  beschrieben werden, wobei der Zusammenhang zwischen diesen beiden Systemgrößen ebenfalls durch die Fouriertransformation gegeben ist.

Legt man an den Eingang ein Signal  $x(t)$  mit dem Spektrum  $X(f)$  an, so gilt für das Spektrum des Ausgangssignals:

$$Y(f) = X(f) \cdot H(f)\hspace{0.05cm}.$$

Mit dem Faltungssatz ist es nun möglich, das Ausgangssignal auch direkt im Zeitbereich zu berechnen:

$$y( t ) = x(t) * h( t ) = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm}{x( \tau )} \cdot h( {t - \tau } )\hspace{0.1cm}{\rm d}\tau = \int_{ - \infty }^{ + \infty } \hspace{-0.15cm} {h( \tau )} \cdot x( {t - \tau } )\hspace{0.1cm}{\rm d}\tau = h(t) * x( t ).$$

Aus dieser Gleichung geht nochmals hervor, dass die Faltungsoperation  kommutativ  ist.


Faltung im Frequenzbereich

Die Dualität zwischen Zeit– und Frequenzbereich erlaubt auch Aussagen hinsichtlich des Spektrums eines Produktsignals:

$$x_1 ( t ) \cdot x_2 ( t )\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\,X_1 (f) * X_2 (f) = \int_{ - \infty }^{ + \infty } {X_1 ( \nu )} \cdot X_2 ( {f - \nu })\hspace{0.1cm}{\rm d}\nu.$$

Dieses Resultat lässt sich ähnlich wie der  Faltungssatz im Zeitbereich  beweisen. Die Integrationsvariable  $\nu$  hat aber nun die Dimension einer Frequenz.

Faltung im Frequenzbereich

$\text{Beispiel 2:}$  Die  Zweiseitenband-Amplitudenmodulation  (ZSB-AM) ohne Träger wird durch das skizzierte Modell beschrieben.

  • Bei der Zeitbereichsdarstellung (blau) ergibt sich das modulierte Signal  $s(t)$  als das Produkt aus dem Nachrichtensignal  $q(t)$  und dem (normierten) Trägersignal  $z(t)$.
  • Nach dem Faltungssatz folgt daraus für den Frequenzbereich (rot), dass das Ausgangsspektrum  $S(f)$  gleich dem Faltungsprodukt aus  $Q(f)$  und  $Z(f)$  ist.


Faltung einer Funktion mit einer Diracfunktion

Sehr einfach wird die Faltungsoperation, wenn einer der beiden Operanden eine  Diracfunktion  ist. Dies gilt für die Faltung im Zeit– und im Frequenzbereich gleichermaßen.

Wir betrachten beispielhaft die Faltung einer Funktion  $x_1(t)$  mit der Funktion

$$x_2 ( t ) = \alpha \cdot \delta ( {t - T} ) \quad \circ\,\!\!\!-\!\!\!-\!\!\!-\!\!\bullet \quad X_2 ( f )= \alpha \cdot {\rm{e}}^{ - {\rm{j}}\hspace{0.03cm}2\hspace{0.03cm}{\rm{\pi }}\hspace{0.01cm}f\hspace{0.01cm}T}.$$

Für die Spektralfunktion des Signals  $y(t) = x_1(t) \ast x_2(t)$  gilt dann:

$$Y( f ) = X_1 ( f ) \cdot X_2 ( f ) = X_1 ( f ) \cdot \alpha \cdot {\rm{e}}^{ - {\rm{j}}\hspace{0.03cm}2\hspace{0.03cm}{\rm{\pi }}\hspace{0.01cm}f\hspace{0.01cm}T} .$$

Die komplexe Exponentialfunktion führt zur Verschiebung um  $T$   ⇒   Verschiebungssatz, der Faktor  $\alpha$  zu einer Dämpfung  $(\alpha < 1)$  bzw. einer Verstärkung  $(\alpha > 1)$. Daraus folgt:

$$x_1 (t) * x_2 (t) = \alpha \cdot x_1 ( {t - T} ).$$

$\text{In Worten: }$  Die Faltung einer beliebigen Funktion mit einer Diracfunktion bei  $t = T$  ergibt die um  $T$  nach rechts verschobene Funktion, wobei noch die Gewichtung der Diracfunktion durch den Faktor  $\alpha$  zu berücksichtigen ist.


$\text{Beispiel 3:}$  Ein Rechtecksignal  $x(t)$  wird durch ein LZI-System um eine Laufzeit  $\tau = 3\,\text{ ms}$  verzögert und um den Faktor  $\alpha = 0.5$  gedämpft.

Faltung eines Rechtecks mit einer Diracfunktion

Verschiebung und Dämpfung erkennt man sowohl am Ausgangssignal  $y(t)$  als auch an der Impulsantwort  $h(t)$.


Grafische Faltung

In diesem Applet wird von folgender Faltungsoperation ausgegangen:

Bildschirmabzug des Programms „Grafische Faltung” (frühere Version)
$$y(t) = x (t) * h (t) = \int_{ - \infty }^{ + \infty } {x ( \tau )} \cdot h ( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$

Die Lösung des Faltungsintegrals soll auf grafischem Wege erfolgen. Es wird vorausgesetzt, dass  $x(t)$  und  $h(t)$  zeitkontinuierliche Signale sind.


Dann sind die folgenden Schritte erforderlich:

  1.   Die  Zeitvariablen  der beiden Funktionen  ändern:  
        $x(t) \to x(\tau)$,   $h(t) \to h(\tau)$.
  2.   Zweite Funktion spiegeln:   $h(\tau) \to h(-\tau)$.
  3.   Gespiegelte Funktion um  $t$  verschieben:   $h(-\tau) \to h(t-\tau)$.
  4.   Multiplikation der beiden Funktionen  $x(\tau)$  und  $h(t-\tau)$.
  5.   Integration  über das Produkt bezüglich  $\tau$  in den Grenzen von  $-\infty$  bis  $+\infty$.


Da die Faltung kommutativ ist, kann anstelle von  $h(\tau)$  auch  $x(\tau)$  gespiegelt werden.



Nebenstehende Grafik zeigt einen Bildschirmabzug einer älteren Version des vorliegenden Applets.


Beispiel einer Faltungsoperation:
Sprungfunktion gefaltet mit Exponentialfunktion

$\text{Beispiel 4:}$  Die Vorgehensweise bei der grafischen Faltung wird nun anhand eines ausführlichen Beispiels erklärt:

  • Am Eingang eines Filters liege eine Sprungfunktion  $x(t) = \gamma(t)$  an.
  • Die Impulsantwort des RC-Tiefpasses sei  $h( t ) = {1}/{T} \cdot {\rm{e} }^{ - t/T}.$


Die Grafik zeigt rot das Eingangssignal  $x(\tau)$, blau die Impulsantwort  $h(\tau)$ und grau das Ausgangssignal  $y(\tau)$. Die Zeitachse ist bereits in  $\tau$  umbenannt.

Das Ausgangssignal kann zum Beispiel nach folgender Gleichung berechnet werden:

$$y(t) = h(t) * x(t) = \int_{ - \infty }^{ + \infty } {h( \tau )} \cdot x( {t - \tau } )\hspace{0.1cm}{\rm d}\tau.$$

Noch einige Anmerkungen zur grafischen Faltung:

  • Der Ausgangswert bei  $t = 0$  ergibt sich, indem man das Eingangssignal  $x(\tau)$  spiegelt, dieses gespiegelte Signal  $x(-\tau)$  mit der Impulsantwort  $h(\tau)$  multipliziert und darüber integriert.
  • Da es hier kein Zeitintervall gibt, bei dem sowohl die blaue Kurve  $h(\tau)$  und gleichzeitig auch die rot gestrichelte Spiegelung  $x(-\tau)$  ungleich Null ist, folgt daraus  $y(t=0)=0$.
  • Für jeden anderen Zeitpunkt  $t$  muss das Eingangssignal verschoben werden   ⇒   $x(t-\tau)$, beispielsweise entsprechend der grün gestrichelten Kurve für  $t=T$.
  • Da in diesem Beispiel auch  $x(t-\tau)$  nur die Werte  $0$  oder  $1$  annehmen kann, wird die Integration  $($allgemein von  $\tau_1$  bis  $\tau_2)$  einfach und man erhält mit  $\tau_1 = 0$  und  $\tau_2 = t$ :
$$y( t) = \int_0^{\hspace{0.05cm} t} {h( \tau)}\hspace{0.1cm} {\rm d}\tau = \frac{1}{T}\cdot\int_0^{\hspace{0.05cm} t} {{\rm{e}}^{ - \tau /T } }\hspace{0.1cm} {\rm d}\tau = 1 - {{\rm{e}}^{ - t /T } }.$$

Die Skizze gilt für  $t=T$  und führt zum Ausgangswert  $y(t=T) = 1 – 1/\text{e} \approx 0.632$.


Versuchsdurchführung


  • Wählen Sie zunächst die Nummer  $(1,\ 2, \text{...})$  der zu bearbeitenden Aufgabe. Die Nummer  $0$  entspricht einem „Reset”:  Gleiche Einstellung wie beim Programmstart.
  • Eine Aufgabenbeschreibung wird angezeigt.  Die Parameterwerte sind angepasst.  Lösung nach Drücken von „Musterlösung”.
  • Sowohl das Eingangssignal sind normiert auf  $\pm 1$  zu verstehen.  Auch die ausgegebenen Leistungen sind normierte Größen.


(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)$. Das Ausgangssignal  $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.56$  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 (breitere) 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 breiter 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 der  $\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$   ⇒   System schmalbandiger.

(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.551$,  $y_{\rm max} \approx 0.588$.

Zur Handhabung des Applets


Anleitung Faltung 2.png

    (A)     Auswahl:   Form des Eingangsimpulses  $x(t)$

    (B)     Parametereingabe für den Eingangsimpuls  $x(t)$

    (C)     Auswahl:   Form der Impulsantwort  $h(t)$  des Tiefpass–Systems

    (D)     Parametereingabe für die Impulsantwort  $h(t)$

    (E)     Bedienfeld (Start;   Pause/Weiter   ;  Step >   ;  Step <  ;  Reset)

    (F)     Ausgabe des Ausgangswertes  $y(t)$  zur fortlaufenden Zeit  $t$

    (G)     Maximalwert  $y_{\rm max} = y(t_{\rm max})$  und äquivalente Breite $\Delta\hspace{0.03cm} t_y$

               Nach Umbenennung der Abszisse:   $t \ \to \ \tau$:

    (H)     Darstellung von  $x(\tau)$  ⇒   rote statische Kurve

    (I)       Darstellung von  $h(\tau)$  ⇒  blaue Kurve  und   $h(t-\tau)$  ⇒   grüne Kurve
                (diese wird mit dem Bewegungsparameter   $t$  nach rechts verschoben)

    (J)       Darstellung von  $x(\tau) \cdot h(t - \tau)$  ⇒   violette Kurve, dynamisch mit  $t$

    (K)      Sukzessive Darstellung des Ausgangssignals  $y(t)$  ⇒   braune Kurve

    (L)      Bereich für die Versuchsdurchführung:   Aufgabenauswahl

    (M)     Versuchsdurchführung:   Bereich für die Aufgabenstellung

    (N)     Versuchsdurchführung:   Bereich für die 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

Applet in neuem Tab öffnen   Open English Version