Nachrichtenquellen mit Gedächtnis
Inhaltsverzeichnis
Ein einfaches einführendes Beispiel
Zu Beginn des ersten Kapitels haben wir eine gedächtnislose Nachrichtenquelle mit dem Symbolvorrat { A, B, C, D} ⇒ $M$ = 4 betrachtet. Eine beispielhafte Symbolfolge ist in der nachfolgenden Grafik als Quelle Q1 nochmals dargestellt. Mit den Symbolwahrscheinlichkeiten $p_A$ = 0.4, $p_B$ = 0.3, $p_C$ = 0.2 und $p_D$ = 0.1 ergibt sich die Entropie zu
Aufgrund der ungleichen Auftrittswahrscheinlichkeiten der Symbole ist die Entropie kleiner als der Entscheidungsgehalt $H_0$ = log2 $M$ = 2 bit/Symbol.
Die Quelle Q2 ist weitgehend identisch mit der Quelle Q1, außer, dass jedes einzelne Symbol nicht nur einmal, sondern zweimal nacheinander ausgegeben wird: A ⇒ AA, B ⇒ BB, usw.. Es ist offensichtlich, dass Q2 eine kleinere Entropie (Unsicherheit) aufweist als Q1. Aufgrund des einfachen Wiederholungscodes ist nun $H$ = 1.84/2 = 0.92 bit/Symbol nur halb so groß, obwohl sich an den Auftrittswahrscheinlichkeiten nichts geändert hat. Dieses Beispiel zeigt:
- Die Entropie einer gedächtnisbehafteten Quelle ist kleiner als die Entropie einer gedächtnislosen Quelle mit gleichen Symbolwahrscheinlichkeiten.
- Es müssen nun auch die statistischen Bindungen innerhalb der Folge 〈 $q_ν$ 〉 berücksichtigt werden, nämlich die Abhängigkeit des Symbols $q_ν$ von den Vorgängersymbolen $q_{ν–1}$, $q_{ν–2}$
Entropie hinsichtlich Zweiertupel
Wir betrachten weiterhin die Quellensymbolfolge 〈 $q_1$, $q_2$, ... , $q_{ν–1}$, $q_ν$, $q_{ν+1}$, ...〉, interessieren uns aber nun für die Entropie zweier aufeinanderfolgender Quellensymbole. Alle Quellensymbole $q_ν$ entstammen einem Alphabet mit dem Symbolunfang $M$, so dass es für die Kombination ( $q_ν$, $q_{ν+1}$ ) genau $M^2$ mögliche Symbolpaare mit folgenden Verbundwahrscheinlichkeiten gibt:
Daraus ist die Verbundentropie eines Zweier–Tupels berechenbar:
Der Index 2 symbolisiert, dass sich die so berechnete Entropie auf Zweiertupel bezieht. Um den mittleren Informationsgehalt pro Symbol zu erhalten, muss $H_2'$ noch halbiert werden:
Um eine konsistente Nomenklatur zu erreichen, benennen wir nun die in Kapitel 1.1 definierte Entropie mit $H_1$:
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$ = log2 $M$ ergibt sich dann folgende Größenbeziehung:
Bei statistischer Unabhängigkeit der Folgenelemente ist $H_2$ gleich $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. Auf den nächsten Seiten werden die Aussagen dieser Seite anhand von Beispielen verdeutlicht.
Wir betrachten die Folge 〈 $q_1$, ... , $q_{50}$ 〉 entsprechend der folgernden Grafik:
- Die Folgenlänge ist $N$ = 50.
- Die Folgenelemente $q_ν$ entstammen dem Alphabet {A, B, C} ⇒ Symbolumfang $M$ = 3.
Durch Zeitmittelung über die 50 Symbole erhält man die Symbolwahrscheinlichkeiten $p_A$ ≈ 0.5, $p_B$ ≈ 0.3 und $p_C$ ≈ 0.2, womit man die Entropienäherung erster Ordnung berechnen kann:
Aufgrund der nicht gleichwahrscheinlichen Symbole ist $H_1$ < $H_0$ = 1.585 bit/Symbol. Als Näherung für die Wahrscheinlichkeiten von Zweiertupeln erhält man aus der obigen Folge:
Beachten Sie, dass aus den 50 Folgenelementen nur 49 Zweiertupel (AA, ... , CC) gebildet werden können, die in der obigen 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 ein etwas kleinerer Wert: $H_2$ ≈ 1.39 bit/Symbol.
Verdeutlichen wir uns die Berechnung der Entropienäherungen $H_1$ und $H_2$ an weiteren Beispielen.
Wir betrachten eine gedächtnislose Binärquelle mit gleichwahrscheinlichen Symbolen, das heißt es gelte $p_A$ = $p_B$ = 1/2.
- Die ersten zwanzig Folgeelemente lauten:
〈 $q_ν$ 〉 = BBAAABAABBBBBAAAABAB ...
- Aufgrund der gleichwahrscheinlichen Symbole und $M$ = 2 gilt:
$H_1$ = $H_0$ = 1 bit/Symbol.
- Die Verbundwahrscheinlichkeit $p_{AB}$ der Kombination AB ist gleich $p_A · p_B$ = 1/4. Ebenso gilt $p_{AA}$ = $p_{BB}$ = $p_{BA}$ = 1/4. Damit erhält man für die zweite Entropienäherung
Hinweis: Aus der oben angegebenen Folge ergeben sich aufgrund der kurzen Länge etwas andere Verbundwahrscheinlichkeiten, nämlich $p_{AA}$ = 6/19, $p_{BB}$ = 5/19 und $p_{AB}$ = $p_{BA}$ = 4/19.
Das nächste Beispiel liefert dagegen das Ergebnis $H_2$ < $H_1$.
Die zweite hier betrachtete Folge ergibt sich aus der oberen Folge durch Anwendung eines einfachen Wiederholungscodes (wiederholte Symbole in Grau): 〈 $q_ν$ 〉 = BBBBAAAAAABBAAAABBBB ...
- Aufgrund der gleichwahrscheinlichen Symbole und $M$ = 2 ergibt sich auch hier:
$H_1$ = $H_0$ = 1 bit/Symbol.
- Wie in Aufgabe A1.3 gezeigt wird, gilt aber nun für die Verbundwahrscheinlichkeiten $p_{AA}$ = $p_{BB}$ = 3/8 und $p_{AB}$ = $p_{BA}$ = 1/8. Daraus folgt:
Wenn man sich die Aufgabenstellung genauer betrachtet, kommt man zu dem Schluss, dass hier die Entropie $H$ = 0.5 bit/Symbol sein müsste (jedes zweite Symbol liefert keine neue Information). Die zweite Entropienäherung $H_2$ = 0.906 bit/Symbol ist aber deutlich größer als die Entropie $H$.
Dieses Beispiel legt den Schluss nahe, dass zur Entropiebestimmung die Näherung zweiter Ordnung nicht ausreicht. 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:
Die Laufvariable $i$ steht jeweils für eines der $M^k$ Tupel. Die Näherung $H_2$ ergibt sich mit $k$ = 2.
Die Entropie einer Nachrichtenquelle mit Gedächtnis ist der folgende Grenzwert:
Für die Entropienäherungen Hk gelten folgende Größenrelationen (H0: Entscheidungsgehalt):
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.048.576 Summenterme gemittelt werden. *Berücksichtigt man, dass jedes dieser $4^{10}$ = $2^{20}$ > $10^6$ $k$–Tupel bei Simulation und 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. <div class="example"> Wir betrachten eine alternierende Binärfolge ⇒ 〈 $q_ν$ 〉 = '''ABABABAB''' ... entsprechend $H_0$ = $H_1$ = 1 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_{AB}$ =$ p_{BA}$ = 1/2 ⇒ $H_2$ = 1/2 bit/Symbol, * $k$ = 3: $p_{ABA}$ = $p_{BAB}$ = 1/2 ⇒ $H_3$ = 1/3 bit/Symbol, * $k$ = 4: $p_{ABAB}$ =$p_{BABA}$ = 1/2 ⇒ $H_4$ = 1/4 bit/Symbol. Die Entropie dieser alternierenden Binärfolge ist demzufolge Dieses Ergebnis war zu erwarten, da die betrachtete Folge nur minimale Information besitzt, die sich allerdings im Entropie–Endwert $H$ nicht auswirkt, nämlich: „Tritt '''A''' zu den geraden oder ungeraden Zeitpunkten auf?” Man erkennt aber auch, dass $H_k$ diesem Endwert $H$ = 0 nur sehr langsam näher kommt: Die Näherung $H_{20} liefert immer noch 0.05 bit/Symbol.
Die Ergebnisse der letzten Seiten sollen hier kurz zusammengefasst werden:
- Allgemein gilt für die Entropie einer Nachrichtenquelle:
- 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$ nennt man relative Redundanz ):
- Eine gedächtnislose Quelle kann durchaus redundant sein ( $r$ > 0 ). Diese Redundanz geht dann allerdings allein auf die Abweichung der Symbolwahrscheinlichkeiten von der Gleichverteilung zurück. Hier gelten folgende Relationen:
- Die entsprechende Bedingung für eine gedächtnisbehaftete Quelle lautet:
- Ist $H_2$ < $H_1$, dann gilt (nach Meinung des Autors) auch $H_3$ < $H_2$, $H_4$ < $H_3$, ... , also es ist das „≤”–Zeichen in der allgemeinen Gleichung durch das „<”–Zeichen zu ersetzen. Sind die Symbole gleichwahrscheinlich, so gilt wieder $H_1$ = $H_0$, bei nicht gleichwahrscheinlichen Symbolen $H_1$ < $H_0$.
