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.

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

Im Buch „Digitalsignalübertragung” – Kapitel 2.4 wurde der AMI–Pseudoternärcode behandelt. Dieser wandelt die Binärfolge 〈 $q_ν$ 〉 mit $q_ν$ ∈ {L, H} in die Ternärfolge 〈 $c_ν$ 〉 mit $c_ν$ ∈ {M, N, P}. Die Bezeichnungen der Quellensymbole stehen für „Low” und „High” und die der Codesymbole für „Minus”, „Null” und „Plus”. Die Codierregel des AMI–Codes (diese Kurzform steht für „Alternate Mark Inversion”) lautet:

• Jedes Binärsymbol $q_ν$ = L wird durch das Codesymbol $c_ν$ = N dargestellt.
• Dagegen wird $q_ν$ = H abwechselnd mit $c_ν$ = P und $c_ν$ = M codiert ⇒ Name „AMI”.

Durch die Codierung wird Redundanz hinzugefügt mit dem Ziel, dass die Codefolge keinen Gleichanteil beinhaltet. Wir betrachten hier jedoch nicht die spektralen Eigenschaften des AMI–Codes, sondern interpretieren diesen Code informationstheoretisch:

• Aufgrund der Stufenzahl $M$ = 3 ist der Entscheidungsgehalt der (ternären) Codefolge gleich $H_0$ = $\log_2$ 3 ≈ 1.585 bit/Symbol. Die erste Entropienäherung liefert $H_1$ = 1.5 bit/Symbol, wie nachfolgende Rechnung zeigt:

• Betrachten wir nun Zweiertupel. Beim AMI–Code kann „P” nicht auf „P” und „M” nicht auf „M” folgen. Die Wahrscheinlichkeit für „NN” ist gleich $p_L · p_L$ = 1/4. Alle anderen (sechs) Zweiertupel treten mit der Wahrscheinlichkeit 1/8 auf. Daraus folgt für die zweite Entropienäherung:

• Für die weiteren Entropienäherungen und die tatsächliche Entropie $H$ wird gelten:

• Bei diesem Beispiel kennt man die tatsächliche Entropie $H$ der Codesymbolfolge 〈 $c_ν$ 〉. Da durch den Coder keine neue Information hinzukommt, aber auch keine verloren geht, ergibt sich die gleiche Entropie wie für die redundanzfreie Binärfolge 〈 $q_ν$ 〉:

Aufgabe A1.4 zeigt den bereits beträchtlichen Aufwand zur Berechnung der Entropienäherung $H_3$; zudem weicht $H_3$ noch deutlich vom Endwert $H$ = 1 bit/Symbol ab. Schneller kommt man zum Ergebnis, wenn man den AMI–Code durch eine Markovkette beschreibt.

Binärquellen mit Markoveigenschaften

Folgen mit statistischen Bindungen zwischen den Folgenelementen (Symbolen) werden oft durch Markovprozesse modelliert, wobei wir uns hier auf Markovprozesse erster Ordnung beschränken. Zunächst betrachten wir einen binären Markovprozess ( $M$ = 2 ) mit den Zuständen (Symbolen) A und B. Oben sehen Sie das Übergangsdiagramm für einen binären Markovprozess erster Ordnung. Von den vier angegebenen Übertragungswahrscheinlichkeiten sind allerdings nur zwei frei wählbar, zum Beispiel

• $p_{\text{A|B}}$ = Pr(A|B) ⇒ bedingte Wahrscheinlichkeit, dass A auf B folgt.
• $p_{B|A}$ = Pr(B|A) ⇒ bedingte Wahrscheinlichkeit, dass B auf A folgt.

Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann

Aufgrund der vorausgesetzten Eigenschaften Stationarität und Ergodizität gilt für die Zustands– bzw. Symbolwahrscheinlichkeiten:

Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:

• Für $p_{A|B}$ = $p_{B|A}$ ergeben sich gleichwahrscheinliche Symbole ⇒ $p_A$ = $p_B$ = 0.5. Damit liefert die erste Entropienäherung $H_1$ = $H_0$ = 1 bit/Symbol, und zwar unabhängig von den tatsächlichen Werten der (bedingten) Übergangswahrscheinlichkeiten $p_{A|B}$ bzw. $p_{B|A}$.
• Die Quellenentropie $H$ als der Grenzwert der Entropienäherung $k$–ter Ordnung $H_k$ für $k$ → ∞ hängt aber sehr wohl von den tatsächlichen Werten von $p_{A|B}$ und $p_{B|A}$ ab und nicht nur von ihrem Quotienten. Dies zeigt das folgende Beispiel.

Wir gehen von einer binären Markovquelle erster Ordnung aus und setzen nun voraus:

• Die 4 bedingten Wahrscheinlichkeiten seien symmetrisch, das heißt, es gelte pA|B = pB|A, pA|A = pB|B.
• Für die beiden Symbolwahrscheinlichkeiten gilt somit: pA = pB = 0.5.

Wir betrachten hier drei solche binäre Markovquellen, die sich durch die Zahlenwerte der symmetrischen Übergangswahrscheinlichkeiten pA|B = pB|A unterscheiden. Die beiden anderen Übergangswahrscheinlichkeiten haben dann folgende Werte: pA|A = 1 – pB|A = pB|B.

Die mittlere Symbolfolge (mit pA|B = pB|A = 0.5) besitzt die Entropie H = 1 bit/Symbol. Das heißt: In diesem Sonderfall gibt es keine statistischen Bindungen innerhalb der Folge. Die linke (rote) Folge mit pA|B = pB|A = 0.2 weist weniger Wechsel zwischen A und B auf. Aufgrund von statistischen Abhängigkeiten zwischen benachbarten Symbolen ist nun H ≈ 0.72 bit/Symbol kleiner. Die rechte (grüne) Symbolfolge mit pA|B = pB|A = 0.8 hat die genau gleiche Entropie wie die rote Folge. Hier erkennt man viele Bereiche mit sich stets abwechselnden Symbolen (... ABABAB ... ). Zu diesem Beispiel ist noch anzumerken: Hätte man nicht die Markoveigenschaften der roten und der grünen Folge ausgenutzt, so hätte man das Ergebnis H ≈ 0.72 bit/Symbol erst nach langwierigen Berechnungen erhalten. Auf den nächsten Seiten wird gezeigt, dass bei einer Quelle mit Markoveigenschaften dieser Endwert H allein aus den Entropienäherungen H1 und H2 ermittelt werden kann. Ebenso lassen sich aus H1 und H2 alle Entropienäherungen Hk für k–Tupel in einfacher Weise berechnen ⇒ H3, H4, H5, ... , H100, ...

Nichtbinäre Markovquellen

Aufgaben zu Kapitel 1.2