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

$$H \hspace{-0.05cm}= 0.4 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.4} + 0.3 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.3} +0.2 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.2} +0.1 \cdot {\rm log}_2\hspace{0.05cm}\frac {1}{0.1} \approx 1.84 \hspace{0.05cm}{\rm bit/Symbol} \hspace{0.01cm}.$$

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:

$${\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' = \sum_{q_{\nu} \in \{ q_{\mu}\hspace{-0.08cm} \}} \sum_{q_{\nu+1} \in \{ q_{\mu}\hspace{-0.08cm} \}}\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'$ noch halbiert werden:

$$H_2 = \frac{H_2'}{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 in Kapitel 1.1 definierte Entropie mit $H_1$:

$$H_1 = \sum_{q_{\nu}\in \{ q_{\mu}\hspace{-0.03cm} \}} {\rm Pr}(q_{\nu}) \cdot {\rm ld}\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$ = log2 $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$ 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.

[[File: P_ID2742__Inf_T_1_2_S2_neu.png|Ternäre Symbolfolge und Bildung von Zweier–Tupeln]] 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:

$$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 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.2cm}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.2cm}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 (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

$$H_2 = \frac{1}{2} \cdot \left [ \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}4 + \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}4 +\frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}4 +\frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}4 \right ] = 1 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

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:

$$\begin{align*}H_2 \hspace{-0.1cm}& = \hspace{-0.1cm} \frac{1}{2} \cdot \left [ 2 \cdot \frac{3}{8} \cdot {\rm log}_2\hspace{0.1cm}\frac {8}{3} + 2 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}8\right ] = \frac{3}{8} \cdot {\rm log}_2\hspace{0.1cm}8 - \frac{3}{8} \cdot{\rm log}_2\hspace{0.1cm}3 + \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}8 =\\ \hspace{-0.1cm}& = \hspace{-0.1cm} 1.5 -0.375 \cdot 1.585 = 0.906 \,{\rm bit/Symbol} < H_1 \hspace{0.05cm}.\end{align*}$$

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:

$$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 Näherung $H_2$ ergibt sich mit $k$ = 2.

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 Hk gelten folgende Größenrelationen (H0: Entscheidungsgehalt):

$$H \le ... \le H_k \le ... \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.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

$$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: „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:

$$H \le ... \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$ nennt man relative Redundanz ):

$$H = H_0 = H_1 = H_2 = H_3 = ...$$ $$\Rightarrow \hspace{0.3cm} 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 allerdings allein auf die Abweichung der Symbolwahrscheinlichkeiten von der Gleichverteilung zurück. Hier gelten folgende Relationen:

$$H = H_1 = H_2 = H_3 = ... \le H_0$$ $$\Rightarrow \hspace{0.3cm}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 < ... < H_3 < H_2 < H_1 \le H_0$$ $$\Rightarrow \hspace{0.3cm}0 < r = \frac{H_1 - H_0}{H_0}\le1 \hspace{0.05cm}.$$

• 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:

$$p_{\rm H} = p_{\rm L} = 1/2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} p_{\rm N} = p_{\rm L} = 1/2\hspace{0.05cm},\hspace{0.2cm}p_{\rm M} = p_{\rm P}= p_{\rm H}/2 = 1/4\hspace{0.05cm},$$

$$\Rightarrow \hspace{0.3cm} H_1 = 1/2 \cdot {\rm log}_2\hspace{0.1cm}2 + 2 \cdot 1/4 \cdot{\rm log}_2\hspace{0.1cm}4 = 1.5 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

• 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:

$$H_2 = 1/2 \cdot [ 1/4 \cdot {\rm ld}\hspace{0.1cm}4 + 6 \cdot 1/8 \cdot {\rm ld}\hspace{0.1cm}8 ] = 1.375 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

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

$$H < ... < H_5 < H_4 < H_3 < H_2 = 1.375 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

• 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_ν$ 〉:

$$H = 1 \,{\rm bit/Symbol} \hspace{0.05cm}.$$

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_{\text{B|A}}$ = Pr(B|A) ⇒ bedingte Wahrscheinlichkeit, dass B auf A folgt.

Für die beiden weiteren Übergangswahrscheinlichkeiten gilt dann

$$p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} = 1- p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} = 1- p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \hspace{0.05cm}.$$

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

$$p_{\rm A} = {\rm Pr}({\rm A}) = \frac{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = {\rm Pr}({\rm B}) = \frac{p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}}{p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} \hspace{0.05cm}.$$

Diese Gleichungen erlauben erste informationstheoretische Aussagen über Markovprozesse:

• Für $p_{\text{A|B}}$ = $p_{\text{B|A}}$ ergeben sich gleichwahrscheinliche Symbole ⇒ $p_{\text{A}}$ = $p_{\text{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_{\text{A|B}}$ bzw. $p_{\text{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_{\text{A|B}}$ und $p_{\text{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 $p_{\text{A|B}}$ = $p_{\text{B|A}}$, $p_{\text{A|A}}$ = $p_{\text{B|B}}$.
• Für die beiden Symbolwahrscheinlichkeiten gilt somit: $p_A$ = $p_B$ = 0.5.

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

• Die mittlere Symbolfolge (mit $p_{\text{A|B}}$ = $p_{\text{B|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 $p_{\text{A|B}}$ = $p_{\text{B|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 $p_{\text{A|B}}$ = $p_{\text{B|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 $H_1$ und $H_2$ ermittelt werden kann.
• Ebenso lassen sich aus H1 und H2 alle Entropienäherungen $H_k$ für $k$–Tupel in einfacher Weise berechnen ⇒ $H_3$, $H_4$, $H_5$, ... , $H_{100}$, ...

Wir gehen weiterhin von der symmetrischen binären Markovquelle erster Ordnung aus. Wie auf der vorherigen Seite verwenden wir folgende Nomenklatur:

• Übergangswahrscheinlichkeiten $p_{\text{B|A}}$, ...
• ergodische Wahrscheinlichkeiten $p_{\text{A}}$ und $p_{\text{B}}$,
• Verbundwahrscheinlichkeiten, zum Beispiel $p_{\text{AB}}$ = $p_{\text{A}}$ · $p_{\text{B|A}}$.

Wir berechnen nun die Entropie eines Zweiertupels (mit der Einheit „bit/Zweiertupel”):

$$\begin{align*}H_2' \hspace{-0.1cm}& = \hspace{-0.1cm} p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + \\ \hspace{-0.1cm}& + \hspace{-0.1cm} p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.\end{align*}$$

Ersetzt man nun die Logarithmen der Produkte durch entsprechende Summen von Logarithmen, so erhält man das Ergebnis $H_2'$ = $H_1$ + $H_{\text{M}}$ mit

$$\begin{align*}H_1 \hspace{-0.1cm}& = \hspace{-0.1cm} p_{\rm A} \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B} \cdot (p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} + p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B})\cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = \\ \hspace{-0.1cm}& = \hspace{-0.1cm} p_{\rm A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm A}} + p_{\rm B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p_{\rm B}} = H_{\rm bin} (p_{\rm A})= H_{\rm bin} (p_{\rm B}) \hspace{0.05cm},\end{align*}$$

$$\begin{align*}H_{\rm M} \hspace{-0.1cm}& = \hspace{-0.1cm} p_{\rm A} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}A}} + p_{\rm A} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}A}} + \\ \hspace{-0.1cm}& + \hspace{-0.1cm} p_{\rm B} \cdot p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm A\hspace{0.01cm}|\hspace{0.01cm}B}} + p_{\rm B} \cdot p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B} \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{ p_{\rm B\hspace{0.01cm}|\hspace{0.01cm}B}} \hspace{0.05cm}.\end{align*}$$

Damit lautet die zweite Entropienäherung (mit der Einheit „bit/Symbol”):

$$H_2 = \frac{H_2'}{2} = \frac{1}{2} \cdot [ H_{\rm 1} + H_{\rm M}] \hspace{0.05cm}.$$

Anzumerken ist:

• Der erste Summand wurde nicht zufällig mit $H_1$ abgekürzt, sondern ist tatsächlich gleich der ersten Entropienäherung, allein abhängig von den Symbolwahrscheinlichkeiten.
• Bei einem symmetrischen Markovprozess ( $p_{\text{A|B}}$ = $p_{\text{B|A}}$ ⇒ $p_{\text{A}}$ = $p_{\text{B}}$ = 1/2) ergibt sich für diesen ersten Summanden $H_1$ = 1 bit/Symbol.
• Der zweite Summand ( $H_{\text{M}}$ ) muss gemäß der zweiten der oberen Gleichungen berechnet werden. Bei einem symmetrischen Markovprozess erhält man $H_{\text{M}}$ = $H_{\text{bin}}(p_{\text{A|B}})$.

Im nächsten Abschnitt wird dieses Ergebnis auf die $k$–te Entropienäherung erweitert.

Der Vorteil von Markovquellen gegenüber anderen Quellen ist, dass sich die Entropieberechnung für $k$–Tupel sehr einfach gestaltet. Für jede Markovquelle gilt:

$$\begin{align*}H_k \hspace{-0.1cm}& = \hspace{-0.1cm} \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H_2 = \frac{1}{2} \cdot [ H_{\rm 1} + H_{\rm M}]\hspace{0.05cm},\\ H_3 \hspace{-0.1cm}& = \hspace{-0.1cm} \frac{1}{3} \cdot [ H_{\rm 1} + 2 \cdot H_{\rm M}] \hspace{0.05cm},\hspace{0.3cm} H_4 = \frac{1}{4} \cdot [ H_{\rm 1} + 3 \cdot H_{\rm M}] \hspace{0.05cm},\hspace{0.15cm}{\rm usw.}\end{align*}$$

Bildet man den Grenzübergang für $k$ → ∞, so erhält man für die tatsächliche Quellenentropie:

$$H = \lim_{k \rightarrow \infty } H_k = H_{\rm M} \hspace{0.05cm}.$$

Aus diesem einfachen Ergebnis folgen wichtige Erkenntnisse für die Entropieberechnung:

• Bei Markovquellen genügt die Bestimmung der Entropienäherungen $H_1$ und $H_2$. Damit lautet die Entropie einer Markovquelle:

$$H = 2 \cdot H_2 - H_{\rm 1} \hspace{0.05cm}.$$

• Durch $H_1$ und $H_2$ liegen auch alle weiteren Entropienäherungen $H_k$ fest:

$$H_k = \frac{2-k}{k} \cdot H_{\rm 1} + \frac{2\cdot (k-1)}{k} \cdot H_{\rm 2} \hspace{0.05cm}.$$

• Diese Näherungen haben allerdings keine große Bedeutung. Wichtig ist meist nur der Grenzwert $H$. Bei Quellen ohne Markoveigenschaften berechnet man die Näherungen $H_k$ nur deshalb, um den Grenzwert, also die tatsächliche Entropie, abschätzen zu können.
• Alle auf dieser Seite angegebenen Gleichungen gelten auch für nichtbinäre Markovquellen ( $M$ > 2 ), wie auf der nächsten Seite gezeigt wird.

Hinweis: In der Aufgabe A1.5 werden die obigen Gleichungen auf den allgemeineren Fall einer unsymmetrischen Binärquelle angewendet.

Nichtbinäre Markovquellen

Für jede Markovquelle gelten unabhängig vom Symbolumfang die folgenden Gleichungen:

$$H = 2 \cdot H_2 - H_{\rm 1} \hspace{0.05cm},\hspace{0.3cm} H_k = \frac{1}{k} \cdot [ H_{\rm 1} + (k-1) \cdot H_{\rm M}] \hspace{0.05cm},\hspace{0.3cm} \lim_{k \rightarrow \infty } H_k = H \hspace{0.05cm}.$$

Diese ermöglichen die einfache Berechnung der Entropie $H$ aus den Näherungen $H_1$ und $H_2$. Wir betrachten nun eine ternäre Markovquelle MQ3 (Stufenzahl $M$ = 3, blaue Farbgebung) und eine quaternäre Markovquelle MQ4 ( $M$ = 4, rot ) mit folgenden Übergangsdiagrammen:

In der Aufgabe A1.6 werden die Entropienäherungen $H_k$ und die jeweiligen Quellenentropien $H$ als der Grenzwert von $H_k$ für $k$ → ∞ berechnet. Die Ergebnisse sind in der folgenden Grafik zusammengestellt. Alle Entropien haben die Einheit „bit/Symbol”.

Die Ergebnisse lassen sich wie folgt interpretieren:

• Bei der ternären Markovquelle MQ3 nehmen die Entropienäherungen von $H_1$ = 1.500 über $H_2$ = 1.375 bis zum Grenzwert $H$ = 1.25 kontinuierlich ab. Wegen $M$ = 3 beträgt der Entscheidungsgehalt $H_0$ = 1.585 (alle Entropien in „bit/Symbol”) .
• Für die quaternäre Markovquelle MQ4 (rote Markierungen) erhält man $H_0$ = $H_1$ = 2 (wegen den vier gleichwahrscheinlichen Zuständen) und $H_2$ = 1.5. Aus dem $H_1$– und $H_2$–Wert lassen sich auch hier alle Entropienäherungen $H_k$ und auch der Endwert $H$ = 1 berechnen.
• Die beiden Quellenmodelle MQ3 und MQ4 entstanden bei dem Versuch, den AMI–Code informationstheoretisch durch Markovquellen zu beschreiben. Die Symbole M, N und P stehen hierbei für „Minus”, „Null” und „Plus”.
• Die Entropienäherungen $H_1$, $H_2$ und $H_3$ des AMI–Codes (grüne Markierungen) wurden in Aufgabe A1.4 berechnet. Auf die Berechnung von $H_4$, $H_5$, ... musste aus Aufwandsgründen verzichtet werden. Bekannt ist aber der Endwert von $H_k$ für $k$ → ∞ ⇒ $H$ = 1.
• Man erkennt, dass das Markovmodell MQ3 für $H_0$ = 1.585, $H_1$ = 1.500 und $H_2$ = 1.375 genau die gleichen Werte liefert wie der AMI–Code. Dagegen unterscheiden sich $H_3$ (1.333 gegenüber 1.292) und insbesondere der Endwert $H$ (1.25 gegenüber 1).
• Das Modell MQ4 ( $M$ = 4 ) unterscheidet sich vom AMI–Code ( $M$ = 3 ) hinsichtlich des Entscheidungsgehaltes $H_0$ und auch bezüglich aller Entropienäherungen $H_k$. Trotzdem ist MQ4 das geeignete Modell für den AMI–Code, da der Endwert $H$ = 1 übereinstimmt.
• Das Modell MQ3 liefert deshalb zu große Entropiewerte, da hier die Folgen PNP und MNM möglich sind, die beim AMI–Code nicht auftreten können. Bereits bei $H_3$ macht sich der Unterschied geringfügig bemerkbar, im Endwert $H$ deutlich (1.25 gegenüber 1).

Beim Modell MQ4 wurde der Zustand „Null” aufgespalten in zwei Zustände N und O:

• Hierbei gilt für den Zustand N: Das aktuelle Binärsymbol L wird mit dem Amplitudenwert „0” dargestellt, wie es der AMI–Regel entspricht. Das nächste auftretende H–Symbol wird als M (Minus) dargestellt, weil das letzte H–Symbol als P (Plus) codiert wurde.
• Auch beim Zustand O' wird das aktuelle Binärsymbol L mit dem Ternärwert „0” dargestellt. Im Unterschied zum Zustand N wird aber nun das nächste auftretende H–Symbol als P (Plus) dargestellt werden, da das letzte H–Symbol als M (Minus) codiert wurde.

Die von MQ4 ausgegebene Symbolfolge entspricht tatsächlich den Regeln des AMI–Codes und weist die Entropie $H$ = 1 bit/Symbol auf. Aufgrund des neuen Zustandes O ist nun allerdings $H_0$ = 2 bit/Symbol (gegenüber 1.585 bit/Symbol) deutlich zu groß und auch alle $H_k$–Näherungen sind größer als beim AMI–Code. Erst für $k$ → ∞ stimmen beide überein: $H$ = 1 bit/Symbol.