Aufgaben:Exercise 1.2: Entropy of Ternary Sources

• Return to book

Wahrscheinlichkeiten zweier Ternärquellen

Die Entropie einer wertdiskreten gedächtnislosen Nachrichtenquelle mit $M$ möglichen Symbolen lautet:

$$H = \sum_{\mu = 1}^M p_{\mu} \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{p_\mu}\hspace{0.05cm},\hspace{0.3cm} {\rm Pseudoeinheit\hspace{-0.15cm}: \hspace{0.15cm}bit}\hspace{0.05cm}.$$

Hierbei bezeichnen die $p_\mu$ die Auftrittswahrscheinlichkeiten der einzelnen Symbole bzw. Ereignisse. Im vorliegenden Beispiel werden die Ereignisse mit $\rm R$(ot), $\rm G$(rün) und $\rm S$(chwarz) bezeichnet.

• Bei einer binären Quelle mit den Auftrittswahrscheinlichkeiten $p$  und  $1-p$  kann hierfür geschrieben werden:

$$H = H_{\rm bin}(p) = p \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{p}+ (1-p) \cdot {\rm log}_2\hspace{0.1cm}\frac{1}{1-p}\hspace{0.05cm},\hspace{0.3cm} {\rm Pseudoeinheit\hspace{-0.15cm}: \hspace{0.15cm}bit}\hspace{0.05cm}.$$

• Die Entropie einer mehrstufigen Quelle lässt sich häufig mit dieser „binären Entropiefunktion” $H_{\rm bin}(p)$ ausdrücken.

Betrachtet werden in dieser Aufgabe zwei Ternärquellen mit den Symbolwahrscheinlichkeiten gemäß der obigen Grafik:

• die Quelle $\rm Q_1$ mit  $p_{\rm G }= 1/2$,  $p_{\rm S }= 1/3$  und  $p_{\rm R }= 1/6$,
• die Quelle $\rm Q_2$ mit  $p_{\rm G }= p$  sowie  $p_{\rm S } = p_{\rm R } = (1-p)/2$.

Die Ternärquelle $\rm Q_2$ lässt sich auch auf das Roulette anwenden, wenn ein Spieler nur auf die Felder $\rm R$, $\rm S$chwarz und $\rm G$rün (die „Null”) setzt. Dieser Spieltyp wird im Fragebogen mit „Roulette 1” bezeichnet.

Dagegen weist „Roulette 2” darauf hin, dass der Spieler auf einzelne Zahlen $(0$, ... , $36)$ setzt.

Hinweis:

• Die Aufgabe gehört zum Kapitel Gedächtnislose Nachrichtenquellen.

Fragebogen

1

Welche Entropie $H$ besitzt die Quelle $\rm \underline{Q_1}$?

$H \ = \ $ $\ \rm bit$

2

Welche der folgenden Aussagen sind zutreffend, wenn man $\rm R$, $\rm G$ und $\rm S$ durch die Zahlenwerte $-1$,  $0$  und  $+1$ darstellt?

	Es ergibt sich eine kleinere Entropie.
	Die Entropie bleibt gleich.
	Es ergibt sich eine größere Entropie.

3

Bestimmen Sie die Entropie der Quelle $\rm \underline{Q_2}$ unter Verwendung der binären Entropiefunktion $H_{\rm bin}(p)$.
Welcher Wert ergibt sich für $\underline{p = 0.5}$?

$H \ = \ $ $\ \rm bit$

4

Für welchen $p$–Wert der Quelle $\rm \underline{Q_2}$ergibt sich die maximale Entropie: $H → H_\text{max}$?

$p \ = \ $

5

Welche Entropie hat die Nachrichtenquelle $\text{Roulette 1}$, also hinsichtlich der Ereignisse $\rm R$ot, $\rm S$chwarz und $\rm G$rün (die „Null”)?

$H \ = \ $ $\ \rm bit$

6

Welche Entropie weist $\text{Roulette 2}$ auf, also hinsichtlich der Zahlen $0$, ... , $36$?

$H \ = \ $ $\ \rm bit$

Musterlösung

Solution

(1)  Mit den Auftrittswahrscheinlichkeiten $1/2$, $1/3$ und $1/6$ erhält man folgenden Entropiewert:

$$H \hspace{0.1cm} = \hspace{0.1cm} 1/2 \cdot {\rm log}_2\hspace{0.1cm}(2) +1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) +1/6 \cdot {\rm log}_2\hspace{0.1cm}(6) =(1/2 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(2) + (1/3 + 1/6)\cdot {\rm log}_2\hspace{0.1cm}(3) \hspace{0.15cm}\underline {\approx 1.46 \, {\rm bit}} \hspace{0.05cm}.$$

(2)  Richtig ist der Lösungsvorschlag 2:

• Die Entropie hängt nur von den Auftrittswahrscheinlichkeiten ab.
• Es ist dabei egal, welche Zahlenwerte oder physikalische Größen man den einzelnen Symbolen zuordnet.
• Anders ist es bei Mittelwerten oder der AKF–Berechnung. Werden nur Symbole angegeben, so kann man hierfür keine Momente angeben.
• Außerdem hängen die Mittelwerte, Autokorrelation, usw. davon ab, ob man die Zuordnung bipolar $(-1, \hspace{0.05cm}0, \hspace{0.05cm}+1)$ oder unipolar (zum Beispiel: $(0, \hspace{0.05cm}1, \hspace{0.05cm}2)$ vereinbart.

(3)  Die Entropie der Quelle $\rm Q_2$ lässt sich wie folgt ausdrücken:

$$H \hspace{0.1cm} = \hspace{0.1cm} p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ 2 \cdot \frac{1-p}{2} \cdot {\rm log}_2\hspace{0.1cm}\frac {2}{1-p}= p \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{p}+ (1-p) \cdot {\rm log}_2\hspace{0.1cm}\frac {1}{1-p} + (1-p)\cdot {\rm log}_2\hspace{0.1cm}(2)= H_{\rm bin}(p) + 1-p \hspace{0.05cm}.$$

Für $p = 0.5$   ⇒   $H_{\rm bin}(p) = 1$ ergibt sich $\underline{H = 1.5\hspace{0.05cm}\rm bit}$.

(4)  Die maximale Entropie einer gedächtnislosen Quelle mit dem Symbolumfang $M$ ergibt sich, wenn alle $M$ Symbole gleichwahrscheinlich sind.

• Für den Sonderfall $M=3$ folgt daraus:

$$p_{\rm R} + p_{\rm G} + p_{\rm S} = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline {p = 1/3 = 0.333}\hspace{0.05cm}.$$

• Damit erhält man mit dem Ergebnis der Teilaufgabe (3) die folgende Entropie:

$$H = H_{\rm bin}(1/3) + 1-1/3 = 1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3/2) + 2/3 $$

$$\Rightarrow \hspace{0.3cm}H = 1/3 \cdot {\rm log}_2\hspace{0.1cm}(3) + 2/3 \cdot {\rm log}_2\hspace{0.1cm}(3) - 2/3 \cdot {\rm log}_2\hspace{0.1cm}(2)+ 2/3 = {\rm log}_2\hspace{0.1cm}(3) = {1.585 \, {\rm bit}} \hspace{0.05cm}.$$

(5)  Das System $\text{Roulette 1}$ ist informationstheoretisch gleich der Konfiguration $\rm Q_2$ mit $p = 1/37$:

$$p_{\rm G} = p = \frac{1}{37}\hspace{0.05cm},\hspace{0.2cm} p_{\rm R} = p_{\rm S} = \frac{1-p}{2} = \frac{18}{37} \hspace{0.05cm}.$$

Damit erhält man mit dem Ergebnis der Teilaufgabe (3):

$$H = H_{\rm bin}(1/37) + \frac{36}{37} = \frac{1}{37} \cdot {\rm log}_2\hspace{0.1cm}(37) + \frac{36}{37} \cdot {\rm log}_2\hspace{0.1cm}(37) - \frac{36}{37} \cdot {\rm log}_2\hspace{0.1cm}36 + \frac{36}{37} = {\rm log}_2\hspace{0.1cm}(37) + \frac{36}{37} \cdot ( 1- {\rm log}_2\hspace{0.1cm}(36)) = 5.209 - 4.057 \hspace{0.15cm} \underline { = 1.152 \, {\rm bit}} \hspace{0.05cm}.$$

(6)  Setzt man bei Roulette auf einzelne Zahlen   ⇒   Konfiguration $\text{Roulette 2}$, so sind alle Zahlen von $0$ bis $36$ gleichwahrscheinlich und man erhält:

$$H = {\rm log}_2\hspace{0.1cm}(37) \hspace{0.15cm} \underline { = 5.209 \, {\rm bit}} \hspace{0.05cm}.$$