Quelltext der Seite Applets:Entropie und Näherungen binärer Nachrichtenquellen

{{LntAppletLink|qfunction}} 

==Programmbeschreibung==
<br>
Dieses Applet soll den Begriff &bdquo;Entropie&rdquo; am Beispiel einer binären Nachrichtenquelle verdeutlichen. Die Quellensymbolfolge lautet somit $〈 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}〉$ mit $q_i \in \{A, B\}$ für $i \ge 1$. Betrachtet werden sowohl eine gedächtnisfreie Quelle als auch eine Markovquelle (mit Gedächtnis &bdquo;1&rdquo;, deren Entropien $H$ jeweils in geschlossener Form angegeben werden können. Implizit vorausgesetzt ist hierbei die Folgenlänge $N \to \infty$.

Die Entropie $H$ lässt sich aber auch aus einer begrenzten Quellensymbolfolge $〈 q_1 \hspace{0.05cm}〉 =〈 q_1 , \hspace{0.05cm}\text{ ...} \hspace{0.05cm}, q_{N}\hspace{0.05cm}〉$ annähern, also auch dann, wenn die statistischen Eigenschaften der Binärquelle unbekannt sind. Auch hierauf wird in der folgenden Beschreibung eingegangen mit dem Fazit:

*Die Näherung ist natürlich um so genauer, je größer $N$ ist.
*Ist über die Quelle nichts weiter bekannt als die beispielhafte Folge, so ist der Rechenaufwand enorm.
 
==Theoretischer Hintergrund==
  
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 [https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon] unter anderem ein Maß für die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses, die „Zufälligkeit” dieses Ereignisses und den mittleren Informationsgehalt einer Zufallsgröße.


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

Wir setzen voraus, dass die Auftrittwahrscheinlichkeiten der beiden Symbole &nbsp;$\rm A$&nbsp; und &nbsp;$\rm B$&nbsp; unabhängig von den vorherigen Symbolen innerhalb der Folg 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 diese Funktion &nbsp;$H_\text{bin}(p)$&nbsp; als die '''binäre Entropiefunktion'''. 

[[Datei:Inf_T_1_1_S4_vers2.png|frame|Binäre Entropiefunktion als Funktion von $p$|center]]
Aus der Grafik erkennt man:
*Der Maximalwert &nbsp;$H_\text{0} = 1\; \rm  bit$&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 ''Informationsgehalt''.
* $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$&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$&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=== 

Wir betrachten weiterhin die binäre 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}〉$ und betrachten nun die Entropie zweier aufeinanderfolgender Quellensymbole. Für die Kombination  $(q_ν, \hspace{0.05cm}q_{ν+1})$ gibt es $2^2 = 4$ mögliche Symbolpaare mit folgenden [[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 $H_2\hspace{0.05cm}'$ 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 $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 $H_1$ ausschließlich die Symbolwahrscheinlichkeiten berücksichtigt und nicht statistischen Bindungen zwischen Symbolen innerhalb der Folge. Mit dem Entscheidungsgehalt $H_0 = \log_2 2 = 1$ 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 $H_1$ und $H_2$ 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 Folgeelemente 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 markiert.
*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 &nbsp;$p_{\rm AA}=p_{\rm BB} = 3/8$&nbsp; und &nbsp;$p_{\rm ABA}=p_{\rm BAB} = 1/8$&nbsp; gilt nun. 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 reicht 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.}}


{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp;
*Bei statistischer Unabhängigkeit der Folgenelemente ist &nbsp;$H = H_2 = H_1 \le H_0$.
*Bei statistischer Abhängigkeit der Folgenelemente gilt dagegen &nbsp;$H < H_2  < H_1 \le H_0$.}}

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

Wir schreiben zur Abkürzung mit der Verbundwahrscheinlichkeit $p_i^{(k)}$ 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 $i$ steht jeweils für eines der $M^k$ Tupel. Bei den hier betrachteten Binärquellen gilt $M=2$. 
*Die vorher berechnete Näherung $H_2$ ergibt sich mit $k = 2$.
*Für die Entropienäherungen $H_k$ gelten folgende Größenrelationen ($H_0$ ist 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 $k$ immer größer:
*Zur Berechnung von $H_{10}$ einer Binärquelle $(M = 2)$ ist über $2^{10} = 1024$ Terme zu mitteln. 
*Mit jeder weiteren Erhöhung von $k$ um $1$ 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 $H_0 = H_1 = 1 \hspace{0.05cm} \rm bit/Symbol$. 

In diesem Sonderfall muss zur Bestimmung der $H_k$–Näherung unabhängig von $k$ 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.1cm} \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.1cm} \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.1cm} \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 $H$ nicht auswirkt, nämlich die Information:  &nbsp; „Tritt $\rm A$ zu den geraden oder ungeraden Zeitpunkten auf?”

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


{{BlaueBox|TEXT=  
$\text{Zusammenfassung der Ergebnisse der letzten Seiten:}$&nbsp;

*Allgemein gilt für die '''Entropie einer Nachrichtenquelle''':
:$$H \le \text{...} \le H_3 \le H_2 \le H_1 \le H_0 
 \hspace{0.05cm}.$$ 
*Eine '''redundanzfreie Quelle''' liegt vor, falls alle $M$ Symbole gleichwahrscheinlich sind und es keine statistischen Bindungen innerhalb der Folge gibt. <br>Für diese gilt ( $r$ bezeichnet hierbei die ''relative Redundanz'' ):
:$$H = H_0 = H_1 = H_2 = H_3 = \text{...}\hspace{0.5cm}
\Rightarrow \hspace{0.5cm} r = \frac{H - H_0}{H_0}= 0 \hspace{0.05cm}.$$ 
*Eine '''gedächtnislose Quelle''' kann durchaus redundant sein $(r> 0)$. Diese Redundanz geht dann allein auf die Abweichung der Symbolwahrscheinlichkeiten von der Gleichverteilung zurück. Hier gelten folgende Relationen:
:$$H = H_1 = H_2 = H_3 = \text{...} \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm}0 \le r = \frac{H_1 - H_0}{H_0}< 1 \hspace{0.05cm}.$$ 
*Die entsprechende Bedingung für eine '''gedächtnisbehaftete Quelle''' lautet:
:$$ H <\text{...} < H_3 < H_2 < H_1 \le H_0 \hspace{0.5cm}\Rightarrow \hspace{0.5cm} 0 < r = \frac{H_1 - H_0}{H_0}\le1 \hspace{0.05cm}.$$
*Ist $H_2 < H_1$, dann gilt auch $H_3 < H_2$, &nbsp; $H_4 < H_3$, usw. &nbsp; &rArr; &nbsp; In der allgemeinen Gleichung ist also das „≤”–Zeichen durch das „<”–Zeichen zu ersetzen. 
*Sind die Symbole gleichwahrscheinlich, so gilt wieder $H_1 = H_0$, während bei nicht gleichwahrscheinlichen Symbolen $H_1 < H_0$ zutrifft.}}




===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 Markovprozesse erster Ordnung beschränken. Zunächst betrachten wir einen binären Markovprozess $(M = 2)$ mit den Zuständen (Symbolen) $\rm A$ und $\rm B$.

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 $\rm A$ auf $\rm B$ 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 $\rm B$ auf $\rm A$ folgt.


Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann $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 $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$ sind die Symbole gleichwahrscheinlich &nbsp; ⇒ &nbsp; $p_{\text{A}} = p_{\text{B}}= 0.5$. Die erste Entropienäherung liefert $H_1 = H_0 = 1 \hspace{0.05cm} \rm  bit/Symbol$, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten $p_{\text{A|B}}$ &nbsp;bzw.&nbsp; $p_{\text{B|A}}$.
*Die Quellenentropie $H$ als der Grenzwert (für $k \to \infty$) 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$   hängt aber sehr wohl von den tatsächlichen Werten von $p_{\text{A|B}}$ &nbsp;und&nbsp; $p_{\text{B|A}}$ ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.


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

[[Datei:P_ID2242__Inf_T_1_2_S5b_neu.png|right|frame|Drei Beispiele binärer Markovquellen]] 
:$$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} }.$$

*Die mittlere (blaue) Symbolfolge mit $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.5$ besitzt die Entropie $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 $p_{\rm {A\hspace{0.01cm}\vert\hspace{0.01cm}B} } = p_{\rm {B\hspace{0.01cm}\vert\hspace{0.01cm}A} } = 0.25$ weist weniger Wechsel zwischen $\rm A$ und $\rm B$ auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun  $H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$ kleiner.

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


Zu diesem Beispiel ist noch anzumerken:
*Hätte man nicht die Markoveigenschaften der roten und der grünen Folge ausgenutzt, so hätte man das Ergebnis $H ≈ 0.72 \hspace{0.05cm}  \rm bit/Symbol$ erst nach langwierigen Berechnungen erhalten.
*Auf den nächsten Seiten wird gezeigt, dass bei einer Quelle mit Markoveigenschaften der Endwert $H$ allein aus den Entropienäherungen $H_1$ und $H_2$ ermittelt werden kann. Ebenso lassen sich aus $H_1$ und $H_2$ alle Entropienäherungen $H_k$ für $k$–Tupel in einfacher Weise berechnen &nbsp;  ⇒  &nbsp; $H_3$, $H_4$, $H_5$, ... , $H_{100}$, ...
	
 
===Vereinfachte Entropieberechnung bei Markovquellen  ===
<br>
[[Datei:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]
Wir gehen weiterhin von der symmetrischen binären Markovquelle erster Ordnung aus. Wie auf der vorherigen Seite verwenden wir folgende Nomenklatur für
*die Übergangswahrscheinlichkeiten $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$,&nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}A}}= 1- p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}B}} = 1 - p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp; 
*die ergodischen Wahrscheinlichkeiten $p_{\text{A}}$ und $p_{\text{B}}$,
*die Verbundwahrscheinlichkeiten, zum Beispiel $p_{\text{AB}} = p_{\text{A}} · p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.


Wir berechnen nun die [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|Entropie eines Zweiertupels]] (mit der Einheit „bit/Zweiertupel”):
 
:$$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 $H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$ 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}.$$

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp; 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}.$$}}


Anzumerken ist:
*Der erste Summand $H_1$ &nbsp; ⇒  &nbsp; erste Entropienäherung ist  allein abhängig von den Symbolwahrscheinlichkeiten.
*Bei einem symmetrischen Markovprozess   &nbsp; ⇒  &nbsp;      $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} $  &nbsp; ⇒  &nbsp; $p_{\text{A}} = p_{\text{B}} = 1/2$ &nbsp; ergibt sich für diesen ersten Summanden $H_1 = 1 \hspace{0.05cm} \rm bit/Symbol$.
*Der zweite Summand $H_{\text{M}}$  muss gemäß der zweiten der oberen Gleichungen berechnet werden. 
*Bei einem symmetrischen Markovprozess erhält man $H_{\text{M}} = H_{\text{bin}}(p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}})$.


Nun wird dieses Ergebnis auf die $k$–te Entropienäherung erweitert. Hierbei wird der Vorteil von Markovquellen gegenüber anderen Quellen ausgenutzt, dass sich die Entropieberechnung für $k$–Tupel sehr einfach gestaltet. Für jede Markovquelle gilt nämlich:
 
:$$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.}$$

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp; Bildet man den Grenzübergang für $k \to \infty$, so erhält man für die tatsächliche Quellenentropie:
:$$H = \lim_{k \rightarrow \infty } H_k = H_{\rm M} \hspace{0.05cm}.$$
Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:
*Bei Markovquellen genügt die Bestimmung der Entropienäherungen $H_1$ und $H_2$. Damit lautet die Entropie einer Markovquelle: 
:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm}.$$

*Durch $H_1$ und $H_2$ liegen auch alle weiteren Entropienäherungen $H_k$ für $k \ge 3$ fest:
 
:$$H_k =  \frac{2-k}{k} \cdot  H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot  H_{\rm 2}
 \hspace{0.05cm}.$$}}


Diese Näherungen haben allerdings keine große Bedeutung. Wichtig ist meist nur der Grenzwert $H$. Bei Quellen ohne Markoveigenschaften berechnet man die Näherungen $H_k$ nur deshalb, um den Grenzwert, also die tatsächliche Entropie, abschätzen zu können.==
<br>
[[Datei:Inf_T_1_2_S5_vers2.png|right|frame|Markovprozesse mit $M = 2$ Zuständen]]
Wir gehen weiterhin von der symmetrischen binären Markovquelle erster Ordnung aus. Wie auf der vorherigen Seite verwenden wir folgende Nomenklatur für
*die Übergangswahrscheinlichkeiten $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$,&nbsp; $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}A}}= 1- p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$, &nbsp; $p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}B}} = 1 - p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}}$, &nbsp; 
*die ergodischen Wahrscheinlichkeiten $p_{\text{A}}$ und $p_{\text{B}}$,
*die Verbundwahrscheinlichkeiten, zum Beispiel $p_{\text{AB}} = p_{\text{A}} · p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}}$.


Wir berechnen nun die [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|Entropie eines Zweiertupels]] (mit der Einheit „bit/Zweiertupel”):
 
:$$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 $H_2\hspace{0.05cm}' = H_1 + H_{\text{M}}$ 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}.$$

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp; 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}.$$}}


Anzumerken ist:
*Der erste Summand $H_1$ &nbsp; ⇒  &nbsp; erste Entropienäherung ist  allein abhängig von den Symbolwahrscheinlichkeiten.
*Bei einem symmetrischen Markovprozess   &nbsp; ⇒  &nbsp;      $p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}} = p_{\rm {B\hspace{0.01cm}|\hspace{0.01cm}A}} $  &nbsp; ⇒  &nbsp; $p_{\text{A}} = p_{\text{B}} = 1/2$ &nbsp; ergibt sich für diesen ersten Summanden $H_1 = 1 \hspace{0.05cm} \rm bit/Symbol$.
*Der zweite Summand $H_{\text{M}}$  muss gemäß der zweiten der oberen Gleichungen berechnet werden. 
*Bei einem symmetrischen Markovprozess erhält man $H_{\text{M}} = H_{\text{bin}}(p_{\rm {A\hspace{0.01cm}|\hspace{0.01cm}B}})$.


Nun wird dieses Ergebnis auf die $k$–te Entropienäherung erweitert. Hierbei wird der Vorteil von Markovquellen gegenüber anderen Quellen ausgenutzt, dass sich die Entropieberechnung für $k$–Tupel sehr einfach gestaltet. Für jede Markovquelle gilt nämlich:
 
:$$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.}$$

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp; Bildet man den Grenzübergang für $k \to \infty$, so erhält man für die tatsächliche Quellenentropie:
:$$H = \lim_{k \rightarrow \infty } H_k = H_{\rm M} \hspace{0.05cm}.$$
Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:
*Bei Markovquellen genügt die Bestimmung der Entropienäherungen $H_1$ und $H_2$. Damit lautet die Entropie einer Markovquelle: 
:$$H = 2 \cdot H_2 -   H_{\rm 1}  \hspace{0.05cm}.$$

*Durch $H_1$ und $H_2$ liegen auch alle weiteren Entropienäherungen $H_k$ für $k \ge 3$ fest:
 
:$$H_k =  \frac{2-k}{k} \cdot  H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot  H_{\rm 2}
 \hspace{0.05cm}.$$}}


Diese Näherungen haben allerdings keine große Bedeutung. Wichtig ist meist nur der Grenzwert $H$. Bei Quellen ohne Markoveigenschaften berechnet man die Näherungen $H_k$ nur deshalb, um den Grenzwert, also die tatsächliche Entropie, abschätzen zu können.


==Über die Autoren==
Dieses interaktive Berechnungstool  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 2007 von [[Biografien_und_Bibliografien/An_LNTwww_beteiligte_Studierende#Thomas_Gro.C3.9Fer_.28Diplomarbeit_LB_2006.2C_danach_freie_Mitarbeit_bis_2010.29|Thomas Großer]] im Rahmen seiner Diplomarbeit 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]]). 
*2018 wurde das Programm  von ''Marwen Ben Ammar''   und [[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|qfunction}}