View source for 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 &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. Implizit vorausgesetzt ist hierbei 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. Auch hierauf wird in der folgenden Beschreibung eingegangen mit dem Fazit:

*Die Näherung ist natürlich um so genauer, je größer &nbsp;$N$&nbsp; 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 &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 ===

[[File: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 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 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$&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=== 

[[File: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 auf (siehe 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. 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 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 $M^k$ Tupel. Bei den hier betrachteten Binärquellen gilt $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  ===	 

[[File: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} }.$

[[File: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.25$&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 ===
{{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$.}}

{{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.}}

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

Hierbei wird der Vorteil von Markovquellen gegenüber anderen Quellen ausgenutzt, dass sich die Entropieberechnung für $k$–Tupel sehr einfach gestaltet. 

:$$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.}$$



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}$, ...

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}})$.
	






==Ü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}}