Information Theory/Discrete Sources with Memory

1. Information Theory
2. Entropie wertdiskreter Nachrichtenquellen
3. Discrete Sources with Memory

• Previous page
• Next page

• Previous page
• Next page

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.

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. <div style="clear:both;"> </div> </div> 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$.

Die Entropie des AMI–Codes

Binärquellen mit Markoveigenschaften

Nichtbinäre Markovquellen

Aufgaben zu Kapitel 1.2