Quelltext der Seite Applets:Huffman- und Shannon-Fano-Codierung

{{LntAppletLink|entropie}} 

==Programmbeschreibung==
<br>
Dieses Applet soll den Begriff &bdquo;Entropie&rdquo; am Beispiel einer binären Nachrichtenquelle verdeutlichen. Die Quellensymbolfolge lautet somit &nbsp;$〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}〉$&nbsp; mit &nbsp;$q_i \in \{A, B\}$&nbsp; für &nbsp;$i \ge 1$. Betrachtet werden sowohl eine gedächtnisfreie Quelle als auch eine Markovquelle erster Ordnung (also mit Gedächtnis &bdquo;1&rdquo;), deren Entropien &nbsp;$H$&nbsp; jeweils in geschlossener Form angegeben werden können.

Ebenso werden für die unendlich lange Quellensymbolfolge so genannte Entropienäherungen &nbsp;$H_1$, &nbsp;$H_2$, ... , &nbsp;$H_k$, ... in geschlossener Form angegeben, wobei 
*sich &nbsp;$H_1$&nbsp; allein auf die Symbolwahrscheinlichkeiten bezieht (das heißt: &nbsp; Abhängigkeiten der Symbole innerhalb der Folge bleiben unberücksichtigt),
* zur Berechnung von &nbsp;$H_2$&nbsp; die Folge in Zweiertupel aufgeteilt und deren Entropie angegeben wird, und schließlich
* durch Erweiterung die Entropie &nbsp;$H_k$&nbsp; von &nbsp;$k$&ndash;Tupeln angebbar ist.


Hierbei besteht für jede beliebige Nachrichtenquelle (mit oder ohne Gedächtnis) folgende Größenrealationen: 
:$$ H <\text{...} \le H_k <\text{...} \le H_3 \le H_2 \le H_1 \le H_0 = \log_2 \ 2 = 1\text{ bit/Symbol} \hspace{0.05cm}.$$
$H_0$&nbsp; bezeichnet den ''Entscheidungsgehalt'' von binären Nachrichtenquellen. Die ''Entropie'' &nbsp;$H$&nbsp; der Quelle ergibt sich als der Grenzwert der &nbsp;$H_k$&nbsp; für &nbsp;$k \to \infty$. 

Implizit vorausgesetzt ist bei allen diesen analytisch angebbaren Größen die Folgenlänge &nbsp;$N \to \infty$. Die Entropie &nbsp;$H$&nbsp; lässt sich aber auch aus einer begrenzten Quellensymbolfolge &nbsp;$〈 q_1 \hspace{0.05cm}〉 =〈 q_1 , \hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{N}\hspace{0.05cm}〉$&nbsp; annähern, also auch dann, wenn die statistischen Eigenschaften der Binärquelle unbekannt sind. Die entsprechenden  Entropienäherungen werden hier mit &nbsp;$\hat H_1$, &nbsp;$\hat H_2$, ... , &nbsp;$\hat H_k$, ... bezeichnet. 

Auch hierauf wird in der folgenden Beschreibung eingegangen mit dem Fazit:

*Die Näherung &nbsp;$\hat H_k$&nbsp; ist natürlich um so genauer, je größer die Folgenlänge  &nbsp;$N$&nbsp; ist.
*Ist über die Quelle nichts weiter bekannt als die beispielhafte Folge, so ist der Rechenaufwand enorm.
 
==Theoretischer Hintergrund==
<br> 
Die Entropie spielt in vielen naturwissenschaftlichen Fachgebieten eine große Rolle. Beschränken wir uns auf unser Fachgebiet der Statistik und der Informationstechnik, so ist die Entropie nach der Definition von &nbsp;[https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; unter anderem ein Maß für die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses, für die „Zufälligkeit” dieses Ereignisses und für den mittleren Informationsgehalt einer Zufallsgröße.


===Entropie einer gedächtnislosen Binärquelle ===

[[Datei:Inf_T_1_1_S4_vers2.png|frame|Binäre Entropiefunktion als Funktion von $p$|right]]
Wir setzen zunächst voraus, dass die Auftrittwahrscheinlichkeiten der beiden Symbole &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; unabhängig von den vorherigen Symbolen innerhalb der Folge gleich &nbsp;$p_{\rm A} = p$&nbsp; und &nbsp;$p_{\rm B} = 1 – p$&nbsp; seien. 

Für die Entropie dieser &bdquo;gedächtnislosen&rdquo; Binärquelle gilt:

:$$H = H_{\rm bin} (p) =  p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p} \hspace{0.5cm}{\rm (Einheit\hspace{-0.15cm}: \hspace{0.15cm}bit\hspace{0.15cm}oder\hspace{0.15cm}bit/Symbol)}
\hspace{0.05cm}.$$

Man bezeichnet die Funktion &nbsp;$H_\text{bin}(p)$&nbsp; als die '''binäre Entropiefunktion'''. Aus der Grafik erkennt man:
*Der Maximalwert &nbsp;$H_\text{0} = 1\; \rm  bit/Symbol$&nbsp; ergibt sich für &nbsp;$p = 0.5$, also für gleichwahrscheinliche Binärsymbole. Dann liefern &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; jeweils den gleichen Beitrag zur Entropie. &nbsp;$H_\text{0}$ nennt man auch den ''Entscheidungsgehalt''.
* $H_\text{bin}(p)$&nbsp; ist symmetrisch um &nbsp;$p = 0.5$. Eine Quelle mit &nbsp;$p_{\rm A} = 0.1$&nbsp; und &nbsp;$p_{\rm B} = 0.9$&nbsp; hat die gleiche Entropie  &nbsp;$H = 0.469 \; \rm   bit/Symbol$&nbsp; wie eine Quelle mit &nbsp;$p_{\rm A} = 0.9$&nbsp; und &nbsp;$p_{\rm B} = 0.1$.
*Die Differenz &nbsp;$ΔH = H_\text{0} - H$&nbsp; gibt die ''Redundanz'' der Quelle an und &nbsp;$r = ΔH/H_\text{0}$&nbsp; die ''relative Redundanz''. Im Beispiel ergeben sich &nbsp;$ΔH = 0.531\; \rm  bit/Symbol$&nbsp; bzw. &nbsp;$r = 53.1 \rm \%$.
*Für &nbsp;$p = 0$&nbsp; ergibt sich &nbsp;$H = 0$, da hier die Symbolfolge &nbsp;$\rm B \ B \ B \text{...}$&nbsp; mit Sicherheit vorhergesagt werden kann. Eigentlich ist nun der Symbolumfang nur noch &nbsp;$M = 1$. Gleiches gilt für &nbsp;$p = 1$, also für die Symbolfolge &nbsp;$\rm A  A A \text{...}$&nbsp;





===Entropie hinsichtlich Zweiertupel=== 

[[Datei:Inf_tupel.png|frame|Zur Verdeutlichung der Zweiertupel &nbsp;$\rm AA$, &nbsp;$\rm AB$, &nbsp;$\rm BA$, &nbsp;$\rm BB$|right]]
Wir teilen nun die Quellensymbolfolge $〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}〉$ in Zweiertupel entsprechend der Grafik auf und betrachten dadurch die Entropie zweier aufeinanderfolgender Quellensymbole.

Die Binärquelle wird weiterhin wie im letzten Abschnitt als ''gedächtnislos'' bzw. ''redundanzfrei'' vorausgesetzt. Für die Kombination  $(q_ν, \hspace{0.05cm}q_{ν+1})$ gibt es in diesem Fall &nbsp;$2^2 = 4$&nbsp; mögliche Symbolpaare (farblich markiert) mit folgenden &nbsp;[[Stochastische_Signaltheorie/Mengentheoretische_Grundlagen#Schnittmenge|Verbundwahrscheinlichkeiten]]:
 
:$${\rm Pr}(q_{\nu}\cap q_{\nu+1})\le {\rm Pr}(q_{\nu}) \cdot {\rm Pr}( q_{\nu+1})
 \hspace{0.05cm}.$$

Daraus ist die ''Verbundentropie'' eines Zweier–Tupels berechenbar (der Index &bdquo;2&rdquo; symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht):
 
:$$H_2\hspace{0.05cm}' = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} \sum_{q_{\nu+1}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm} q_{\mu}\hspace{0.01cm} \}}\hspace{-0.1cm}{\rm Pr}(q_{\nu}\cap q_{\nu+1}) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu}\cap q_{\nu+1})} \hspace{0.4cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Zweiertupel})
 \hspace{0.05cm}.$$

Um den mittleren Informationsgehalt pro Symbol zu erhalten, muss &nbsp;$H_2\hspace{0.05cm}'$&nbsp; noch halbiert werden:
 
:$$H_2 = {H_2\hspace{0.05cm}'}/{2}  \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
 \hspace{0.05cm}.$$

Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die im letzten Abschnitt definierte Entropie mit &nbsp;$H_1$:

:$$H_1 = \sum_{q_{\nu}\hspace{0.05cm} \in \hspace{0.05cm}\{ \hspace{0.05cm}q_{\mu}\hspace{0.01cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm log_2}\hspace{0.1cm}\frac {1}{{\rm Pr}(q_{\nu})} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
 \hspace{0.05cm}.$$

Der Index &bdquo;1&rdquo; soll darauf hinweisen, dass &nbsp;$H_1$&nbsp; ausschließlich die Symbolwahrscheinlichkeiten berücksichtigt und nicht statistischen Bindungen zwischen Symbolen innerhalb der Folge. Mit dem Entscheidungsgehalt &nbsp;$H_0 = \log_2 2 = 1\text{ (bit)}$&nbsp; ergibt sich dann folgende Größenbeziehung:
 
:$$H_0 \ge H_1 \ge H_2
 \hspace{0.05cm}.$$

Verdeutlichen wir uns nun die Berechnung der Entropienäherungen &nbsp;$H_1$&nbsp; und &nbsp;$H_2$&nbsp; an zwei Beispielen.

{{GraueBox|TEXT=  
$\text{Beispiel 1:}$&nbsp; Wir betrachten zunächst eine ''gedächtnislose Binärquelle'' mit gleichwahrscheinlichen Symbolen, das heißt es gelte &nbsp;$p_{\rm A} = p_{\rm B} = 1/2$. Die ersten zwanzig Folgenelemente lauten: &nbsp; $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABAB$ ...
*Aufgrund der gleichwahrscheinlichen Binärsymbole ist &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
*Die Verbundwahrscheinlichkeit &nbsp;$p_{\rm AB}$&nbsp; der Kombination &nbsp;$\rm AB$&nbsp; ist gleich &nbsp;$p_{\rm A} · p_{\rm B} = 1/4$. Ebenso gilt &nbsp;$p_{\rm AA} = p_{\rm BB} = p_{\rm BA} = 1/4$. 
*Damit erhält man für die zweite Entropienäherung
 
:$$H_2 = {1}/{2} \cdot \big [ {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +  {1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 +{1}/{4} \cdot {\rm log}_2\hspace{0.1cm}4 \big ] = 1 \,{\rm bit/Symbol} = H_1 = H_0
 \hspace{0.05cm}.$$}}



{{GraueBox|TEXT=  
$\text{Beispiel 2:}$&nbsp; Die zweite hier betrachtete Folge ergibt sich aus  der Folge von $\text{Beispiel 1}$ durch Anwendung eines einfachen Wiederholungscodes: 
:$$〈 q_ν 〉 =\rm BbBbAaAaAaBbAaAaBbBb \text{...} $$
*Die wiederholten Symbole sind durch entsprechende Kleinbuchstaben dargestellt. Bitte beachten Sie: &nbsp; Es handelt sich trotzdem um eine Binärquelle.
*Aufgrund der gleichwahrscheinlichen Binärsymbole ergibt sich auch hier  &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
*Für die Verbundwahrscheinlichkeiten gilt nun &nbsp;$p_{\rm AA}=p_{\rm BB} = 3/8$&nbsp; und &nbsp;$p_{\rm ABA}=p_{\rm BAB} = 1/8$. Daraus folgt:
:$$\begin{align*}H_2 ={1}/{2} \cdot \big [ 2 \cdot {3}/{8} \cdot {\rm log}_2\hspace{0.1cm} {8}/{3} + 
 2 \cdot {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8\big ] = {3}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 - {3}/{8} \cdot{\rm log}_2\hspace{0.1cm}3 +   {1}/{8} \cdot {\rm log}_2\hspace{0.1cm}8 \approx 0.906 \,{\rm bit/Symbol} < H_1 = H_0
 \hspace{0.05cm}.\end{align*}$$

Betrachtet man sich die Aufgabenstellung genauer, so kommt man zu folgendem Schluss: 
*Die Entropie müsste eigentlich &nbsp;$H = 0.5 \hspace{0.05cm} \rm bit/Symbol$&nbsp; sein (jedes zweite Symbol liefert keine neue Information). 
*Die zweite Entropienäherung &nbsp;$H_2 = 0.906 \hspace{0.05cm} \rm bit/Symbol$&nbsp; ist aber deutlich größer als die Entropie &nbsp;$H$.
*Zur Entropiebestimmung dieser redundanten Symbolfolge reicht also die Näherung zweiter Ordnung nicht aus. 
*Vielmehr muss man größere zusammenhängende Blöcke mit &nbsp;$k > 2$&nbsp; Symbolen betrachten. Einen solchen Block bezeichnen wir im Folgenden als $k$–Tupel.}}



 	 
===Verallgemeinerung auf $k$–Tupel und Grenzübergang ===

Wir schreiben zur Abkürzung mit der Verbundwahrscheinlichkeit &nbsp;$p_i^{(k)}$&nbsp; eines $k$–Tupels allgemein:
 
:$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{M^k} p_i^{(k)} \cdot {\rm log}_2\hspace{0.1cm} \frac{1}{p_i^{(k)}} \hspace{0.5cm}({\rm Einheit\hspace{-0.1cm}: \hspace{0.1cm}bit/Symbol})
 \hspace{0.05cm}.$$

*Die Laufvariable &nbsp;$i$&nbsp; steht jeweils für eines der &nbsp;$M^k$ Tupel. Bei den hier betrachteten Binärquellen gilt &nbsp;$M=2$. 
*Die vorher berechnete Näherung &nbsp;$H_2$&nbsp; ergibt sich mit &nbsp;$k = 2$.
*Für die Entropienäherungen &nbsp;$H_k$&nbsp; gelten folgende Größenrelationen; $H_0 = 1\text{ (bit/Symbol)}$ ist wieder der Entscheidungsgehalt:
:$$H \le \text{...} \le H_k \le \text{...} \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$$
*Die '''Entropie einer Nachrichtenquelle mit Gedächtnis''' ist der folgende Grenzwert: 
:$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$

Der Rechenaufwand wird bis auf wenige Sonderfälle $($siehe nachfolgendes $\text{Beispiel 3)}$ mit zunehmendem &nbsp;$k$&nbsp; immer größer:
*Zur Berechnung von &nbsp;$H_{10}$&nbsp; einer Binärquelle ist über &nbsp;$2^{10} = 1024$&nbsp; Terme zu mitteln. 
*Mit jeder weiteren Erhöhung von &nbsp;$k$&nbsp; um &nbsp;$1$&nbsp; verdoppelt sich die Anzahl der Summenterme.


{{GraueBox|TEXT=  
$\text{Beispiel 3:}$&nbsp;
Wir betrachten eine alternierende Binärfolge &nbsp; ⇒ &nbsp; $〈 q_ν 〉 =\rm ABABABAB$ ... &nbsp; . Entsprechend gilt &nbsp;$H_0 = H_1 = 1 \hspace{0.15cm} \rm bit/Symbol$. 

In diesem Sonderfall muss zur Bestimmung der &nbsp;$H_k$–Näherung unabhängig von &nbsp;$k$&nbsp; stets nur über zwei Verbundwahrscheinlichkeiten gemittelt werden:
* $k = 2$: &nbsp;&nbsp;   $p_{\rm AB} = p_{\rm BA} = 1/2$     &nbsp; &nbsp;       ⇒ &nbsp; &nbsp;  $H_2 =  1/2 \hspace{0.15cm} \rm bit/Symbol$,
* $k = 3$:  &nbsp;&nbsp;   $p_{\rm ABA} = p_{\rm BAB} = 1/2$    &nbsp; &nbsp;    ⇒  &nbsp; &nbsp; $H_3 =  1/3 \hspace{0.15cm} \rm bit/Symbol$,
* $k = 4$:  &nbsp;&nbsp;  $p_{\rm ABAB} = p_{\rm BABA} = 1/2$  &nbsp; &nbsp; ⇒  &nbsp; &nbsp; $H_4 =  1/4 \hspace{0.15cm} \rm bit/Symbol$.


Die (tatsächliche) Entropie dieser alternierenden Binärfolge ist demzufolge
:$$H = \lim_{k \rightarrow \infty }{1}/{k} = 0 \hspace{0.05cm}.$$

Dieses Ergebnis war zu erwarten, da die betrachtete Folge nur minimale Information besitzt, die sich allerdings im Entropie–Endwert &nbsp;$H$&nbsp; nicht auswirkt, nämlich die Information:  &nbsp; „Tritt $\rm A$ zu den geraden oder ungeraden Zeitpunkten auf?”

Man erkennt, dass &nbsp;$H_k$&nbsp; dem Endwert &nbsp;$H = 0$&nbsp; nur sehr langsam näher kommt: &nbsp; Die zwanzigste Entropienäherung  liefert immer noch &nbsp;$H_{20} = 0.05 \hspace{0.15cm} \rm bit/Symbol$. }}







===Binärquellen mit Markoveigenschaften  ===	 

[[Datei:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]

Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch [[Stochastische_Signaltheorie/Markovketten|Markovprozesse]] modelliert, wobei wir uns hier auf binäre Markovprozesse erster Ordnung mit den Zuständen (Symbolen) &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; beschränken. 

Rechts  sehen Sie das Übergangsdiagramm für einen binären Markovprozess erster Ordnung. Von den vier angegebenen Übertragungswahrscheinlichkeiten sind allerdings nur zwei frei wählbar, zum Beispiel
* $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = \rm Pr(A\hspace{0.01cm}|\hspace{0.01cm}B)$ &nbsp;  ⇒  &nbsp; bedingte Wahrscheinlichkeit, dass &nbsp;$\rm A$&nbsp; auf &nbsp;$\rm B$&nbsp; folgt.
* $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} = \rm Pr(B\hspace{0.01cm}|\hspace{0.01cm}A)$   &nbsp;  ⇒  &nbsp;   bedingte Wahrscheinlichkeit, dass &nbsp;$\rm B$&nbsp; auf &nbsp;$\rm A$&nbsp; folgt.


Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann &nbsp;$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}$ &nbsp;und &nbsp; $p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}
 \hspace{0.05cm}.$

Aufgrund der vorausgesetzten Eigenschaften [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Station.C3.A4re_Zufallsprozesse|Stationarität]] und [[Stochastische_Signaltheorie/Autokorrelationsfunktion_(AKF)#Ergodische_Zufallsprozesse|Ergodizität]] gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:
 
:$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}
 \hspace{0.05cm}.$$

Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:
* Für &nbsp;$p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$&nbsp; sind die Symbole gleichwahrscheinlich &nbsp; ⇒ &nbsp; $p_{\text{A}} = p_{\text{B}}= 0.5$. Die erste Entropienäherung liefert demzufolge  &nbsp;$H_1 = H_0 = 1 \hspace{0.05cm} \rm  bit/Symbol$, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten &nbsp;$p_{\text{A|B}}$ &nbsp;bzw.&nbsp; $p_{\text{B|A}}$.
*Die Quellenentropie &nbsp;$H$&nbsp; als der Grenzwert $($für &nbsp;$k \to \infty)$&nbsp; der [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Verallgemeinerung_auf_.7F.27.22.60UNIQ-MathJax108-QINU.60.22.27.7F.E2.80.93Tupel_und_Grenz.C3.BCbergang|Entropienäherung $k$–ter Ordnung]] &nbsp; &rArr; &nbsp; $H_k$&nbsp;   hängt aber sehr wohl von den tatsächlichen Werten von &nbsp;$p_{\text{A|B}}$ &nbsp;und&nbsp; $p_{\text{B|A}}$&nbsp; ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.


{{GraueBox|TEXT=  
$\text{Beispiel 4:}$&nbsp;
Wir betrachten drei Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} }$&nbsp; unterscheiden. 
*Für die  Symbolwahrscheinlichkeiten gilt somit  &nbsp;$p_{\rm A} = p_{\rm B}= 0.5$.
*Die  anderen Übergangswahrscheinlichkeiten haben dann die Werte &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =
p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}B} }.$

[[Datei:P_ID2242__Inf_T_1_2_S5b_neu.png|center|frame|Drei Beispiele binärer Markovquellen]] 

*Die mittlere (blaue) Symbolfolge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.5$&nbsp; besitzt die Entropie &nbsp;$H ≈ 1 \hspace{0.05cm}  \rm bit/Symbol$. Das heißt: &nbsp; In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge.

*Die linke (rote) Folge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$&nbsp; weist weniger Wechsel zwischen &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun  &nbsp;$H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$&nbsp; kleiner.

*Die rechte (grüne) Symbolfolge mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$&nbsp; hat die genau gleiche Entropie &nbsp;$H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$&nbsp; wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... $\rm ABABAB$ ... ).}}


Für den allgemeineren Fall &nbsp;$p_{\text{A}} \ne p_{\text{B}}$&nbsp; ist die  Entropieberechnung der Zweiertupel etwas komplizierter: 
*Mit den  Verbundwahrscheinlichkeiten, zum Beispiel &nbsp;$p_{\text{AB}} = p_{\text{A}} · p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$, kann geschrieben werden:
 
:$$H_2\hspace{0.05cm}' = p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{  p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A}  \cdot  p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} +  p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot  p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 \hspace{0.05cm}.$$

*Ersetzt man nun die Logarithmen der Produkte durch entsprechende Summen von Logarithmen, so erhält man das Ergebnis &nbsp;$H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$&nbsp; mit  
:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
 \hspace{0.05cm},$$
:$$H_{\rm M}= p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 \hspace{0.05cm}.$$

*Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):
:$$H_2 =  {1}/{2} \cdot {H_2\hspace{0.05cm}'} = {1}/{2} \cdot \big [ H_{\rm 1} + H_{\rm M} \big] 
 \hspace{0.05cm}.$$

*Erweitert man dieses Ergebnis für &nbsp;$H_2$&nbsp; auf die $k$–te Entropienäherung, so erhält man:
 
:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ].$$

*Die '''Entropie einer Markovquelle''' ergibt sich als der folgende Grenzwert und ist demzufolge einfach zu berechnen: 
:$$H = \lim_{k \rightarrow \infty }H_k  \hspace{0.5cm}\Rightarrow \hspace{0.5cm} H = H_{\rm M} = 2 \cdot  H_2 - H_1 \hspace{0.05cm}.$$




== Zusammenfassung und Schlussfolgerungen ==
<br>
=== Unbekannte Binärquelle ===
* Ist von der Nachrichtenquelle nicht mehr bekannt als der Symbolunfang &nbsp;$M=2$, so müssen die Entropienäherungen &nbsp;$\hat H_k$&nbsp; numerisch aus der Quellensymbolfolge &nbsp;$〈 q_1, \hspace{0.05cm} q_2,\hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{ν–1}, \hspace{0.05cm}q_ν, \hspace{0.05cm}\hspace{0.05cm}q_{ν+1} ,\hspace{0.05cm}\text{ ...}\hspace{0.05cm},\hspace{0.05cm}q_{N} \hspace{0.05cm}〉$&nbsp; ermittelt werden. Die Entropie &nbsp;$H$&nbsp;ergibt sich als der Grenzwert der &nbsp;$\hat H_k$&nbsp; für &nbsp;$k \to \infty$, wobei gilt: 
:$$ H <\text{...} <\hat  H_k <\text{...} < \hat H_3 < \hat H_2 < \hat H_1 \le H_0  \hspace{0.05cm}.$$
*  Bei der numerischen Ermittlung werden alle Wahrscheinlichkeiten &nbsp;$(p_{\rm A}, \text{...})$&nbsp; und bedingten Wahrscheinlichkeiten &nbsp;$(p_{\rm A|B}, \text{...})$&nbsp; durch entsprechende relative Häufigkeiten &nbsp;$(h_{\rm A}, \text{...})$&nbsp; und bedingte Wahrscheinlichkeiten &nbsp;$(h_{\rm A|B}, \text{...})$&nbsp; angenähert.
* Die Genauigkeit der numerischen Ermittlung nimmt bei gleichem &nbsp;$N$&nbsp; mit steigendem &nbsp;$k$&nbsp; ab. Das heißt: &nbsp; Die Folgenlänge &nbsp;$N$&nbsp; der Simulation muss an den größten &nbsp;$k$&ndash;Wert angepasst werden.


=== Gedächtnislose Binärquelle ===

* Eine gedächtnislose Binärquelle ist vollständig durch die Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A}$&nbsp; und &nbsp;$p_{\rm B} = 1- p_{\rm A}$&nbsp; charakterisiert. Für die Entropie gilt folgende Gleichung:

:$$H = p \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm}} + (1-p) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1-p} \hspace{0.5cm}{\rm (Einheit\hspace{-0.15cm}: \hspace{0.15cm}bit\hspace{0.15cm}oder\hspace{0.15cm}bit/Symbol)}
\hspace{0.05cm}.$$

* Der Maximalwert der Entropie ergibt sich für &nbsp;$p_{\rm A}= p_{\rm B} =0.5$; &nbsp;$H_0 = \log_2 \ M$&nbsp; bezeichnet man als den ''Entscheidungsgehalt'' der Quelle. Im binären Fall &nbsp;$(M = 2)$&nbsp; gilt: 

:$$H_{\rm max} = H_0 = \text{ 1 bit/Symbol}\hspace{0.05cm}.$$

* In diesem Fall &nbsp;$(p_{\rm A}= p_{\rm B} =0.5)$&nbsp; ist die Symbolfolge redundanzfrei &nbsp; &rArr; &nbsp; die relative Redundanz ist gleich &nbsp;$r = (H - H_0)/H_0= 0$.

* Im unsymmetrischen Fall &nbsp;$(p_{\rm A} \ne p_{\rm B})$&nbsp; ist die relative Redundanz &nbsp;$r > 0$&nbsp; und für die Entropie gilt mit den Entropienäherung &nbsp;$H_k$:

:$$H = H_1 < H_0, \hspace{0.5cm}H_1 = H_2 = H_3 = \text{...} .$$

* Bei einer gedächtnislosen Quelle sind also alle (analytisch berechneten) Entropienäherungen &nbsp;$H_k$&nbsp; exakt gleich. Für die durch Simulation aus der Symbolfolge &nbsp;$〈 q_ν〉$&nbsp; der Länge &nbsp;$N$&nbsp; gewonnenen Näherungen &nbsp;$\hat  H_k$&nbsp; gilt dieser Zusammenhang bestenfalls näherungsweise

:$$\hat  H_1 \approx \hat  H_2 \approx \hat  H_3 \approx \text{...} .$$

* Als Ergebnis sollte man &nbsp;$H \approx \hat  H_1$&nbsp; verwenden. Bei gegebenem &nbsp;$N$&nbsp; sind die auf der Zeitmittelung basierenden Fehler für &nbsp;$\hat  H_2$ &nbsp;$\hat  H_3$, ... deutlich größer. Oder anders ausgedrückt: &nbsp; Um die gleiche statistische Sicherheit für die Ermittlung von &nbsp;$\hat  H_{k+1}$&nbsp; wie bei &nbsp;$\hat  H_k$&nbsp; zu erzielen, muss man &nbsp;$N$&nbsp; verdoppeln.   


=== Binäre Markovquelle ===

[[Datei:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]

*Folgen mit statistischen Bindungen zwischen den Folgenelementen werden oft durch Markovprozesse modelliert, wobei wir uns hier auf binäre Markovprozesse erster Ordnung mit den Symbolen &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; beschränken.

*Für die Entropie &nbsp;$H = H_{\text{M}}$&nbsp; und die erste Entropienäherung &nbsp;$H_1$&nbsp; einer solchen Markovquelle gelten die folgenden  Gleichungen:

:$$H_{\text{M}} =  p_{\rm A}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm B}  \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B}  \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}}
 \hspace{0.05cm},$$

:$$H_1 = p_{\rm A}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} $$

:$$\Rightarrow \hspace{0.3cm}H_1  = p_{\rm A}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B}  \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B})
 \hspace{0.05cm}.$$

*Die Entropienäherungen &nbsp;$H_k$&nbsp; für &nbsp;$k$–Tupel hängen mit der ersten Näherung &nbsp;$H_1$&nbsp; und dem Endwert &nbsp;$H = H_{\text{M}}$&nbsp; wie folgt zusammen: 

:$$H_k = {1}/{k} \cdot \big [ H_{\rm 1} + (k-1) \cdot H_{\rm M}\big ] \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
 H_2 = {1}/{2} \cdot \big [ H_{\rm 1} +  H_{\rm M} \big ]\hspace{0.05cm}, \hspace{0.3cm}
 H_3 ={1}/{3} \cdot \big [ H_{\rm 1} + 2 \cdot H_{\rm M}\big ] \hspace{0.05cm},\hspace{0.3cm}
 H_4 =  {1}/{4} \cdot \big [ H_{\rm 1} + 3 \cdot H_{\rm M}\big ] 
 \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}$$

* Daraus folgt direkt: &nbsp; Ist über die Nachrichtenquelle nicht mehr bekannt, als dass es sich um eine Markovquelle erster Ordnung handelt, so kann der Endwert &nbsp;$H = H_{\rm M}$&nbsp; allein aus den Entropienäherungen &nbsp;$H_1$&nbsp; und &nbsp;$H_2$&nbsp; ermittelt werden: 
:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm}.$$

{{BlaueBox|TEXT=  
Bei einem '''symmetrischen Markovprozess'''   &nbsp; ⇒  &nbsp;   Übergangswahrscheinlichkeiten   &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } $ &nbsp; ⇒  &nbsp;   Symbolwahrscheinlichkeiten   &nbsp;$p_{\rm A } = p_{\rm B } = 0.5 $&nbsp; erhält man

:$$H_{\text{M} } = H_{\text{bin} }(p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} })=  p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } } + (1 - p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }) \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{1 - p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } },\hspace{0.5cm}H_1 = 1\text{ bit/Symbol} .$$}}  

==Versuchsdurchführung==
[[Datei:Exercises_Entropie.png|right]]
*Wählen Sie zunächst die Aufgabennummer.
*Eine Aufgabenbeschreibung wird angezeigt.
*Alle Parameterwerte sind angepasst.
*Alle Entropiewerte werden berechnet und eine Symbolfolge ausgegeben.
*Musterlösung nach Drücken von &bdquo;Hide solution&rdquo;.
*Mit der Nummer &bdquo;0&rdquo; wird auf die gleichen Einstellung wie beim Programmstart zurückgesetzt.
<br clear=all>
{{BlaueBox|TEXT=
'''(1)''' &nbsp; Wählen Sie die gedächtnislose Binärquelle mit &nbsp;$p_{\rm A} = p_{\rm B} = 0.5$. Wie lauten die analytisch berechneten Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? 

:Wie unterscheiden sich die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$&nbsp; mit &nbsp;$N=10^5$&nbsp; von &nbsp;$H_1$, ... , &nbsp;$H_6$? &nbsp; Machen Sie jeweils zehn Versuche.  }}

::*&nbsp;Es handelt sich um eine redundanzfreie Binärquelle &nbsp; &rArr; &nbsp; $H = H_{\rm bin}(0.5) = H_1 =$ ... $=H_6 = 1\text{ bit/Symbol}$. 
::*&nbsp;Auch die Simulation mit &nbsp;$N=10^5$&nbsp; liefert bei (fast) allen Versuchsreihen &nbsp;$\hat H_1 =$ ... &nbsp;$=\hat H_6 = 1.000$ &nbsp; &rArr; &nbsp; das auf drei Nachkommastellen richtige Ergebnis. 

{{BlaueBox|TEXT=
'''(2)''' &nbsp; Wie unterscheiden sich bei sonst gleichen Einstellungen die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$ mit $N=10^3$? &nbsp; Wieder jeweils zehn Versuche.  }}

::*&nbsp;Die Entropienäherungen $H_k$ werden nun durch $\hat H_k$ ungenauer nachgebildet als mit $N=10^5$ &nbsp; &rArr; &nbsp; die Statistik ist nicht ausreichend. 
::*&nbsp;Die Simulation mit $N=10^3$ liefert bei zehn Versuchsreihen für $\hat H_1$ entweder $1.000$ oder $0.999$ und für $\hat H_6$ Werte zwischen $0.982$ und $0.995$ &nbsp; 
::*&nbsp; &rArr; &nbsp; Simulationsgenauigkeit nimmt mit steigendem $k$ ab. Die simulierten Werte $\hat H_k$ sind stets kleiner als $H_k = 1.000$. Beides gilt auch für noch kleineres &nbsp;$N$.

{{BlaueBox|TEXT=
'''(3)''' &nbsp; Wählen Sie nun die gedächtnislose Binärquelle mit &nbsp;$p_{\rm A} =  0.2$&nbsp; und &nbsp;$p_{\rm B} =  0.8$. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? 

:Wie unterscheiden sich die Simulationsergebnisse &nbsp;$\hat H_1$, ... , &nbsp;$\hat H_6$&nbsp; mit &nbsp;$N=10^5$&nbsp; von &nbsp;$H_1$, ... , &nbsp;$H_6$? &nbsp; Wieder jeweils zehn Versuche.}}

::*&nbsp;Es gilt &nbsp;$H = H_{\rm bin}(0.2) = 0.722\text{ bit/Symbol}$. Wie bei jeder gedächtnislosen Nachrichtenquelle gilt auch hier &nbsp;$H_1 =$ ... $=H_6 = H$. 
::*&nbsp;Die Simulation mit &nbsp;$N=10^5$&nbsp; liefert bei zehn Versuchsreihen für &nbsp;$\hat H_1$&nbsp; Werte zwischen $0.719$ und $0.727$. Es gilt aber stets &nbsp;$\hat H_1 =$ ... $= \hat H_6$.
::*&nbsp;In solchen Fällen weicht die relative Häufigkeit &nbsp;$h_{\rm A}$&nbsp; von der Wahrscheinlichkeit &nbsp;$p_{\rm A}$&nbsp; ab. Ist &nbsp;$\hat H_1 > 0.722$, so ist &nbsp;$h_{\rm A} > 0.2$.

{{BlaueBox|TEXT=
'''(4)''' &nbsp; Was ändert sich gegenüber '''(3)''' mit den Symbolwahrscheinlichkeiten &nbsp;$p_{\rm A} =  0.8$&nbsp; und &nbsp;$p_{\rm B} =  0.2$?}} 

::&nbsp;'''Nichts'''. Die binäre Entropiefunktion ist symmetrisch um &nbsp;$p=0.5$.
::&nbsp;'''Ist nun &nbsp;$\hat H_1 > 0.722$, so ist &nbsp;$h_{\rm A} < 0.8$.'''

{{BlaueBox|TEXT=
'''(5)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.8$&nbsp;. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}

::*&nbsp;Bei dieser &bdquo;Markovquelle&rdquo; ist &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.2$&nbsp;. Deshalb ist auch die unbedingte Wahrscheinlichkeit &nbsp;$p_{\rm A} = 0.2$ &nbsp; &rArr; &nbsp; $p_{\rm B} = 0.8$.
::*Es handelt sich also um die gleiche gedächtnislose Quelle wie bei '''(4)''' &nbsp; &rArr; &nbsp;$H = H_1 =$ ... $=H_6 =  0.722\text{ bit/Symbol}$. 

{{BlaueBox|TEXT=
'''(6)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.2$&nbsp;. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}

::*&nbsp;Hier handelt es sich um eine &bdquo;echte Markovquelle&rdquo;, da sich &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.2$&nbsp; und &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1 - p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.8$&nbsp; unterscheiden. 
::*Wegen &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}}$ sind die beiden unbedingten Symbolwahrscheinlichkeiten gleich: &nbsp;$p_{\rm A} = p_{\rm B} = 0.5$&nbsp; &rArr; &nbsp; $H_1 = 1$.
::*Die Entropienäherungen $H_k$ werden mit steigendem $k$ kleiner: &nbsp;$H_2 = 0.861$, &nbsp;$H_3 = 0.815$, ... , &nbsp;$H_6 = 0.768$.  Der Endwert ist wieder &nbsp;$H = H_\infty = 0.722\text{ bit/Symbol}$.

{{BlaueBox|TEXT=
'''(7)''' &nbsp; Welche Unterschiede gegenüber '''(6)''' ergeben sich mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.8$? }}

::*&nbsp;Die Entropienäherung &nbsp;$H = H_{\rm bin}(0.8) = H_{\rm bin}(0.2)= 0.722\text{ bit/Symbol}$&nbsp; bleibt gleich, ebenso alle Entropienäherungen &nbsp;$H_k$. 
::* Wegen den größeren Übergangswahrscheinlichkeiten &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}} = 0.8$&nbsp; erkennt man jetzt deutlich mehr Übergänge in der ausgegebenen Symbolfolge. 

{{BlaueBox|TEXT=
'''(8)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.9$. Wie groß sind die Entropie &nbsp;$H$ und die Entropienäherungen &nbsp;$H_1$, ... , &nbsp;$H_6$? }}

::*Wegen &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B}} \ne p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A}}$ sind nun die beiden unbedingten Symbolwahrscheinlichkeiten unterschiedlich: &nbsp;$p_{\rm A} = 0.471$&nbsp; und &nbsp;$p_{\rm B} = 0.529$&nbsp; &rArr; &nbsp; $H_1 = 0.998 \ne 1$.
::*Die Entropienäherungen $H_k$ werden wieder kontinuierlich kleiner: &nbsp;$H_2 = 0.800$, &nbsp;$H_3 = 0.734$, ... , &nbsp;$H_6 = 0.669$.  Endwert: &nbsp; $H = H_\infty = 0.603\text{ bit/Symbol}$. 
::*&nbsp;Aus der Symbolfolge erkennt man, dass zwei Symbole &nbsp;$\rm A$&nbsp; ganz selten aufeinanderfolgen. 

{{BlaueBox|TEXT=
'''(9)''' &nbsp; Es gelte weiterhin &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0.9$. Für welches &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }$&nbsp; ergibt sich die maximale Entropie? }}

::*Anhand der roten Kurve in der Grafik zu '''(8)''' lässt sich bereits das Ergebnis  &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} }\approx 0.45$&nbsp; abschätzen. 
::* Der dazugehörige Entropie&ndash;Endwert ist &nbsp; $H = H_\infty = 0.818\text{ bit/Symbol}$.

{{BlaueBox|TEXT=
'''(10)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  1.0$. Interpretieren Sie die dargestellten Ergebnisse. }} 

::*Die unbedingten Symbolwahrscheinlichkeiten sind &nbsp;$p_{\rm A} = 0.444$&nbsp; und &nbsp;$p_{\rm B} = 0.556$&nbsp; &rArr; &nbsp; $H_1 = 0.991 \ne 1$. Der Entropie&ndash;Endwert ist &nbsp;$H = H_\infty = 0.401\text{ bit/Symbol}$.
::*&nbsp;Aus der Symbolfolge erkennt man, dass das Symbol &nbsp;$\rm A$&nbsp; im Gegensatz zum Symbol &nbsp;$\rm B$&nbsp; stets isoliert auftritt. 

{{BlaueBox|TEXT=
'''(11)''' &nbsp; Wählen Sie nun die Markovquelle mit &nbsp;$p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } =  0.8$&nbsp; und &nbsp;$p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } =  0$. Interpretieren Sie die dargestellten Ergebnisse. }} 

::*Die unbedingten Symbolwahrscheinlichkeiten sind &nbsp;$p_{\rm A} = 1$&nbsp; und &nbsp;$p_{\rm B} = 0$&nbsp; &rArr; &nbsp; die Symbolfolge besteht nur aus &nbsp;$\rm A$&nbsp; &nbsp; &rArr; &nbsp; Entropienäherung &nbsp;$H_1 = 0 $. 
::*&nbsp;Alle weiteren Entropienäherungen $H_k$ und auch der Entropie&ndash;Endwert sind ebenfalls Null.
 



 

==Zur Handhabung des Applets==

[[Datei:Anleitung_Entropie.png|left]]
<br>
&nbsp; &nbsp; '''(A)''' &nbsp; &nbsp; Auswahl: &nbsp; Gedächtnislose Quelle / Markovquelle

&nbsp; &nbsp; '''(B)''' &nbsp; &nbsp; Parametereingabe per Slider (Beispiel Markovquelle) 

&nbsp; &nbsp; '''(C)''' &nbsp; &nbsp; Markovdiagramm (falls Markovquelle)

&nbsp; &nbsp; '''(D)''' &nbsp; &nbsp; Eingabe der Folgenlänge &nbsp;$N$&nbsp; zur Berechnung der&nbsp; $\hat H_k$

&nbsp; &nbsp; '''(E)''' &nbsp; &nbsp; Ausgabe einer simulierten Symbolfolge

&nbsp; &nbsp; '''(F)''' &nbsp; &nbsp; Ausgabe des Entropiewertes&nbsp; $H$

&nbsp; &nbsp; '''(G)''' &nbsp; &nbsp; Ausgabe der Entropienäherungen&nbsp; $H_k$

&nbsp; &nbsp; '''(H)''' &nbsp; &nbsp; Ausgabe der numerisch ermittelten Entropienäherungen&nbsp; $\hat H_k$

&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; '''(J)''' &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; '''(L)''' &nbsp; &nbsp; Bereich für die Versuchsdurchführung:  &nbsp; Musterlösung
<br clear=all>
==Ü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. 
*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]]). 
*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.

==Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster==

{{LntAppletLink|entropie}}