Gedächtnislose Nachrichtenquellen
Inhaltsverzeichnis
# ÜBERBLICK ZUM ERSTEN HAUPTKAPITEL #
Dieses erste Kapitel beschreibt die Berechnung und die Bedeutung der Entropie. Diese ist entsprechend der Shannonschen Informationsdefinition ein Maß für die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses oder die Unsicherheit bei der Messung einer stochastischen Größe. Etwas salopp ausgedrückt quantifiziert die Entropie einer Zufallsgröße deren „Zufälligkeit”.
Im Einzelnen werden behandelt:
- Der »Entscheidungsgehalt« und die »Entropie« einer gedächtnislosen Nachrichtenquelle,
- die »binäre Entropiefunktion« und deren Anwendung auf nichtbinäre Quellen,
- die Entropieberechnung bei »gedächtnisbehafteten Quellen« und geeignete Näherungen,
- die Besonderheiten von »Markovquellen« hinsichtlich der Entropieberechnung,
- die Vorgehensweise bei Quellen mit großem Symbolumfang, zum Beispiel »natürliche Texte«,
- die »Entropieabschätzungen« nach Shannon und Küpfmüller.
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch „Wertdiskrete Informationstheorie” des Praktikums „Simulation Digitaler Übertragungssysteme ”. Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
- dem Windows-Programm WDIT ⇒ der Link verweist auf die ZIP-Version des Programms und
- der zugehörigen Praktikumsanleitung ⇒ der Link verweist auf die PDF-Version.
Modell und Voraussetzungen
Wir betrachten eine wertdiskrete Nachrichtenquelle $\rm Q$, die eine Folge $ \langle q_ν \rangle$ von Quellensymbolen abgibt.
- Für die Laufvariable gilt $ν = 1$, ... , $N$, wobei $N$ „hinreichend groß” sein sollte.
- Jedes einzelne Quellensymbol $q_ν$ entstammt einem Symbolvorrat $\{q_μ \}$ mit $μ = 1$, ... , $M$, wobei $M$ den Symbolumfang bezeichnet:
- $$q_{\nu} \in \left \{ q_{\mu} \right \}, \hspace{0.25cm}{\rm mit}\hspace{0.25cm} \nu = 1, \hspace{0.05cm} \text{ ...}\hspace{0.05cm} , N\hspace{0.25cm}{\rm und}\hspace{0.25cm}\mu = 1,\hspace{0.05cm} \text{ ...}\hspace{0.05cm} , M \hspace{0.05cm}.$$
Die Grafik zeigt eine quaternäre Nachrichtenquelle $(M = 4)$ mit dem Alphabet $\rm \{A, \ B, \ C, \ D\}$ und eine beispielhafte Folge der Länge $N = 100$.
Es gelten folgende Voraussetzungen:
- Die Nachrichtenquelle wird durch $M = 4$ Symbolwahrscheinlichkeiten $p_μ$ vollständig beschrieben. Allgemein gilt:
- $$\sum_{\mu = 1}^M \hspace{0.1cm}p_{\mu} = 1 \hspace{0.05cm}.$$
- Die Nachrichtenquelle sei gedächtnislos, das heißt, die einzelnen Folgenelemente seien statistisch voneinander unabhängig:
- $${\rm Pr} \left (q_{\nu} = q_{\mu} \right ) = {\rm Pr} \left (q_{\nu} = q_{\mu} \hspace{0.03cm} | \hspace{0.03cm} q_{\nu -1}, q_{\nu -2}, \hspace{0.05cm} \text{ ...}\hspace{0.05cm}\right ) \hspace{0.05cm}.$$
- Da das Alphabet aus Symbolen (und nicht aus Zufallsgrößen) besteht, ist hier die Angabe von Erwartungswerten (linearer Mittelwert, quadratischer Mittelwert, Streuung, usw.) nicht möglich, aus informationstheoretischer Sicht aber auch nicht nötig.
Diese Eigenschaften werden nun an einem Beispiel verdeutlicht.
$\text{Beispiel 1:}$ Für die Symbolwahrscheinlichkeiten einer Quaternärquelle gelte:
- $$p_{\rm A} = 0.4 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.3 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.2 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.1\hspace{0.05cm}.$$
Bei einer unendlich langen Folge $(N \to \infty)$
- wären die relativen Häufigkeiten $h_{\rm A}$, $h_{\rm B}$, $h_{\rm C}$, $h_{\rm D}$ ⇒ a–posteriori–Kenngrößen
- identisch mit den Wahrscheinlichkeiten $p_{\rm A}$, $p_{\rm B}$, $p_{\rm C}$, $p_{\rm D}$ ⇒ a–priori–Kenngrößen.
Bei kleinerem $N$ kann es durchaus zu Abweichungen kommen, wie die nebenstehende Tabelle (Ergebnis einer Simulation) zeigt.
- In der oberen Grafik ist eine beispielhafte Folge mit $N = 100$ Symbolen angegeben.
- Aufgrund der Mengenelemente $\rm A$, $\rm B$, $\rm C$ und $\rm D$ können keine Mittelwerte angegeben werden.
Ersetzt man aber die Symbole durch Zahlenwerte, zum Beispiel $\rm A \Rightarrow 1$, $\rm B \Rightarrow 2$, $\rm C \Rightarrow 3$, $\rm D \Rightarrow 4$, so ergeben sich entsprechend
Zeitmittelung ⇒ überstreichende Linie bzw. Scharmittelung ⇒ Erwartungswertbildung
- für den linearen Mittelwert :
- $$m_1 = \overline { q_{\nu} } = {\rm E} \big [ q_{\mu} \big ] = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 4 = 2 \hspace{0.05cm},$$
- für den quadratischen Mittelwert:
- $$m_2 = \overline { q_{\nu}^{\hspace{0.05cm}2} } = {\rm E} \big [ q_{\mu}^{\hspace{0.05cm}2} \big ] = 0.4 \cdot 1^2 + 0.3 \cdot 2^2 + 0.2 \cdot 3^2 + 0.1 \cdot 4^2 = 5 \hspace{0.05cm},$$
- für die Standardabweichung (Streuung) nach dem „Satz von Steiner”:
- $$\sigma = \sqrt {m_2 - m_1^2} = \sqrt {5 - 2^2} = 1 \hspace{0.05cm}.$$
Entscheidungsgehalt einer diskreten Nachrichtenquelle
Claude Elwood Shannon definierte 1948 im Standardwerk der Informationstheorie [Sha48][1] den Informationsbegriff als „Abnahme der Ungewissheit über das Eintreten eines statistischen Ereignisses”.
Machen wir hierzu ein gedankliches Experiment mit $M$ möglichen Ergebnissen, die alle gleichwahrscheinlich seien: $p_1 = p_2 = \hspace{0.05cm} \text{ ...}\hspace{0.05cm} = p_M = 1/M \hspace{0.05cm}.$
Unter dieser Annahme gilt:
- Ist $M = 1$, so wird jeder einzelne Versuch das gleiche Ergebnis liefern und demzufolge besteht keine Unsicherheit hinsichtlich des Ausgangs. Wird uns das Versuchsergebnis mitgeteilt, so haben wir dadurch natürlich auch keinen Informationsgewinn.
- Dagegen erfährt ein Beobachter bei einem Experiment mit $M = 2$, zum Beispiel dem „Münzwurf” mit der Ereignismenge $\big \{\rm \boldsymbol{\rm Z}(ahl), \rm \boldsymbol{\rm W}(app) \big \}$ und den Wahrscheinlichkeiten $p_{\rm Z} = p_{\rm W} = 0.5$ durchaus einen Informationsgewinn. Die Unsicherheit hinsichtlich $\rm Z$ bzw. $\rm W$ wird aufgelöst.
- Beim Experiment „Würfeln” $(M = 6)$ und noch mehr beim Roulette $(M = 37)$ ist die gewonnene Information für den Beobachter noch deutlich größer als beim „Münzwurf”, wenn er erfährt, welche Zahl gewürfelt bzw. welche Kugel gefallen ist.
- Schließlich sollte noch berücksichtigt werden, dass das Experiment „Dreifacher Münzwurf” mit den $M = 8$ möglichen Ergebnissen $\rm ZZZ$, $\rm ZZW$, $\rm ZWZ$, $\rm ZWW$, $\rm WZZ$, $\rm WZW$, $\rm WWZ$, $\rm WWW$ die dreifache Information liefert wie der einfache Münzwurf $(M = 2)$.
Die nachfolgende Festlegung erfüllt alle hier aufgeführten Anforderungen an ein quantitatives Informationsmaß bei gleichwahrscheinlichen Ereignissen, allein gekennzeichnet durch den Symbolumfang $M$.
$\text{Definition:}$ Der Entscheidungsgehalt einer diskreten Nachrichtenquelle hängt nur vom Symbolumfang $M$ ab und ergibt sich zu
- $$H_0 = {\rm log}\hspace{0.1cm}M = {\rm log}_2\hspace{0.1cm}M \hspace{0.15cm} {\rm (in \ ”bit”)} = {\rm ln}\hspace{0.1cm}M \hspace{0.15cm}\text {(in "nat")} = {\rm lg}\hspace{0.1cm}M \hspace{0.15cm}\text {(in "Hartley")}\hspace{0.05cm}.$$
- Gebräuchlich ist hierfür in der deutschsprachigen Literatur auch die Bezeichnung »Nachrichtengehalt«.
- Da $H_0$ gleichzeitig den Maximalwert der Entropie $H$ angibt, wird in unserem Tutorial teilweise auch $H_\text{max}$ als Kurzzeichen verwendet.
Zu unserer Nomenklatur ist anzumerken:
- Der Logarithmus wird im Folgenden unabhängig von der Basis mit „log” bezeichnet.
- Die oben genannten Relationen werden aufgrund folgender Eigenschaften erfüllt:
- $${\rm log}\hspace{0.1cm}1 = 0 \hspace{0.05cm},\hspace{0.2cm} {\rm log}\hspace{0.1cm}37 > {\rm log}\hspace{0.1cm}6 > {\rm log}\hspace{0.1cm}2\hspace{0.05cm},\hspace{0.2cm} {\rm log}\hspace{0.1cm}M^k = k \cdot {\rm log}\hspace{0.1cm}M \hspace{0.05cm}.$$
- Meist verwenden wir den Logarithmus zur Basis $2$ ⇒ »Logarithmus dualis« $\rm (ld)$, wobei dann die Pseudoeinheit „bit” – genauer: „bit/Symbol” – hinzugefügt wird:
- $${\rm ld}\hspace{0.1cm}M = {\rm log_2}\hspace{0.1cm}M = \frac{{\rm lg}\hspace{0.1cm}M}{{\rm lg}\hspace{0.1cm}2} = \frac{{\rm ln}\hspace{0.1cm}M}{{\rm ln}\hspace{0.1cm}2} \hspace{0.05cm}.$$
- Weiter findet man in der Literatur vereinzelt auch die oben zusätzlich angegebenen Definitionen, die auf dem natürlichen Logarithmus $\rm (ln)$ oder dem Zehnerlogarithmus $\rm (lg)$ basieren.
Informationsgehalt und Entropie
Wir verzichten nun auf die bisherige Voraussetzung, dass alle $M$ möglichen Ergebnisse eines Versuchs gleichwahrscheinlich seien. Im Hinblick auf eine möglichst kompakte Schreibweise legen wir für diese Seite lediglich fest:
- $$p_1 > p_2 > \hspace{0.05cm} \text{ ...}\hspace{0.05cm} > p_\mu > \hspace{0.05cm} \text{ ...}\hspace{0.05cm} > p_{M-1} > p_M\hspace{0.05cm},\hspace{0.4cm}\sum_{\mu = 1}^M p_{\mu} = 1 \hspace{0.05cm}.$$
Wir betrachten nun den „Informationsgehalt” der einzelnen Symbole, wobei wir den „Logarithmus dualis” mit $\log_2$ bezeichnen:
- $$I_\mu = {\rm log_2}\hspace{0.1cm}\frac{1}{p_\mu}= -\hspace{0.05cm}{\rm log_2}\hspace{0.1cm}{p_\mu} \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 erkennt:
- Wegen $p_μ ≤ 1$ ist der Informationsgehalt nie negativ. Im Grenzfall $p_μ \to 1$ geht $I_μ \to 0$.
- Allerdings ist für $I_μ = 0$ ⇒ $p_μ = 1$ ⇒ $M = 1$ auch der Entscheidungsgehalt $H_0 = 0$.
- Bei abfallenden Wahrscheinlichkeiten $p_μ$ nimmt der Informationsgehalt kontinuierlich zu:
- $$I_1 < I_2 < \hspace{0.05cm} \text{ ...}\hspace{0.05cm} < I_\mu <\hspace{0.05cm} \text{ ...}\hspace{0.05cm} < I_{M-1} < I_M \hspace{0.05cm}.$$
$\text{Fazit:}$ Je unwahrscheinlicher ein Ereignis ist, desto größer ist sein Informationsgehalt. Diesen Sachverhalt stellt man auch im täglichen Leben fest:
- „6 Richtige” im Lotto nimmt man sicher eher wahr als „3 Richtige” oder gar keinen Gewinn.
- Ein Tsunami in Asien dominiert auch die Nachrichten in Deutschland über Wochen im Gegensatz zu den fast standardmäßigen Verspätungen der Deutschen Bahn.
- Eine Niederlagenserie von Bayern München führt zu Riesen–Schlagzeilen im Gegensatz zu einer Siegesserie. Bei 1860 München ist genau das Gegenteil der Fall.
Der Informationsgehalt eines einzelnen Symbols (oder Ereignisses) ist allerdings nicht sehr interessant. Dagegen erhält man
- durch Scharmittelung über alle möglichen Symbole $q_μ$ bzw.
- durch Zeitmittelung über alle Elemente der Folge $\langle q_ν \rangle$
eine der zentralen Größen der Informationstheorie.
$\text{Definition:}$ Die Entropie $H$ einer Quelle gibt den mittleren Informationsgehalt aller Symbole an:
- $$H = \overline{I_\nu} = {\rm E}\hspace{0.01cm}[I_\mu] = \sum_{\mu = 1}^M p_{\mu} \cdot {\rm log_2}\hspace{0.1cm}\frac{1}{p_\mu}= -\sum_{\mu = 1}^M p_{\mu} \cdot{\rm log_2}\hspace{0.1cm}{p_\mu} \hspace{0.5cm}\text{(Einheit: bit, genauer: bit/Symbol)} \hspace{0.05cm}.$$
Die überstreichende Linie kennzeichnet wieder eine Zeitmittelung und $\rm E[\text{...}]$ eine Scharmittelung.
Die Entropie ist unter anderem ein Maß für
- die mittlere Unsicherheit über den Ausgang eines statistischen Ereignisses,
- die „Zufälligkeit” dieses Ereignisses, sowie
- den mittleren Informationsgehalt einer Zufallsgröße.
Binäre Entropiefunktion
Wir beschränken uns zunächst auf den Sonderfall $M = 2$ und betrachten eine binäre Quelle, die die beiden Symbole $\rm A$ und $\rm B$ abgibt. Die Auftrittwahrscheinlichkeiten seien $p_{\rm A} = p$ und $p_{\rm B} = 1 – p$.
Für die Entropie dieser Binärquelle gilt:
- $$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 nennt die Funktion $H_\text{bin}(p)$ die binäre Entropiefunktion. Die Entropie einer Quelle mit größerem Symbolumfang $M$ lässt sich häufig unter Verwendung von $H_\text{bin}(p)$ ausdrücken.
$\text{Beispiel 2:}$ Die Grafik zeigt die binäre Entropiefunktion für die Werte $0 ≤ p ≤ 1$ der Symbolwahrscheinlichkeit von $\rm A$ $($oder auch von $\rm B)$. Man erkennt:
- 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$ ⇒ Symbolfolge $\rm A \ A \ A \text{...}$.
- $H_\text{bin}(p)$ ist stets eine „konkave Funktion”, da die zweite Ableitung nach dem Parameter $p$ für alle Werte von $p$ negativ ist:
- $$\frac{ {\rm d}^2H_{\rm bin} (p)}{ {\rm d}\,p^2} = \frac{- 1}{ {\rm ln}(2) \cdot p \cdot (1-p)}< 0 \hspace{0.05cm}.$$
Nachrichtenquellen mit größerem Symbolumfang
Im ersten Abschnitt dieses Kapitels haben wir eine quaternäre Nachrichtenquelle $(M = 4)$ mit den Symbolwahrscheinlichkeiten $p_{\rm A} = 0.4$, $p_{\rm B} = 0.3$, $p_{\rm C} = 0.2$ und $ p_{\rm D} = 0.1$ betrachtet. Diese Quelle besitzt die folgende Entropie:
- $$H_{\rm quat} = 0.4 \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{0.4} + 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}+ 0.1 \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{0.1}.$$
Oft ist zur zahlenmäßigen Berechnung der Umweg über den Zehnerlogarithmus $\lg \ x = {\rm log}_{10} \ x$ sinnvoll, da der „Logarithmus dualis” $ {\rm log}_2 \ x$ meist auf Taschenrechnern nicht zu finden ist.
- $$H_{\rm quat}=\frac{1}{{\rm lg}\hspace{0.1cm}2} \cdot \left [ 0.4 \cdot {\rm lg}\hspace{0.1cm}\frac{1}{0.4} + 0.3 \cdot {\rm lg}\hspace{0.1cm}\frac{1}{0.3} + 0.2 \cdot {\rm lg}\hspace{0.1cm}\frac{1}{0.2}+ 0.1 \cdot {\rm lg}\hspace{0.1cm}\frac{1}{0.1} \right ] = 1.845\,{\rm bit} \hspace{0.05cm}.$$
$\text{Beispiel 3:}$ Nun bestehen zwischen den einzelnen Symbolwahrscheinlichkeiten gewisse Symmetrien:
- $$p_{\rm A} = p_{\rm D} = p \hspace{0.05cm},\hspace{0.4cm}p_{\rm B} = p_{\rm C} = 0.5 - p \hspace{0.05cm},\hspace{0.3cm}{\rm mit} \hspace{0.15cm}0 \le p \le 0.5 \hspace{0.05cm}.$$
In diesem Fall kann zur Entropieberechnung auf die binäre Entropiefunktion zurückgegriffen werden:
- $$H_{\rm quat} = 2 \cdot p \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{\hspace{0.1cm}p\hspace{0.1cm} } + 2 \cdot (0.5-p) \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{0.5-p}$$
- $$\Rightarrow \hspace{0.3cm} H_{\rm quat} = 1 + H_{\rm bin}(2p) \hspace{0.05cm}.$$
Die Grafik zeigt abhängig von $p$
- den Entropieverlauf der Quaternärquelle (blau)
- im Vergleich zum Entropieverlauf der Binärquelle (rot).
Für die Quaternärquelle ist nur der Abszissen $0 ≤ p ≤ 0.5$ zulässig.
Man erkennt aus der blauen Kurve für die Quaternärquelle:
- Die maximale Entropie $H_\text{max} = 2 \; \rm bit/Symbol$ ergibt sich für $p = 0.25$ ⇒ gleichwahrscheinliche Symbole: $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm A} = 0.25$.
- Mit $p = 0$ entartet die Quaternärquelle zur Binärquelle mit $p_{\rm B} = p_{\rm C} = 0.5$ und $p_{\rm A} = p_{\rm D} = 0$ ⇒ Entropie $H = 1 \; \rm bit/Symbol$. Ähnliches gilt für $p = 0.5$.
- Die Quelle mit $p_{\rm A} = p_{\rm D} = 0.1$ und $p_{\rm B} = p_{\rm C} = 0.4$ weist folgende Kennwerte auf (jeweils mit der Pseudoeinheit „bit/Symbol”):
- (1) Entropie: $H = 1 + H_{\rm bin} (2p) =1 + H_{\rm bin} (0.2) = 1.722,$
- (2) Redundanz: ${\rm \Delta }H = {\rm log_2}\hspace{0.1cm} M - H =2- 1.722= 0.278,$
- (3) relative Redundanz: $r ={\rm \Delta }H/({\rm log_2}\hspace{0.1cm} M) = 0.139\hspace{0.05cm}.$
- Die Redundanz der Quaternärquelle mit $p = 0.1$ ist gleich $ΔH = 0.278 \; \rm bit/Symbol$ und damit genau so groß wie die Redundanz der Binärquelle mit $p = 0.2$.
Aufgaben zum Kapitel
Aufgabe 1.1Z: Binäre Entropiefunktion
Aufgabe 1.2: Entropie von Ternärquellen
Quellenverzeichnis
- ↑ Shannon, C.E.: A Mathematical Theory of Communication. In: Bell Syst. Techn. J. 27 (1948), S. 379-423 und S. 623-656.
