Difference between revisions of "Aufgaben:Exercise 1.3: Entropy Approximations"

Revision as of 19:26, 8 May 2021

Different binary sequences

The diagram shows four symbol sequences $\langle q_\nu \rangle $ , each with length $N = 60$. The source symbols are $\rm A$ and $\rm B$ respectively.

It follows directly that $H_0 = 1 \; \rm bit/symbol$ applies to the decision content of all sources considered.
However, the symbols $\rm A$ and $\rm B$ do not occur with equal probability, but with the probabilities $p_{\rm A}$ and $p_{\rm B}$.

In addition to $H_0$ , the table below shows the entropy approximations

$H_1$, based on $p_{\rm A}$ und $p_{\rm B}$ (column 2),
$H_2$, based on two-tuples (column 3),
$H_3$, based on three-tuples (column 4),
$H_4$, based on four-tuples (column 5),
the actual entropy $H$, which is obtained from $H_k$ by the boundary transition for $k \to \infty$ (last column).

Zwischen diesen Entropien bestehen folgende Größenrelationen: $H \le$ ... $\le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$

Nicht bekannt ist die Zuordnung zwischen den Quellen $\rm Q1$, $\rm Q2$, $\rm Q3$, $\rm Q4$ und den in der Grafik gezeigten gezeigten Symbolfolgen (Schwarz, Blau, Rot, Grün).
Es ist lediglich bekannt, dass die Quelle $\rm Q4$ einen Wiederholungscode beinhaltet. Aufgrund der Tatsache, dass bei der entsprechenden Symbolfolge jedes zweite Symbol keinerlei Information lierfert, ist $H_0 = 0.5 \; \rm bit/Symbol$.
Zudem sind die Entropienäherungen $H_1 = 1 \; \rm bit/Symbol$ (gleichwahrscheinliche Symbole) und $H_4 \approx 0.789 \; \rm bit/Symbol$ gegeben.

Zu bestimmen sind für diese Nachrichtenquelle $\rm Q4$ schließlich noch die Entropienäherungen $H_2$ und $H_3$.

Quellenentropie und Näherungen in „bit/Symbol”

Hinweise:

Die Aufgabe gehört zum Kapitel Nachrichtenquellen mit Gedächtnis.

Für die $k$–te Entropienäherung gilt bei Binärquellen $(M = 2)$ mit der Verbundwahrscheinlichkeit $ p_i^{(k)}$ eines $k$–Tupels:

$$H_k = \frac{1}{k} \cdot \sum_{i=1}^{2^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}.$$

Fragebogen

Musterlösung

Solution

(1) Die schwarze Binärfolge stammt von der Quelle $\underline{\rm Q3}$,

da die Symbole gleichwahrscheinlich sind ⇒ $H_1 = H_0$ und
keine statistischen Bindungen zwischen den Symbolen bestehen ⇒ $H=$ ... $= H_2 = H_1$.

(2) Man erkennt bei der blauen Binärfolge, dass $\rm A$ sehr viel häufiger auftritt als $\rm B$, so dass $H_1 < H_0$ gelten muss.

Entsprechend der Tabelle erfüllt nur die Quelle $\underline{\rm Q1}$ diese Bedingung.
Aus $H_1 = 0.5 \; \rm bit/Symbol$ kann man die Symbolwahrscheinlichkeiten $p_{\rm A} = 0.89$ und $p_{\rm B} = 0.11$ ermitteln.

(3) Durch Ausschlussverfahren kommt man für die rote Binärfolge zum Ergebnis $\underline{\rm Q2}$:

Die Quelle $\rm Q1$ gehört nämlich zur blauen Folge, $\rm Q3$ zur schwarzen und $\rm Q4$ zum Wiederholungscode und damit offensichtlich zur grünen Symbolfolge.
Die rote Symbolfolge weist folgende Eigenschaften auf:

Wegen $H_1 = H_0$ sind die Symbole gleichwahrscheinlich: $p_{\rm A} = p_{\rm B} = 0.5$.
Wegen $H < H_1$ bestehen statistische Bindungen innerhalb der Folge.

Diese erkennt man daran, dass es zwischen $\rm A$ und $\rm B$ mehr Übergänge als bei statistischer Unabhängigkeit gibt.

(4) Bei der grünen Symbolfolge $($Quelle $\rm Q4)$ sind die Symbole $\rm A$ und $\rm B$ gleichwahrscheinlich:

Symbolfolgen eines binären Wiederholungscodes

$$p_{\rm A} = p_{\rm B} = 0.5 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}H_1 = 1\,{\rm bit/Symbol} \hspace{0.05cm}.$$

Zur $H_2$-Ermittlung betrachtet man Zweiertupel. Die Verbundwahrscheinlichkeiten $p_{\rm AA}$, $p_{\rm AB}$, $p_{\rm BA}$ und $p_{\rm BB}$ können daraus berechnet werden. Aus der Skizze erkennt man:

Die Kombinationen $\rm AB$ und $\rm BA$ sind nur dann möglich, wenn ein Tupel bei geradzahligem $\nu$ beginnt. Für die Verbundwahrscheinlichkeiten $p_{\rm AB}$ und $p_{\rm BA}$ gilt dann:

$$p_{\rm AB} \hspace{0.1cm} = \hspace{0.1cm} {\rm Pr}(\nu {\rm \hspace{0.15cm}ist\hspace{0.15cm}gerade}) \cdot {\rm Pr}( q_{\nu} = \mathbf{A}) \cdot {\rm Pr}(q_{\nu+1} = \mathbf{B}\hspace{0.05cm} | q_{\nu} = \mathbf{A}) = {1}/{2} \cdot {1}/{2} \cdot {1}/{2} = {1}/{8} = p_{\rm BA} \hspace{0.05cm}.$$

Dagegen gelten für die beiden weiteren Kombinationen $\rm AA$ und $\rm BB$:

$$p_{\rm AA} ={\rm Pr}(\nu = 1) \cdot {\rm Pr}( q_1 = \mathbf{A}) \cdot {\rm Pr}(q_{2} = \mathbf{A}\hspace{0.05cm} | q_{1} = \mathbf{A}) + {\rm Pr}(\nu=2) \cdot {\rm Pr}( q_{2} = \mathbf{A}) \cdot {\rm Pr}(q_{3} = \mathbf{A}\hspace{0.05cm} | q_{2} = \mathbf{A}) \hspace{0.05cm}.$$

$$\Rightarrow \hspace{0.3cm}p_{\rm AA} = \frac{1}{2} \cdot \frac{1}{2} \cdot 1+ \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{8} = p_{\rm BB} \hspace{0.05cm}.$$

Hierbei steht $\nu = 1$ für alle ungeradzahligen Indizes und $\nu = 2$ für alle geradzahligen Indizes.

Damit ergibt sich für die Entropienäherung:

$$H_2 = \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.15cm} \underline {= 0.906 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

(5) Nach ähnlichem Vorgehen kommt man bei Dreiertupeln zu den Verbundwahrscheinlichkeiten

$$p_{\rm AAA} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm BBB} = 1/4 \hspace{0.05cm},\hspace{0.2cm} p_{\rm ABA} = p_{\rm BAB} = 0 \hspace{0.05cm},\hspace{0.2cm} p_{\rm AAB} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm ABB} = p_{\rm BBA} = p_{\rm BAA} = 1/8$$

und daraus zur Entropienäherung

$$H_3 = \frac{1}{3} \cdot \left [ 2 \cdot \frac{1}{4} \cdot {\rm log}_2\hspace{0.1cm}(4) + 4 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}(8)\right ] = \frac{2.5}{3} \hspace{0.15cm} \underline {= 0.833 \,{\rm bit/Symbol}} \hspace{0.05cm}.$$

Zur Berechnung von $H_4$ ergeben sich folgende $16$ Wahrscheinlichkeiten:

$$p_{\rm AAAA} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm BBBB} = 3/16 \hspace{0.05cm},\hspace{0.2cm} p_{\rm AABB} = p_{\rm BBAA} = 2/16 \hspace{0.05cm},$$

$$ p_{\rm AAAB} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm ABBA} = p_{\rm ABBB} = p_{\rm BBBA} = p_{\rm BAAB} = p_{\rm BAAA}= 1/16 \hspace{0.05cm}$$

$$ p_{\rm AABA} \hspace{0.1cm} = \hspace{0.1cm} p_{\rm ABAA} = p_{\rm ABAB} = p_{\rm BBAB} = p_{\rm BABB} = p_{\rm BABA}= 0\hspace{0.05cm}.$$

Daraus folgt:

$$H_4= \frac{1}{4} \hspace{-0.05cm}\cdot \hspace{-0.05cm}\left [ 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{3}{16} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.1cm}\frac{16}{3} + 2 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{1}{8} \hspace{-0.05cm}\cdot \hspace{-0.05cm}{\rm log}_2\hspace{0.1cm}(8) + 6 \hspace{-0.05cm}\cdot \hspace{-0.05cm} \frac{1}{16} \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.1cm}(16)\right ] =\frac{\left [ 6 \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.01cm}(16) - 6 \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.01cm}(3) + 4 \hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.01cm}(8) + 6\hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.01cm}(16)\right ]}{32} .$$

Man erkennt:

Auch die Näherung $H_4 = 0.789\,{\rm bit/Symbol}$ weicht noch deutlich vom Entropie-Endwert $H = 0.5\,{\rm bit/Symbol}$ ab.
Der Wiederholungscode kann offensichtlich nicht durch eine Markovquelle modelliert werden. Wäre $\rm Q4$ eine Markovquelle, so müsste nämlich gelten:

$$H = 2 \cdot H_2 - H_1 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}H_2 = 1/2 \cdot (H+H_1) = 1/2 \cdot (0.5+1) = 0.75 \,{\rm bit/Symbol}\hspace{0.05cm}.$$

@@ Line 3: / Line 3: @@
 }}
-[[File:Inf_A_1_3_vers2.png|right|frame|Verschiedene Binärfolgen]]
+[[File:Inf_A_1_3_vers2.png|right|frame|Different binary sequences]]
-Die Grafik zeigt vier Symbolfolgen&nbsp; $\langle q_\nu \rangle $&nbsp; mit jeweiliger Länge&nbsp; $N = 60$.&nbsp; Die Quellensymbole sind jeweils&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$.
+The diagram shows four symbol sequences&nbsp; $\langle q_\nu \rangle $&nbsp;, each with length&nbsp; $N = 60$.&nbsp; The source symbols are&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$ respectively.
-*Daraus folgt direkt, dass für den Entscheidungsgehalt aller betrachteten Quellen&nbsp; $H_0 = 1 \; \rm bit/Symbol$&nbsp; gilt.
+*It follows directly that&nbsp; $H_0 = 1 \; \rm bit/symbol$&nbsp; applies to the decision content of all sources considered.
-*Die Symbole&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$&nbsp; treten  jedoch nicht gleichwahrscheinlich auf, sondern mit den Wahrscheinlichkeiten&nbsp; $p_{\rm A}$&nbsp; und&nbsp; $p_{\rm B}$.
+*However, the symbols&nbsp; $\rm A$&nbsp; and&nbsp; $\rm B$&nbsp; do not occur with equal probability, but with the probabilities&nbsp; $p_{\rm A}$&nbsp; and&nbsp; $p_{\rm B}$.
-Die untere Tabelle zeigt neben&nbsp; $H_0$&nbsp; noch die Entropienäherungen
+In addition to&nbsp; $H_0$&nbsp;, the table below shows the entropy approximations
-* $H_1$,&nbsp; basierend auf&nbsp; $p_{\rm A}$&nbsp; und&nbsp; $p_{\rm B}$&nbsp; (Spalte 2),
+* $H_1$,&nbsp; based on&nbsp; $p_{\rm A}$&nbsp; und&nbsp; $p_{\rm B}$&nbsp; (column 2),
-* $H_2$,&nbsp; basierend auf Zweiertupel (Spalte 3),
+* $H_2$,&nbsp; based on two-tuples (column 3),
-* $H_3$,&nbsp; basierend auf Dreiertupel (Spalte 4),
+* $H_3$,&nbsp; based on three-tuples (column 4),
-* $H_4$,&nbsp; basierend auf Vierertupel (Spalte 5),
+* $H_4$,&nbsp; based on four-tuples (column 5),
-* die tatsächliche Entropie&nbsp; $H$, die sich aus&nbsp; $H_k$&nbsp; durch den Grenzübergang für&nbsp; $k \to \infty$&nbsp; ergibt (letzte Spalte).
+* the actual entropy&nbsp; $H$, which is obtained from&nbsp; $H_k$&nbsp; by the boundary transition for&nbsp; $k \to \infty$&nbsp; (last column).

	$\rm Q1$,
	$\rm Q2$,
	$\rm Q3$,
	$\rm Q4$.

	$\rm Q1$,
	$\rm Q2$,
	$\rm Q3$,
	$\rm Q4$.

	$\rm Q1$,
	$\rm Q2$,
	$\rm Q3$,
	$\rm Q4$.