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 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 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  $\rm A$  und  $\rm B$  unabhängig von den vorherigen Symbolen innerhalb der Folg gleich  $p_{\rm A} = p$  und  $p_{\rm B} = 1 – p$  seien. Für die Entropie dieser „gedächtnislosen” Binärquelle gilt:

Binäre Entropiefunktion als Funktion von $p$

$$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  $H_\text{bin}(p)$  als die binäre Entropiefunktion. Aus der Grafik erkennt man:

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

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