Aufgaben:Aufgabe 2.5: Restredundanz bei LZW-Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2446__Inf_A_2_5_neu.png|right|frame|Restredundanz $r(N)$ und Näherung $r\hspace{0.05cm}'(N)$ dreier Quellen]]
+
[[Datei:P_ID2446__Inf_A_2_5_neu.png|right|frame|Restredundanz  $r(N)$  & Näherung  $r\hspace{0.05cm}'(N)$  dreier Binärquellen]]
Wir gehen hier von einer binären Eingangsfolge der Länge $N$ aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
+
Wir gehen hier von einer binären Eingangsfolge der Länge  $N$  aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
* $\rm BQ1$: &nbsp; Symbolwahrscheinlichkeiten  $p_{\rm A} = 0.89$ und $p_{\rm B} = 0.11$, also unterschiedlich<br> &#8658;&nbsp; Entropie $H = 0.5\text{ bit/Quellensymbol}$ &nbsp; &#8658; &nbsp; die Quelle ist redundant.
+
* $\rm BQ1$: &nbsp; Symbolwahrscheinlichkeiten&nbsp;   $p_{\rm A} = 0.89$&nbsp; und&nbsp; $p_{\rm B} = 0.11$, also unterschiedlich<br> &nbsp;  &#8658; &nbsp; Entropie&nbsp; $H = 0.5\text{ bit/Quellensymbol}$ &nbsp; &#8658; &nbsp; die Quelle ist redundant.
* $\rm BQ2$:  &nbsp; $p_{\rm A} = p_{\rm B} = 0.5$ (gleichwahrscheinlich) &nbsp; &#8658; &nbsp; Entropie $H = 1\text{ bit/Quellensymbol}$ <br>&#8658;&nbsp; die Quelle ist redundanzfrei.
+
* $\rm BQ2$:  &nbsp; $p_{\rm A} = p_{\rm B} = 0.5$&nbsp; (gleichwahrscheinlich)<br> &nbsp; &#8658; &nbsp; Entropie&nbsp; $H = 1\text{ bit/Quellensymbol}$ &nbsp; &#8658; &nbsp; die Quelle ist redundanzfrei.
* $\rm BQ3$: &nbsp;  Hier gibt es keine konkreten Angaben zur Statistik. In der Teilaufgabe '''(6)''' sollen Sie die Entropie $H$ dieser Quelle  abschätzen.
+
* $\rm BQ3$: &nbsp;  Hier gibt es keine konkreten Angaben zur Statistik.&nbsp; <br>In der Teilaufgabe&nbsp; '''(6)'''&nbsp; sollen Sie die Entropie&nbsp; $H$&nbsp; dieser Quelle  abschätzen.
  
  
Für diese drei Quellen wurden per Simulation die jeweilige <i>Restredundanz</i> $r(N)$ ermittelt, die nach der [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|Lempel&ndash;Ziv&ndash;Welch&ndash;Codierung]] in der Binärfolge verbleibt. Die Ergebnisse sind in der jeweils ersten Spalte obiger Tabelle für die Quellen
+
Für diese drei Quellen wurden per Simulation die jeweilige <i>Restredundanz</i>&nbsp; $r(N)$&nbsp; ermittelt, die nach der&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|Lempel&ndash;Ziv&ndash;Welch&ndash;Codierung]]&nbsp; in der Binärfolge verbleibt.&nbsp;
*$\rm BQ1$ (gelbe Hinterlegung),
 
*$\rm BQ2$ (grüne Hinterlegung) und
 
*$\rm BQ3$ (blaue Hinterlegung)
 
  
 +
Die Ergebnisse sind in der jeweils ersten Spalte obiger Tabelle für die Quellen
 +
*$\rm BQ1$&nbsp; (gelbe Hinterlegung),
 +
*$\rm BQ2$&nbsp; (grüne Hinterlegung) und
 +
*$\rm BQ3$&nbsp; (blaue Hinterlegung)
  
eingetragen, wobei wir uns bei der Simulation auf Folgenlängen $N &#8804; 50000$ beschränkt haben.
+
 
 +
eingetragen, wobei wir uns bei der Simulation auf Folgenlängen&nbsp; $N &#8804; 50000$&nbsp; beschränkt haben.
  
 
Die <i>relative Redundanz der Ausgangsfolge</i> &ndash; vereinfachend <i>Restredundanz</i> genannt &ndash;  kann aus  
 
Die <i>relative Redundanz der Ausgangsfolge</i> &ndash; vereinfachend <i>Restredundanz</i> genannt &ndash;  kann aus  
* der Länge $N$ der Eingangsfolge,
+
* der Länge&nbsp;  $N$&nbsp;  der Eingangsfolge,
* der Länge $L(N)$ der Ausgangsfolge und
+
* der Länge&nbsp;  $L(N)$&nbsp;  der Ausgangsfolge und
*der Entropie $H$
+
*der Entropie&nbsp;  $H$
  
  
Zeile 27: Zeile 29:
 
:$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 -  \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$
 
:$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 -  \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$
  
Hierbei ist berücksichtigt, dass bei perfekter Quellencodierung die Länge der Ausgangsfolge bis auf den Wert $L_{\rm min} = N &middot; H$ herabgesenkt werden könnte.  
+
Hierbei ist berücksichtigt, dass bei perfekter Quellencodierung die Länge der Ausgangsfolge bis auf den Wert&nbsp;  $L_{\rm min} = N &middot; H$&nbsp;  herabgesenkt werden könnte.  
*Bei nichtperfekter Quellencodierung  gibt $L(n) - N &middot; H$ die verbleibende Redundanz (mit der Pseudo&ndash;Einheit &bdquo;bit&rdquo;) an.  
+
*Bei nichtperfekter Quellencodierung  gibt&nbsp;  $L(n) - N &middot; H$&nbsp;  die verbleibende Redundanz (mit der Pseudo&ndash;Einheit &bdquo;bit&rdquo;) an.  
*Nach Division durch $L(n)$ erhält man die relative Redundanz $r(n)$ mit dem Wertebereich zwischen $0$ und $1$; $r(n)$ sollte möglichst klein sein.
+
*Nach Division durch&nbsp;  $L(n)$&nbsp;  erhält man die relative Redundanz&nbsp;  $r(n)$&nbsp;  mit dem Wertebereich zwischen Null und Eins; $r(n)$ sollte möglichst klein sein.
  
  
Eine zweite Kenngröße zur Effizienzmessung der LZW&ndash;Codierung ist der <i>Komprimierungsfaktor</i> $K(N)$, der ebenfalls klein sein sollte:
+
Eine zweite Kenngröße zur Effizienzmessung der LZW&ndash;Codierung ist der&nbsp;  <i>Komprimierungsfaktor</i>&nbsp;  $K(N)$, der als der Quotient der Längen von Ausgangs&ndash; und Eingangsfolge ebenfalls klein sein sollte:
 
:$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$
 
:$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$
  
Im [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Theorieteil]] wurde gezeigt, dass die Restredundanz $r(n)$ oft durch die Funktion
+
Im&nbsp;  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Theorieteil]]&nbsp;  wurde gezeigt, dass die Restredundanz&nbsp;  $r(n)$&nbsp;  oft durch die Funktion
 
:$$r\hspace{0.05cm}'(N) =\frac {A}{{\rm lg}\hspace{0.1cm}(N)}
 
:$$r\hspace{0.05cm}'(N) =\frac {A}{{\rm lg}\hspace{0.1cm}(N)}
 
\hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)}  
 
\hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)}  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
gut angenähert wird. Die Näherung $r\hspace{0.05cm}'(N)$ ist für $\rm BQ1$ in der zweiten Spalte obiger Tabelle angegeben. In den Teilaufgaben '''(4)''' und '''(5)''' sollen Sie die Approximation für die Quellen $\rm BQ2$ und $\rm BQ3$ vornehmen.
+
gut angenähert wird.  
 +
 
 +
*Diese Näherung&nbsp;  $r\hspace{0.05cm}'(N)$&nbsp;  ist für&nbsp;  $\rm BQ1$&nbsp;  in der zweiten Spalte obiger Tabelle angegeben.
 +
* In den Teilaufgaben&nbsp;  '''(4)'''&nbsp;  und&nbsp;  '''(5)'''&nbsp;  sollen Sie die Approximation für die Quellen&nbsp;  $\rm BQ2$&nbsp;  und&nbsp;  $\rm BQ3$&nbsp;  vornehmen.
 +
 
 +
 
 +
 
  
  
Zeile 46: Zeile 54:
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp;  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
 
*Insbesondere wird  Bezug genommen auf die Seiten
 
*Insbesondere wird  Bezug genommen auf die Seiten
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Restredundanz_als_Ma.C3.9F_f.C3.BCr_die_Effizienz_von_Codierverfahren|Restredrundanz als Maß für die Effizienz von Codierverfahren]],
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Restredundanz_als_Ma.C3.9F_f.C3.BCr_die_Effizienz_von_Codierverfahren|Restredrundanz als Maß für die Effizienz von Codierverfahren]],
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Effizienz_der_Lempel.E2.80.93Ziv.E2.80.93Codierung|Effizienz der Lempel-Ziv-Codierung]] sowie
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Effizienz_der_Lempel.E2.80.93Ziv.E2.80.93Codierung|Effizienz der Lempel-Ziv-Codierung]] sowie
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Quantitative Aussagen zur asymptotischen Optimalität]].   
 
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Quantitative Aussagen zur asymptotischen Optimalität]].   
*Die Beschreibungsgrößen $K(N)$ und $r(N)$ hängen deterministisch zusammen.
+
*Die Beschreibungsgrößen&nbsp;  $K(N)$&nbsp;  und&nbsp;  $r(N)$&nbsp;  hängen deterministisch zusammen.
 
   
 
   
  
Zeile 58: Zeile 66:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Mit welchem Parameter $A$ wurde die Näherung $r\hspace{0.05cm}'(N)$ der Restredundanz für die Binärquelle $\rm BQ1$ erstellt?
+
{Mit welchem Parameter&nbsp; $A$&nbsp; wurde die Näherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; der Restredundanz für die Binärquelle&nbsp; $\rm BQ1$&nbsp; erstellt?
 
|type="{}"}
 
|type="{}"}
 
$A \ = \ $  { 1.06 3% }
 
$A \ = \ $  { 1.06 3% }
  
  
{Wie groß muss $N = N_2$ bei  $\rm BQ1$ mindestens sein, damit die Restredundanz die Bedingung $r(N) &asymp; r\hspace{0.05cm}'(N) \le 5\%$  erfüllt?  
+
{Wie groß muss&nbsp; $N = N_2$&nbsp; bei&nbsp; $\rm BQ1$&nbsp; mindestens sein, damit die Restredundanz die Bedingung&nbsp; $r(N) &asymp; r\hspace{0.05cm}'(N) \le 5\%$&nbsp;   erfüllt?  
 
|type="{}"}
 
|type="{}"}
 
$N_{2} \ =  \ $ { 1.58 3% } $\ \cdot 10^{21}$
 
$N_{2} \ =  \ $ { 1.58 3% } $\ \cdot 10^{21}$
  
  
{Wie groß muss $N = N_3$  bei  $\rm BQ1$ mindestens sein, damit der Komprimierungsfaktor $K(N)= L(N)/N$ nicht größer ist als $0.6$?
+
{Wie groß muss&nbsp; $N = N_3$&nbsp; bei&nbsp; $\rm BQ1$&nbsp; mindestens sein, damit der Komprimierungsfaktor&nbsp; $K(N)= L(N)/N$&nbsp; nicht größer ist als&nbsp; $0.6$?
 
|type="{}"}
 
|type="{}"}
 
$N_{3} \ =  \ $ { 2.29 3% } $\ \cdot 10^{6}$
 
$N_{3} \ =  \ $ { 2.29 3% } $\ \cdot 10^{6}$
  
  
{Bestimmen Sie nun die Redundanznäherung $r\hspace{0.05cm}'(N)$ für die redundanzfreie Binärquelle $\rm BQ2$, insbesondere:
+
{Bestimmen Sie nun die Redundanznäherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; für die redundanzfreie Binärquelle $\rm BQ2$, insbesondere:
 
|type="{}"}
 
|type="{}"}
 
$r'(N = 50000)\ =  \ $ { 0.162 3% }
 
$r'(N = 50000)\ =  \ $ { 0.162 3% }

Version vom 24. Januar 2020, 12:22 Uhr

Restredundanz  $r(N)$  & Näherung  $r\hspace{0.05cm}'(N)$  dreier Binärquellen

Wir gehen hier von einer binären Eingangsfolge der Länge  $N$  aus und betrachten drei verschiedene binäre Nachrichtenquellen:

  • $\rm BQ1$:   Symbolwahrscheinlichkeiten  $p_{\rm A} = 0.89$  und  $p_{\rm B} = 0.11$, also unterschiedlich
      ⇒   Entropie  $H = 0.5\text{ bit/Quellensymbol}$   ⇒   die Quelle ist redundant.
  • $\rm BQ2$:   $p_{\rm A} = p_{\rm B} = 0.5$  (gleichwahrscheinlich)
      ⇒   Entropie  $H = 1\text{ bit/Quellensymbol}$   ⇒   die Quelle ist redundanzfrei.
  • $\rm BQ3$:   Hier gibt es keine konkreten Angaben zur Statistik. 
    In der Teilaufgabe  (6)  sollen Sie die Entropie  $H$  dieser Quelle abschätzen.


Für diese drei Quellen wurden per Simulation die jeweilige Restredundanz  $r(N)$  ermittelt, die nach der  Lempel–Ziv–Welch–Codierung  in der Binärfolge verbleibt. 

Die Ergebnisse sind in der jeweils ersten Spalte obiger Tabelle für die Quellen

  • $\rm BQ1$  (gelbe Hinterlegung),
  • $\rm BQ2$  (grüne Hinterlegung) und
  • $\rm BQ3$  (blaue Hinterlegung)


eingetragen, wobei wir uns bei der Simulation auf Folgenlängen  $N ≤ 50000$  beschränkt haben.

Die relative Redundanz der Ausgangsfolge – vereinfachend Restredundanz genannt – kann aus

  • der Länge  $N$  der Eingangsfolge,
  • der Länge  $L(N)$  der Ausgangsfolge und
  • der Entropie  $H$


in folgender Weise berechnet werden:

$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$

Hierbei ist berücksichtigt, dass bei perfekter Quellencodierung die Länge der Ausgangsfolge bis auf den Wert  $L_{\rm min} = N · H$  herabgesenkt werden könnte.

  • Bei nichtperfekter Quellencodierung gibt  $L(n) - N · H$  die verbleibende Redundanz (mit der Pseudo–Einheit „bit”) an.
  • Nach Division durch  $L(n)$  erhält man die relative Redundanz  $r(n)$  mit dem Wertebereich zwischen Null und Eins; $r(n)$ sollte möglichst klein sein.


Eine zweite Kenngröße zur Effizienzmessung der LZW–Codierung ist der  Komprimierungsfaktor  $K(N)$, der als der Quotient der Längen von Ausgangs– und Eingangsfolge ebenfalls klein sein sollte:

$$K(N) = {L(N) }/{N} \hspace{0.05cm},$$

Im  Theorieteil  wurde gezeigt, dass die Restredundanz  $r(n)$  oft durch die Funktion

$$r\hspace{0.05cm}'(N) =\frac {A}{{\rm lg}\hspace{0.1cm}(N)} \hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)} \hspace{0.05cm}.$$

gut angenähert wird.

  • Diese Näherung  $r\hspace{0.05cm}'(N)$  ist für  $\rm BQ1$  in der zweiten Spalte obiger Tabelle angegeben.
  • In den Teilaufgaben  (4)  und  (5)  sollen Sie die Approximation für die Quellen  $\rm BQ2$  und  $\rm BQ3$  vornehmen.





Hinweise:

Restredrundanz als Maß für die Effizienz von Codierverfahren,
Effizienz der Lempel-Ziv-Codierung sowie
Quantitative Aussagen zur asymptotischen Optimalität.
  • Die Beschreibungsgrößen  $K(N)$  und  $r(N)$  hängen deterministisch zusammen.


Fragebogen

1

Mit welchem Parameter  $A$  wurde die Näherung  $r\hspace{0.05cm}'(N)$  der Restredundanz für die Binärquelle  $\rm BQ1$  erstellt?

$A \ = \ $

2

Wie groß muss  $N = N_2$  bei  $\rm BQ1$  mindestens sein, damit die Restredundanz die Bedingung  $r(N) ≈ r\hspace{0.05cm}'(N) \le 5\%$  erfüllt?

$N_{2} \ = \ $

$\ \cdot 10^{21}$

3

Wie groß muss  $N = N_3$  bei  $\rm BQ1$  mindestens sein, damit der Komprimierungsfaktor  $K(N)= L(N)/N$  nicht größer ist als  $0.6$?

$N_{3} \ = \ $

$\ \cdot 10^{6}$

4

Bestimmen Sie nun die Redundanznäherung  $r\hspace{0.05cm}'(N)$  für die redundanzfreie Binärquelle $\rm BQ2$, insbesondere:

$r'(N = 50000)\ = \ $

$r'(N = 10^6)\ = \ $

$r'(N = 10^{12})\ = \ $

5

Welche Werte liefert die Redundanznäherung $r\hspace{0.05cm}'(N)$ für die nicht näher spezifizierte Binärquelle $\rm BQ3$? Insbesondere:

$r'(N = 50000)\ = \ $

$r'(N = 10^6)\ = \ $

$r'(N = 10^{12})\ = \ $

6

Welche Quellenentropie $H$ könnte $\rm BQ3$ nach diesem Ergebnis besitzen? Hinweis: Es ist genau eine Antwort richtig.

$H = 1.00 \ \rm bit/Quellensymbol$,
$H = 0.75 \ \rm bit/Quellensymbol$,
$H = 0.50 \ \rm bit/Quellensymbol$,
$H = 0.25 \ \rm bit/Quellensymbol$.


Musterlösung

(1)  Die Näherung $r\hspace{0.05cm}'(N)$ stimmt definitionsgemäß für die Eingangsfolgenlänge $N = 10000$ mit der per Simulation ermittelten Restredundanz $r(N) = 0.265$ exakt überein. Damit ist

$$A = 4 \cdot r(N = 10000) =4 \cdot {0.265} \hspace{0.15cm}\underline{= 1.06} \hspace{0.05cm}. $$


(2)  Aus der Beziehung ${A}/{\rm lg}\hspace{0.1cm}(N) ≤ 0.05$    ⇒    ${A}/{\rm lg}\hspace{0.1cm}(N) = 0.05$ folgt:

$${{\rm lg}\hspace{0.1cm}N_{\rm 2}} = \frac{A}{0.05} = 21.2 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} N_{\rm 2} = 10^{21.2} \hspace{0.15cm}\underline{= 1.58 \cdot 10^{21}} \hspace{0.05cm}.$$


(3)  Allgemein gilt  $r(N) = 1 - {H}/{K(N)} \hspace{0.05cm}.$ $\rm BQ1$ hat die Entropie $H = 0.5$ bit/Symbol. Daraus folgt wegen  $r(N) ≈ r\hspace{0.05cm}'(N)$ für $K(N_3) = 0.6$:

$$r(N_{\rm c}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm} {\rm lg}\hspace{0.1cm}N_{\rm 3} = \frac{A}{0.167} = 6.36 \hspace{0.1cm}\Rightarrow\hspace{0.1cm} N_{\rm 3} = 10^{6.36} \hspace{0.15cm}\underline{= 2.29 \cdot 10^{6}} \hspace{0.05cm}.$$


Ergebnisse für $\rm BQ2$

(4)  Für $N = 10000$ gilt  $r(N) ≈ r\hspace{0.05cm}'(N) = 0.19$:

$$\frac{A}{{\rm lg}\hspace{0.1cm}10000} = 0.19 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} A = 0.19 \cdot 4 = 0.76 \hspace{0.05cm}. $$

Die Ergebnisse sind in nebenstehender Tabelle zusammengefasst. Man erkennt die sehr gute Übereinstimmung zwischen  $r(N)$ und  $r\hspace{0.05cm}'(N)$. Die gesuchten Zahlenwerte sind in der Tabelle rot markiert: $$r'(N = 50000)\hspace{0.15cm}\underline{ = 0.162},\hspace{0.3cm}r'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.127},\hspace{0.3cm} r'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.063}.$$

Für den Komprimierungsfaktor gilt (der Apostroph weist darauf hin, dass von der Näherung $r\hspace{0.05cm}'(N)$ ausgegangen wurde):

$$K\hspace{0.05cm}'(N) = \frac{1}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$

Damit gilt für die Länge des LZW–Ausgabestrings:

$$L\hspace{0.05cm}'(N) = K\hspace{0.05cm}'(N) \cdot N = \frac{N}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$
Ergebnisse für $\rm BQ3$

(5)  Nach ähnlicher Vorgehensweise wie in der Teilaufgabe (4) erhält man für die Binärquelle $\rm BQ3$ den Anpassungsparameter $A = 1.36$ und daraus die Ergebnisse gemäß der blau hinterlegten Tabelle.

Hinweis:   Die letzte Spalte dieser Tabelle ist nur bei Kenntnis der Teilaufgabe (6) verständlich. Dort wird gezeigt, dass die Quelle $\rm BQ3$ die Entropie $H = 0.25$ bit/Quellensymbol besitzt.

In diesem Fall gilt für den Komprimierungsfaktor:

$$K\hspace{0.05cm}'(N) = \frac{H}{1 - r\hspace{0.05cm}'(N)} = \frac{0.25}{1 - r'(N)} \hspace{0.05cm}.$$

Damit erhält man für die gesuchten Werte der Restredundanz:

$$r\hspace{0.05cm}'(N = 50000)\hspace{0.15cm}\underline{ = 0.289},\hspace{0.3cm}r\hspace{0.05cm}'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.227},\hspace{0.3cm} r\hspace{0.05cm}'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.113}.$$

Für $N = 10^{12}$ weicht also der Komprimierungsfaktor $(0.282)$ noch deutlich von der Entropie $(0.25)$ ab, die für $N \to \infty$ erreicht werden kann (Quellencodierungstheorem).


(6)  Die einzelnen Näherungen $r\hspace{0.05cm}'(N)$ unterscheiden sich nur durch den Parameter $A$. Dabei haben wir festgestellt:

  • Quelle $\rm BQ1$ mit $H = 0.50$   ⇒   $A = 1.06$   ⇒   entsprechend dem Angabenblatt,
  • Quelle $\rm BQ2$ mit $H = 1.00$   ⇒   $A = 0.76$   ⇒   siehe Teilaufgabe (4),
  • Quelle $\rm BQ3$ ($H$ unbekannt): $A = 4 · 0.34 =1.36$   ⇒   entsprechend der letzten Spalte in der Tabelle.


Je kleiner die Entropie $H$ ist, um so größer ist offensichtlich der Anpassungsfaktor $A$ (und umgekehrt).
Da genau eine Lösung möglich ist, muss $H = 0.25$ bit/Quellensymbol richtig sein   ⇒   Antwort 4.

Tatsächlich wurden bei der Simulation für die Quelle $\rm BQ3$ die Wahrscheinlichkeiten  $p_{\rm A} = 0.96$ und  $p_{\rm B} = 0.04$   ⇒   $H ≈ 0.25$ verwendet.