Applets:Entropie und Näherungen binärer Nachrichtenquellen

Open Applet in a new tab

Programmbeschreibung

Dieses Applet soll den Begriff „Entropie” 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 „1”, 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 Berechnung und graphische Darstellung der Gaußschen Fehlerfunktionen ${\rm Q}(x)$ und $1/2\cdot {\rm erfc}(x)$, die für die Fehlerwahrscheinlichkeitsberechnung von großer Bedeutung sind.

• Sowohl die Abszisse als auch der Funktionswert kann entweder linear oder logarithmisch dargestellt werden.
• Für beide Funktionen wird jeweils eine obere Schranke (englisch: Upper Bound ) und eine untere Schranke (englisch: Lower Bound) angegeben.

Theoretischer Hintergrund

Bei der Untersuchung digitaler Übertragungssysteme muss oft die Wahrscheinlichkeit bestimmt werden, dass eine (mittelwertfreie) gaußverteilte Zufallsgröße $x$ mit der Varianz $σ^2$ einen vorgegebenen Wert $x_0$ überschreitet. Für diese Wahrscheinlichkeit gilt:

$${\rm Pr}(x > x_0)={\rm Q}(\frac{x_0}{\sigma}) = 1/2 \cdot {\rm erfc}(\frac{x_0}{\sqrt{2} \cdot \sigma}).$$

Entropie hinsichtlich Zweiertupel

Wir betrachten weiterhin 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}〉$ und betrachten nun die Entropie zweier aufeinanderfolgender Quellensymbole.

• Alle Quellensymbole $q_ν$ entstammen einem Alphabet mit dem Symbolunfang $M$, so dass es für die Kombination $(q_ν, \hspace{0.05cm}q_{ν+1})$ genau $M^2$ mögliche Symbolpaare mit folgenden Verbundwahrscheinlichkeiten gibt:

$${\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:

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

Der Index „2” symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht.

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 Kapitel Gedächtnislose Nachrichtenquellen 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 „1” 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 \ M$ ergibt sich dann folgende Größenbeziehung:

$$H_0 \ge H_1 \ge H_2 \hspace{0.05cm}.$$

Bei statistischer Unabhängigkeit der Folgenelemente ist $H_2 = H_1$.

Die bisherigen Gleichungen geben jeweils einen Scharmittelwert an. Die für die Berechnung von $H_1$ und $H_2$ benötigten Wahrscheinlichkeiten lassen sich aber auch als Zeitmittelwerte aus einer sehr langen Folge berechnen oder – etwas genauer ausgedrückt – durch die entsprechenden relativen Häufigkeiten annähern.

Verdeutlichen wir uns nun die Berechnung der Entropienäherungen $H_1$ und $H_2$ an drei Beispielen.

$\text{Beispiel 2:}$  Wir betrachten zunächst die Folge $〈 q_1$, ... , $q_{50} \rangle $ gemäß folgernder Grafik, wobei die Folgenelemente $q_ν$ dem Alphabet $\rm \{A, B, C \}$ entstammen   ⇒   der Symbolumfang ist $M = 3$.

Ternäre Symbolfolge und Bildung von Zweier–Tupeln

Durch Zeitmittelung über die $50$ Symbole erhält man die Symbolwahrscheinlichkeiten $p_{\rm A} ≈ 0.5$,   $p_{\rm B} ≈ 0.3$  und  $p_{\rm C} ≈ 0.2$, womit man die Entropienäherung erster Ordnung berechnen kann:

$$H_1 = 0.5 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.5} + 0.3 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.3} +0.2 \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{0.2} \approx \, 1.486 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

Aufgrund der nicht gleichwahrscheinlichen Symbole ist $H_1 < H_0 = 1.585 \hspace{0.05cm} \rm bit/Symbol$. Als Näherung für die Wahrscheinlichkeiten von Zweiertupeln erhält man aus der obigen Folge:

$$\begin{align*}p_{\rm AA} \hspace{-0.1cm}& = \hspace{-0.1cm} 14/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AB} = 8/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm AC} = 3/49\hspace{0.05cm}, \\ p_{\rm BA} \hspace{-0.1cm}& = \hspace{0.07cm} 7/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm BB} = 2/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm BC} = 5/49\hspace{0.05cm}, \\ p_{\rm CA} \hspace{-0.1cm}& = \hspace{0.07cm} 4/49\hspace{0.05cm}, \hspace{0.25cm}p_{\rm CB} = 5/49\hspace{0.05cm}, \hspace{0.2cm}p_{\rm CC} = 1/49\hspace{0.05cm}.\end{align*}$$

Beachten Sie, dass aus den $50$ Folgenelementen nur $49$ Zweiertupel $(\rm AA$, ... , $\rm CC)$ gebildet werden können, die in obiger Grafik farblich unterschiedlich markiert sind.

• Die daraus berechenbare Entropienäherung $H_2$ sollte eigentlich gleich $H_1$ sein, da die gegebene Symbolfolge von einer gedächtnislosen Quelle stammt.
• Aufgrund der kurzen Folgenlänge $N = 50$ und der daraus resultierenden statistischen Ungenauigkeit ergibt sich aber ein kleinerer Wert:   $H_2 ≈ 1.39\hspace{0.05cm} \rm bit/Symbol$.

$\text{Beispiel 3:}$  Nun betrachten wir eine gedächtnislose Binärquelle mit gleichwahrscheinlichen Symbolen, das heißt es gelte $p_{\rm A} = p_{\rm B} = 1/2$. Die ersten zwanzig Folgeelemente lauten:   $〈 q_ν 〉 =\rm BBAAABAABBBBBAAAABAB$ ...

• Aufgrund der gleichwahrscheinlichen Binärsymbole ist $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
• Die Verbundwahrscheinlichkeit $p_{\rm AB}$ der Kombination $\rm AB$ ist gleich $p_{\rm A} · p_{\rm B} = 1/4$. Ebenso gilt $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}.$$

Hinweis:   Aus der oben angegebenen Folge ergeben sich aufgrund der kurzen Länge etwas andere Verbundwahrscheinlichkeiten, nämlich $p_{\rm AA} = 6/19$,   $p_{\rm BB} = 5/19$  und  $p_{\rm AB} = p_{\rm BA} = 4/19$.

$\text{Beispiel 4:}$  Die dritte hier betrachtete Folge ergibt sich aus der Folge von $\text{Beispiel 3}$ 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 $H_1 = H_0 = 1 \hspace{0.05cm} \rm bit/Symbol$.
• Wie in Aufgabe 1.3 gezeigt wird, gilt nun für die Verbundwahrscheinlichkeiten $p_{\rm AA}=p_{\rm BB} = 3/8$ und $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 $H = 0.5 \hspace{0.05cm} \rm bit/Symbol$ sein (jedes zweite Symbol liefert keine neue Information).
• Die zweite Entropienäherung $H_2 = 0.906 \hspace{0.05cm} \rm bit/Symbol$ ist aber deutlich größer als die Entropie $H$.
• Zur Entropiebestimmung reicht die Näherung zweiter Ordnung nicht aus. Vielmehr muss man größere zusammenhängende Blöcke mit $k > 2$ Symbolen betrachten.
• Einen solchen Block bezeichnen wir im Folgenden als $k$–Tupel.

Verallgemeinerung auf $k$–Tupel und Grenzübergang

Zur Abkürzung schreiben wir 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. Die vorher berechnete Näherung $H_2$ ergibt sich mit $k = 2$.

$\text{Definition:}$  Die Entropie einer Nachrichtenquelle mit Gedächtnis ist der folgende Grenzwert:

$$H = \lim_{k \rightarrow \infty }H_k \hspace{0.05cm}.$$

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

Der Rechenaufwand wird bis auf wenige Sonderfälle (siehe nachfolgendes Beispiel) mit zunehmendem $k$ immer größer und hängt natürlich auch vom Symbolumfang $M$ ab:

• 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.
• Bei einer Quaternärquelle $(M = 4)$ muss zur $H_{10}$–Bestimmung bereits über $4^{10} = 1\hspace{0.08cm}048\hspace{0.08cm}576$ Summenterme gemittelt werden.
• Berücksichtigt man, dass jedes dieser $4^{10} =2^{20} >10^6$ $k$–Tupel bei Simulation/Zeitmittelung etwa $100$ mal (statistischer Richtwert) vorkommen sollte, um ausreichende Simulationsgenauigkeit zu gewährleisten, so folgt daraus, dass die Folgenlänge größer als $N = 10^8$ sein sollte.

$\text{Beispiel 5:}$  Wir betrachten eine alternierende Binärfolge   ⇒   $〈 q_ν 〉 =\rm ABABABAB$ ...   . 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$:    $p_{\rm AB} = p_{\rm BA} = 1/2$     ⇒     $H_2 = 1/2 \hspace{0.1cm} \rm bit/Symbol$,
• $k = 3$:    $p_{\rm ABA} = p_{\rm BAB} = 1/2$     ⇒     $H_3 = 1/3 \hspace{0.1cm} \rm bit/Symbol$,
• $k = 4$:    $p_{\rm ABAB} = p_{\rm BABA} = 1/2$     ⇒     $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:   „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$.

$\text{Zusammenfassung der Ergebnisse der letzten Seiten:}$ 

• 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.
  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$,   $H_4 < H_3$, usw.   ⇒   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.

Über die Autoren

Dieses interaktive Berechnungstool wurde am Lehrstuhl für Nachrichtentechnik der Technischen Universität München konzipiert und realisiert.

• Die erste Version wurde 2007 von Thomas Großer im Rahmen seiner Diplomarbeit mit „FlashMX–Actionscript” erstellt (Betreuer: Günter Söder).
• 2018 wurde das Programm von Marwen Ben Ammar und Xiaohan Liu (Bachelorarbeit, Betreuer: Tasnád Kernetzky ) auf „HTML5” umgesetzt und neu gestaltet.

Nochmalige Aufrufmöglichkeit des Applets in neuem Fenster

Open Applet in a new tab