Aufgaben:Aufgabe 1.3: Entropienäherungen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:Inf_A_1_3_vers2.png|right|Vier verschiedene Binärfolgen]]
+
[[Datei:Inf_A_1_3_vers2.png|right|frame|Verschiedene Binärfolgen]]
Die Grafik zeigt vier Symbolfolgen $\langle q_\nu \rangle $mit jeweilger Länge $N = 60$. Die Quellensymbole sind jeweils $\rm A$ und $\rm B$. Daraus folgt direkt, dass für den Entscheidungsgehalt aller betrachteten Quellen $H_0 = 1 \; \rm bit/Symbol$ gilt. Die Symbole $\rm A$ und $\rm B$ treten  jedoch nicht gleichwahrscheinlich auf, sondern mit den Wahrscheinlichkeiten $p_{\rm A}$ und $p_{\rm B}$.
+
Die Grafik rechts oben zeigt vier Symbolfolgen  $\langle q_\nu \rangle $  mit jeweiliger Länge  $N = 60$.  Die Quellensymbole sind jeweils  $\rm A$  und  $\rm B$.  
 +
*Daraus folgt direkt, dass für den Entscheidungsgehalt aller betrachteten Quellen  $H_0 = 1 \; \rm bit/Symbol$  gilt.  
 +
*Die Symbole  $\rm A$  und  $\rm B$  treten  jedoch nicht gleichwahrscheinlich auf, sondern mit den Wahrscheinlichkeiten  $p_{\rm A}$  und  $p_{\rm B}$.
  
Die folgende Tabelle zeigt neben $H_0$ noch die Entropienäherungen
+
 
* $H_1$, basierend auf $p_{\rm A}$ und $p_{\rm B}$ (Spalte 2),
+
Die untere Tabelle zeigt neben  $H_0$  noch die Entropienäherungen
* $H_2$, basierend auf Zweiertupel (Spalte 3),
+
* $H_1$,  basierend auf  $p_{\rm A}$  und  $p_{\rm B}$  (Spalte 2),
* $H_3$, basierend auf Dreiertupel (Spalte 4),
+
* $H_2$,  basierend auf Zweiertupel (Spalte 3),
* $H_4$, basierend auf Vierertupel (Spalte 5),
+
* $H_3$,  basierend auf Dreiertupel (Spalte 4),
* die tatsächliche Entropie $H$, die sich aus $H_k$ durch den Grenzübergang für $k \to \infty$ ergibt (letzte Spalte).
+
* $H_4$,  basierend auf Vierertupel (Spalte 5),
 +
* die tatsächliche Entropie  $H$, die sich aus  $H_k$  durch den Grenzübergang für  $k \to \infty$  ergibt (letzte Spalte).
  
  
 
Zwischen diesen Entropien bestehen folgende Größenrelationen:   $H \le$ ... $\le H_3 \le H_2 \le H_1 \le H_0 \hspace{0.05cm}.$
 
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 '''Q1''', '''Q2''', '''Q3''', '''Q4''' und den in der Grafik gezeigten gezeigten Symbolfolgen (Schwarz, Blau, Rot, Grün).  
+
*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 '''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
+
*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 die Entropie  $H = 0.5 \; \rm bit/Symbol$.  
 +
*Zudem sind die Näherungen  $H_1 = 1 \; \rm bit/Symbol$  und  $H_4 \approx 0.789 \; \rm bit/Symbol$  gegeben.
  
Zu bestimmen sind für diese Nachrichtenquelle schließlich noch die Entropienäherungen $H_2$ und $H_3$.
 
 
[[Datei:Inf_A_1_3b_vers2.png|Quellenentropie und Näherungen in „bit/Symbol”]]
 
  
 +
Zu bestimmen sind für diese Nachrichtenquelle  $\rm Q4$  schließlich noch die Entropienäherungen  $H_2$  und  $H_3$.
  
 +
[[Datei:Inf_A_1_3b_vers2.png|left|frame|Quellenentropie und Näherungen in „bit/Symbol”]]
 +
<br clear=all>
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis|Nachrichtenquellen mit Gedächtnis]].
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
*Für die $k$&ndash;te Entropienäherung gilt bei Binärquellen ($M = 2$) mit der Verbundwahrscheinlichkeit $ p_i^{(k)}$ eines $k$&ndash;Tupels:
+
*Für die&nbsp; $k$&ndash;te Entropienäherung gilt bei Binärquellen&nbsp; $(M = 2)$&nbsp; mit der Verbundwahrscheinlichkeit&nbsp; $ p_i^{(k)}$&nbsp; eines&nbsp; $k$&ndash;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})
 
:$$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}.$$
 
  \hspace{0.05cm}.$$
Zeile 35: Zeile 39:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Von welcher Quelle stammt die schwarze Symbolfolge?
+
{Von welcher Quelle stammt die <u>schwarze Symbolfolge</u>?
|type="[]"}
+
|type="()"}
- Q1,
+
- $\rm Q1$,
- Q2,
+
- $\rm Q2$,
+ Q3,
+
+ $\rm Q3$,
- Q4.
+
- $\rm Q4$.
  
  
{Von welcher Quelle stammt die blaue Symbolfolge?
+
{Von welcher Quelle stammt die <u>blaue Symbolfolge</u>?
|type="[]"}
+
|type="()"}
+ Q1,
+
+ $\rm Q1$,
- Q2,
+
- $\rm Q2$,
- Q3,
+
- $\rm Q3$,
- Q4.
+
- $\rm Q4$.
  
  
{Von welcher Quelle stammt die rote Symbolfolge?
+
{Von welcher Quelle stammt die <u>rote Symbolfolge</u>?
|type="[]"}
+
|type="()"}
- Q1,
+
- $\rm Q1$,
+ Q2,
+
+ $\rm Q2$,
- Q3,
+
- $\rm Q3$,
- Q4.
+
- $\rm Q4$.
  
  
{Berechnen Sie die Entropienäherung $H_2$ des Wiederholungscodes '''Q4'''.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_2$&nbsp; des Wiederholungscodes&nbsp; $\rm Q4$.
 
|type="{}"}
 
|type="{}"}
$H_2 \ = $ { 0.906 3% } $\ \rm bit/Symbol$
+
$H_2 \ = \ $ { 0.906 3% } $\ \rm bit/Symbol$
  
  
{Berechnen Sie die Entropienäherung $H_3$ des Wiederholungscodes  '''Q4'''.
+
{Berechnen Sie die Entropienäherung&nbsp; $H_3$&nbsp; des Wiederholungscodes&nbsp; $\rm Q4$.
 
|type="{}"}
 
|type="{}"}
$H_3 \ = $ { 0.833 3% } $\ \rm bit/Symbol$
+
$H_3 \ = \ $ { 0.833 3% } $\ \rm bit/Symbol$
  
  
Zeile 74: Zeile 78:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Es handelt sich um die <u>Quelle Q3</u>, da die Symbole gleichwahrscheinlich sind &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <i>H</i><sub>1</sub> = <i>H</i><sub>0</sub> und keine statistischen Bindungen zwischen den Symbolen bestehen &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <i>H</i> = .... = <i>H</i><sub>2</sub> = <i>H</i><sub>1</sub>.
+
'''(1)'''&nbsp; Die schwarze Binärfolge stammt von der Quelle&nbsp; $\underline{\rm Q3}$,  
 +
*da die Symbole gleichwahrscheinlich sind &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $H_1 = H_0$,&nbsp; und  
 +
*keine statistischen Bindungen zwischen den Symbolen bestehen &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $H=$ ... $= H_2 = H_1$.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Man erkennt bei der blauen Binärfolge, dass&nbsp; $\rm A$&nbsp; sehr viel häufiger auftritt als&nbsp; $\rm B$, so dass&nbsp; $H_1 < H_0$&nbsp; gelten muss.
 +
*Entsprechend der Tabelle erfüllt nur die Quelle&nbsp; $\underline{\rm Q1}$&nbsp; diese Bedingung.
 +
*Aus&nbsp; $H_1 = 0.5 \; \rm bit/Symbol$&nbsp; kann man die Symbolwahrscheinlichkeiten&nbsp; $p_{\rm A} = 0.89$&nbsp; und&nbsp; $p_{\rm B} = 0.11$&nbsp; ermitteln.
 +
 
  
:<b>2.</b>&nbsp;&nbsp;Man erkennt hier, dass <b>A</b> sehr viel häufiger auftritt als <b>B</b>, so dass <i>H</i><sub>1</sub> < <i>H</i><sub>0</sub> gelten muss. Entsprechend der Tabelle erfüllt nur die <u>Quelle Q1</u> diese Bedingung. Aus <i>H</i><sub>1</sub> = 0.5 bit/Symbol kann man die Symbolwahrscheinlichkeiten <i>p</i><sub>A</sub>&asymp; 0.89 und <i>p</i><sub>B</sub> &asymp; 0.11 ermitteln.
 
  
:<b>3.</b>&nbsp;&nbsp;Durch Ausschlussverfahren kommt man zum <u>Ergebnis Q2</u>: Die Quelle Q1 gehört zur schwarzen Folge, Q3 zur blauen und Q4 zum Wiederholungscode und damit offensichtlich zur grünen Symbolfolge. Die rote Symbolfolge weist folgende Eigenschaften auf:
+
'''(3)'''&nbsp; Durch Ausschlussverfahren kommt man für die rote Binärfolge zum Ergebnis&nbsp; $\underline{\rm Q2}$:  
 +
*Die Quelle&nbsp; $\rm Q1$&nbsp; gehört nämlich zur blauen Folge,&nbsp; $\rm Q3$&nbsp; zur schwarzen und&nbsp; $\rm Q4$&nbsp; zum Wiederholungscode und damit offensichtlich zur grünen Symbolfolge.  
 +
*Die rote Symbolfolge weist folgende Eigenschaften auf:
 +
:* Wegen&nbsp; $H_1 = H_0$&nbsp; sind die Symbole gleichwahrscheinlich: &nbsp; $p_{\rm A} = p_{\rm B} = 0.5$.
 +
:* Wegen&nbsp; $H < H_1$&nbsp; bestehen statistische Bindungen innerhalb der Folge.
 +
*Diese erkennt man daran, dass es zwischen&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$&nbsp; mehr Übergänge als bei statistischer Unabhängigkeit gibt.
  
:* Wegen <i>H</i><sub>1</sub> = <i>H</i><sub>0</sub> sind die Symbole gleichwahrscheinlich: <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = 0.5.
 
  
:* Wegen <i>H</i> < <i>H</i><sub>1</sub> bestehen statistische Bindungen innerhalb der Folge. Diese erkennt man daran, dass es mehr Übergänge zwischen <b>A</b> und <b>B</b> als bei statistischer Unabhängigkeit gibt.
 
  
:<b>4.</b>&nbsp;&nbsp;Bei der grünen Symbolfolge (Quelle Q4) sind die Symbole <b>A</b> und <b>B</b> gleichwahrscheinlich:
+
'''(4)'''&nbsp; Bei der grünen Symbolfolge&nbsp; $($Quelle $\rm Q4)$&nbsp; sind die Symbole&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$&nbsp; gleichwahrscheinlich:
 +
[[Datei:P_ID2247__Inf_A_1_3d.png|right|frame|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}
 
:$$p_{\rm A} = p_{\rm B} = 0.5 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}H_1 = 1\,{\rm bit/Symbol}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
[[Datei:P_ID2247__Inf_A_1_3d.png|right|Symbolfolgen eines binären Wiederholungscodes]]
+
Zur&nbsp; $H_2$&ndash;Ermittlung  betrachtet man Zweiertupel.&nbsp; Die Verbundwahrscheinlichkeiten&nbsp; $p_{\rm AA}$,&nbsp; $p_{\rm AB}$,&nbsp; $p_{\rm BA}$&nbsp; und&nbsp; $p_{\rm BB}$&nbsp; können daraus berechnet werden.&nbsp; Aus der Skizze erkennt man:
[[Datei:Inf_A_1_3d_vers2.png|right|Symbolfolgen eines binären Wiederholungscodes]]
+
* Die Kombinationen&nbsp; $\rm AB$&nbsp; und&nbsp; $\rm BA$&nbsp; sind nur dann möglich, wenn ein Tupel bei geradzahligem&nbsp; $\nu$&nbsp; beginnt.&nbsp; Für die Verbundwahrscheinlichkeiten&nbsp; $p_{\rm AB}$&nbsp; und&nbsp; $p_{\rm BA}$&nbsp; gilt dann:
:Zur Berechnung von <i>H</i><sub>2</sub> müssen Zweiertupel betrachtet und daraus die Verbundwahrscheinlichkeiten <i>p</i><sub>AA</sub>, <i>p</i><sub>AB</sub>, <i>p</i><sub>BA</sub> und <i>p</i><sub>BB</sub> berechnet werden. Aus der Skizze erkennt man:
+
:$$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}.$$
:* Die Kombinationen <b>AB</b> und <b>BA</b> sind nur dann möglich, wenn ein Tupel bei geradzahligem <i>&nu;</i> beginnt. Für die Verbundwahrscheinlichkeiten <i>p</i><sub>AB</sub> und <i>p</i><sub>BA</sub> gilt dann:
+
*Dagegen gelten für die beiden weiteren Kombinationen&nbsp; $\rm AA$&nbsp; und&nbsp; $\rm BB$:
:$$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}) = \\
+
:$$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.1cm} =  \hspace{0.1cm} \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8} = p_{\rm BA}
 
 
  \hspace{0.05cm}.$$
 
  \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}
:* Dagegen gelten für die beiden weiteren Kombinationen <b>AA</b> und <b>BB</b>:
 
:$$p_{\rm AA} \hspace{0.1cm} =  \hspace{0.1cm} {\rm Pr}(\nu {\rm \hspace{0.15cm}ist\hspace{0.15cm}ungerade,\hspace{0.15cm}zum\hspace{0.15cm}Beispiel\hspace{0.15cm}1})  \cdot {\rm Pr}( q_1 = \mathbf{A}) \cdot {\rm Pr}(q_{2} = \mathbf{A}\hspace{0.05cm} | q_{1} = \mathbf{A}) + \\
 
\hspace{0.1cm} +  \hspace{0.1cm} {\rm Pr}(\nu {\rm \hspace{0.15cm}ist\hspace{0.15cm}gerade,\hspace{0.15cm}zum\hspace{0.15cm}Beispiel\hspace{0.15cm}2})  \cdot {\rm Pr}( q_{2} = \mathbf{A}) \cdot {\rm Pr}(q_{3} = \mathbf{A}\hspace{0.05cm} | q_{2} = \mathbf{A}) = \\
 
  \hspace{0.1cm} = \hspace{0.1cm} \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}.$$
 
  \hspace{0.05cm}.$$
 +
:Hierbei steht&nbsp; $\nu = 1$&nbsp; für alle ungeradzahligen Indizes und&nbsp; $\nu = 2$&nbsp; für alle geradzahligen Indizes.
  
:Damit ergibt sich für die Entropienäherung:
+
*Damit ergibt sich für die Entropienäherung:
:$$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} +  
+
:$$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 ] =\\
+
  2 \cdot \frac{1}{8} \cdot {\rm log}_2\hspace{0.1cm}(8)\right ] =
=  \hspace{0.1cm}
 
 
  \frac{3}{8} \cdot  
 
  \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) =\\
+
{\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.1cm} =  \hspace{0.1cm} 1.5 -0.375 \cdot 1.585 \hspace{0.15cm} \underline {= 0.906 \,{\rm bit/Symbol}}  
 
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
:<b>5.</b>&nbsp;&nbsp;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},\\
+
'''(5)'''&nbsp; Nach ähnlichem Vorgehen kommt man bei Dreiertupeln zu den Verbundwahrscheinlichkeiten
p_{\rm AAB} \hspace{0.1cm} =  \hspace{0.1cm} p_{\rm ABB} = p_{\rm BBA} = p_{\rm BAA} = 1/8$$
+
:$$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
+
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) +  
 
:$$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}}  
 
  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}.$$
 
  \hspace{0.05cm}.$$
:Zur Berechnung von <i>H</i><sub>4</sub> ergeben sich folgende 16 Wahrscheinlichkeiten:
+
Zur Berechnung von&nbsp; $H_4$&nbsp;  ergeben sich folgende&nbsp; $16$&nbsp; 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 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
+
:$$ 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},\\
+
  \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}.$$
+
:$$ 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:
+
Daraus folgt:
:$$H_4 \hspace{0.2cm} \hspace{0.2cm} \frac{1}{4} \cdot \left [ 2 \cdot \frac{3}{16} \cdot {\rm log}_2\hspace{0.1cm}\frac{16}{3} +  
+
:$$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 \cdot \frac{1}{8} \cdot{\rm log}_2\hspace{0.1cm}(8) +  
+
  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 \cdot \frac{1}{16} \cdot {\rm log}_2\hspace{0.1cm}(16)\right ] =\\
+
  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}  
\hspace{0.1cm} \hspace{0.2cm} \left [ 6 \cdot
+
{\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}(16) - 6 \cdot {\rm log}_2\hspace{0.01cm}(3) + 4 \cdot  
+
{\rm log}_2\hspace{0.01cm}(8) + 6\hspace{-0.05cm}\cdot \hspace{-0.05cm} {\rm log}_2\hspace{0.01cm}(16)\right ]}{32} .$$
{\rm log}_2\hspace{0.01cm}(8) + 6 \cdot {\rm log}_2\hspace{0.01cm}(16)\right ]/32  {= 0.789 \,{\rm bit/Symbol}}  
+
Man erkennt:
\hspace{0.05cm}.$$
+
*Auch die Näherung&nbsp; $H_4 = 0.789\,{\rm bit/Symbol}$&nbsp; weicht noch deutlich vom Entropie-Endwert&nbsp; $H = 0.5\,{\rm bit/Symbol}$&nbsp; ab.
:Man erkennt, dass auch die Näherung <i>H</i><sub>4</sub> = 0.789 bit/Symbol noch weit vom tatsächlichen Entropiewert <i>H</i> = 0.5 bit/Symbol abweicht.
+
*Der Wiederholungscode kann offensichtlich nicht durch eine Markovquelle modelliert werden.&nbsp; Wäre&nbsp; $\rm Q4$&nbsp; eine Markovquelle, so müsste nämlich gelten:
 
 
:<b>Hinweis:</b> Der Wiederholungscode kann offensichtlich nicht durch eine Markovquelle modelliert werden. Wäre Q4 eine Markovquelle, so müsste nämlich gelten:
 
 
:$$H = 2 \cdot H_2 - H_1
 
:$$H = 2 \cdot H_2 - H_1
 
\hspace{0.3cm}\Rightarrow\hspace{0.3cm}H_2 = 1/2 \cdot (H+H_1) =  
 
\hspace{0.3cm}\Rightarrow\hspace{0.3cm}H_2 = 1/2 \cdot (H+H_1) =  

Aktuelle Version vom 19. Juni 2021, 13:52 Uhr

Verschiedene Binärfolgen

Die Grafik rechts oben zeigt vier Symbolfolgen  $\langle q_\nu \rangle $  mit jeweiliger Länge  $N = 60$.  Die Quellensymbole sind jeweils  $\rm A$  und  $\rm B$.

  • Daraus folgt direkt, dass für den Entscheidungsgehalt aller betrachteten Quellen  $H_0 = 1 \; \rm bit/Symbol$  gilt.
  • Die Symbole  $\rm A$  und  $\rm B$  treten jedoch nicht gleichwahrscheinlich auf, sondern mit den Wahrscheinlichkeiten  $p_{\rm A}$  und  $p_{\rm B}$.


Die untere Tabelle zeigt neben  $H_0$  noch die Entropienäherungen

  • $H_1$,  basierend auf  $p_{\rm A}$  und  $p_{\rm B}$  (Spalte 2),
  • $H_2$,  basierend auf Zweiertupel (Spalte 3),
  • $H_3$,  basierend auf Dreiertupel (Spalte 4),
  • $H_4$,  basierend auf Vierertupel (Spalte 5),
  • die tatsächliche Entropie  $H$, die sich aus  $H_k$  durch den Grenzübergang für  $k \to \infty$  ergibt (letzte Spalte).


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 die Entropie  $H = 0.5 \; \rm bit/Symbol$.
  • Zudem sind die Näherungen  $H_1 = 1 \; \rm bit/Symbol$  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:

  • 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

1

Von welcher Quelle stammt die schwarze Symbolfolge?

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

2

Von welcher Quelle stammt die blaue Symbolfolge?

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

3

Von welcher Quelle stammt die rote Symbolfolge?

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

4

Berechnen Sie die Entropienäherung  $H_2$  des Wiederholungscodes  $\rm Q4$.

$H_2 \ = \ $

$\ \rm bit/Symbol$

5

Berechnen Sie die Entropienäherung  $H_3$  des Wiederholungscodes  $\rm Q4$.

$H_3 \ = \ $

$\ \rm bit/Symbol$


Musterlösung

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