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

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(17 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2446__Inf_A_2_5_neu.png|right|Restredundanz <i>r</i>(<i>N</i>) und Näherung <i>r</i> ′(<i>N</i>) dreier Quellen]]
+
[[Datei:P_ID2446__Inf_A_2_5_neu.png|right|frame|Restredundanz&nbsp; $r(N)$&nbsp; und <br>Näherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; dreier Binärquellen]]
Wir gehen hier von einer binären Eingangsfolge der Länge <i>N</i> aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
+
Wir gehen hier von einer binären Eingangsfolge der Länge&nbsp; $N$&nbsp; aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
* '''BQ1''': &nbsp; Symbolwahrscheinlichkeiten  <i>p</i><sub>A</sub> = 0.89, <i>p</i><sub>B</sub>&nbsp;=&nbsp;0.11, also unterschiedlich<br> &#8658;&nbsp; Entropie <i>H</i> = 0.5 bit/Quellensymbol &nbsp; &#8658; &nbsp; 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.
* '''BQ2''':  &nbsp; <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = 0.5 (gleichwahrscheinlich) &nbsp; &#8658; &nbsp; Entropie <i>H</i> = 1 bit/Quellensymbol <br>&#8658;&nbsp; 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.
* '''BQ3''': &nbsp;  Hier gibt es keine konkreten Angaben zur Statistik. In der Teilaufgabe (6) sollen Sie die Entropie <i>H</i> 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> <i>r</i>(<i>N</i>) 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
 
'''BQ1''' (gelbe Hinterlegung), '''BQ2''' (grüne Hinterlegung) und '''BQ3''' (blaue Hinterlegung) eingetragen, wobei wir uns bei der Simulation auf Folgenlängen <i>N</i> &#8804; 50000 beschränkt haben.
 
  
Die <i>relative Redundanz der Ausgangsfolge</i> &ndash; vereinfachend <i>Restredundanz</i> genannt &ndash; kann aus
+
Für diese drei Quellen wurden per Simulation die jeweilige Restredundanz&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;
  
:* der Länge <i>N</i> der Eingangsfolge,
+
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)
  
:* der Länge <i>L</i>(<i>N</i>) der Ausgangsfolge und
 
  
:* der Quellenentropie <i>H</i>
+
eingetragen, wobei wir uns bei der Simulation auf Folgenlängen&nbsp; $N &#8804; 50000$&nbsp; beschränkt haben.
  
:in folgender Weise berechnet werden:
+
Die relative Redundanz der Ausgangsfolge &ndash; vereinfachend &bdquo;Restredundanz&rdquo; genannt &ndash;  kann aus
 +
* der Länge&nbsp;  $N$&nbsp;  der Eingangsfolge,
 +
* der Länge&nbsp;  $L(N)$&nbsp;  der Ausgangsfolge und
 +
*der Entropie&nbsp;  $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}.$$
 
:$$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  <i>L</i><sub>min</sub> = <i>N</i> &middot; <i>H</i> herabgesenkt werden könnte. Bei nichtperfekter Quellencodierung  gibt <i>L</i>(<i>N</i>) &ndash; <i>N</i> &middot; <i>H</i> die verbleibende Redundanz (mit der Pseudo&ndash;Einheit &bdquo;bit&rdquo;) an. Nach Division durch <i>L</i>(<i>N</i>) erhält man die relative Redundanz <i>r</i>(<i>N</i>) mit dem Wertebereich zwischen 0 und 1; <i>r</i>(<i>N</i>) sollte möglichst klein sein.
 
  
:Eine zweite Kenngröße zur Effizienzmessung der LZW&ndash;Codierung ist der <i>Komprimierungsfaktor</i>
+
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&nbsp;  $L(n) - N &middot; H$&nbsp;  die verbleibende Redundanz (mit der Pseudo&ndash;Einheit &bdquo;bit&rdquo;) an.
 +
*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&nbsp;  &bdquo;Komprimierungsfaktor&rdquo;&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},$$
:der ebenfalls klein sein sollte. <i>Hinweis</i>: <i>K</i>(<i>N</i>) und <i>r</i>(<i>N</i>) hängen deterministisch zusammen.
 
  
:Im Theorieteil wurde gezeigt, dass die Restredundanz <i>r</i>(<i>N</i>) 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'(N) ={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}.$$
:oft gut angenähert wird. Die Näherung <i>r</i>&prime;(<i>N</i>) ist für BQ1 in der zweiten Spalte obiger Tabelle angegeben. In den Teilaufgaben (d) und (e) sollen Sie die Approximation für die Quellen BQ2 und 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.
 +
 
 +
 
 +
 
 +
 
  
  
''Hinweise:''
 
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
 
*Insbesondere wird  Bezug genommen auf die Seiten [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|LZ77 &ndash; die Grundform der Lempel-Ziv-Algorithmen]], [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Lempel.E2.80.93Ziv.E2.80.93Codierung_mit_variabler_Indexbitl.C3.A4nge|Lempel-Ziv-Codierung mit variabler Indexbitlänge]] sowie [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Decodierung_des_LZW.E2.80.93Algorithmus|Decodierung des LZW-Agorithmus]].
 
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 
*Die [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]] sowie die [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Zusatzaufgabe 2.3Z]] behandeln andere LZ-Verfahren in ähnlicher Weise.
 
  
  
:<b>Hinweis:</b> Die Aufgabe bezieht sich auf Seite 7 und Seite 8 von Kapitel 2.2.
+
''Hinweise:''
 +
*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
 +
:: [[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#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Quantitative Aussagen zur asymptotischen Optimalität]].
 +
*Die Beschreibungsgrößen&nbsp;  $K(N)$&nbsp;  und&nbsp;  $r(N)$&nbsp;  hängen deterministisch zusammen.
 +
  
  
Zeile 48: Zeile 66:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Mit welchem Parameter <i>A</i> wurde die Näherung <i>r'</i>(<i>N</i>) der Restredundanz für die Binärquelle 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="{}"}
$BQ1:\ A$ = { 1.06 3% }
+
$A \ = \ $ { 1.06 3% }
  
  
{Wie groß muss <i>N</i> = <i>N</i><sub>b</sub> mindestens sein, damit die Restredundanz die Bedingung <i>r</i>(<i>N</i>) &#8804; 5% erfüllt? <i>Hinweis:</i> Ersetzen Sie <i>r</i>(<i>N</i>) durch <i>r'</i><sub> </sub>(<i>N</i>).
+
{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="{}"}
$BQ1:\ N_b$ = { 1.58 3% } $\cdot 10^{21}$
+
$N_{2} \ =  \ $ { 1.58 3% } $\ \cdot 10^{21}$
  
  
{Wie groß muss <i>N</i> = <i>N</i><sub>c</sub> mindestens sein, damit der Komprimierungsfaktor &nbsp;&#8658;&nbsp;&nbsp; <i>K</i>(<i>N</i>) = <i>L</i>(<i>N</i>)/<i>N</i> 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="{}"}
$BQ1:\ N_c$ = { 2.29 3% } $\cdot 10^{6}$
+
$N_{3} \ =  \ $ { 2.29 3% } $\ \cdot 10^{6}$
  
  
{Bestimmen Sie nun die Redundanznäherung <i>r'</i>(<i>N</i>) für die redundanzfreie Binärquelle 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="{}"}
$BQ2:\ r'(N = 50000)$ = { 0.162 3% }
+
$r'(N = 50000)\ =  \ $ { 0.162 3% }
$r'(N = 10^6)$ = { 0.127 3% }
+
$r'(N = 10^6)\ =  \ $ { 0.127 3% }
$r'(N = 10^12)$ = { 0.063 3% }
+
$r'(N = 10^{12})\ =  \ $ { 0.063 3% }
  
  
{Welche Werte liefert die Redundanznäherung <i>r</i>&prime;(<i>N</i>) für die nicht näher spezifizierte Binärquelle BQ3? Insbesondere:
+
{Welche Werte liefert die Redundanznäherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; für die nicht näher spezifizierte Binärquelle&nbsp; $\rm BQ3$? Insbesondere:
 
|type="{}"}
 
|type="{}"}
$BQ2:\ r'(N = 50000)$ = { 0.289 3% }
+
$r'(N = 50000)\ =  \ $ { 0.289 3% }
$r'(N = 10^6)$ = { 0.227 3% }
+
$r'(N = 10^6)\ =  \ $ { 0.227 3% }
$r'(N = 10^12)$ = { 0.113 3% }
+
$r'(N = 10^{12})\ =  \ $ { 0.113 3% }
  
  
{Welche Quellenentropie <i>H</i> könnte BQ3 nach diesem Ergebnis besitzen? <i>Hinweis:</i> Es ist genau eine Antwort richtig.
+
{Welche Quellenentropie&nbsp; $H$&nbsp; könnte&nbsp; $\rm BQ3$&nbsp; nach diesem Ergebnis besitzen?&nbsp; Hinweis:&nbsp; Es ist genau eine Antwort richtig.
|type="[]"}
+
|type="()"}
- <i>H</i> = 1.00 bit/Quellensymbol,
+
- $H = 1.00 \ \rm bit/Quellensymbol$,
- <i>H</i> = 0.75 bit/Quellensymbol,
+
- $H = 0.75 \ \rm bit/Quellensymbol$,
- <i>H</i> = 0.50 bit/Quellensymbol,
+
- $H = 0.50 \ \rm bit/Quellensymbol$,
+ <i>H</i> = 0.25 bit/Quellensymbol.
+
+ $H = 0.25 \ \rm bit/Quellensymbol$.
  
  
Zeile 90: Zeile 108:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Die Näherung <i>r'</i><sup> </sup>(<i>N</i>) stimmt definitionsgemäß für die Eingangsfolgenlänge <i>N</i> = 10000 mit der per Simulation ermittelten Restredundanz <i>r</i>(<i>N</i>) = 0.265 exakt überein. Damit ist
+
'''(1)'''&nbsp; Die Näherung&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; stimmt per Definition für die Folgenlänge&nbsp; $N = 10000$&nbsp; mit der per Simulation ermittelten Restredundanz&nbsp; $r(N) = 0.265$&nbsp; exakt überein.  
 +
*Damit ist
 
:$$A = 4 \cdot  r(N = 10000) =4 \cdot {0.265} \hspace{0.15cm}\underline{= 1.06}
 
:$$A = 4 \cdot  r(N = 10000) =4 \cdot {0.265} \hspace{0.15cm}\underline{= 1.06}
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
:<b>2.</b>&nbsp;&nbsp;Aus der Beziehung <i>A</i>/lg (<i>N</i>) &#8804; 0.05 &nbsp;&nbsp;&nbsp;&#8658;&nbsp;&nbsp;&nbsp; <i>A</i>/lg (<i>N</i><sub>b</sub>) = 0.05 folgt:
+
 
:$${{\rm lg}\hspace{0.1cm}N_{\rm b}} = \frac{A}{0.05} = 21.2 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
+
 
N_{\rm b} = 10^{21.2} \hspace{0.15cm}\underline{= 1.58 \cdot 10^{21}}
+
'''(2)'''&nbsp; Aus der Beziehung&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N) &#8804; 0.05$ &nbsp;&nbsp;&nbsp;&#8658;&nbsp;&nbsp;&nbsp; ${A}/{\rm lg}\hspace{0.1cm}(N_2) = 0.05$&nbsp; 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}.$$
 
\hspace{0.05cm}.$$
  
:<b>3.</b>&nbsp;&nbsp;Allgemein gilt:
+
 
:$$r(N) = 1 - \frac{H}{K(N)}  
+
 
\hspace{0.05cm}. $$
+
'''(3)'''&nbsp; Allgemein gilt &nbsp;$r(N) = 1 - {H}/{K(N)} \hspace{0.05cm}.$&nbsp;
:BQ1 hat die Entropie <i>H</i> = 0.5 bit/Symbol. Daraus folgt wegen <i>r</i>(<i>N</i>) &asymp; <i>r'</i><sup> </sup>(<i>N</i>) für <i>K</i>(<i>N</i><sub>c</sub>) = 0.6:
+
*$\rm BQ1$&nbsp; hat die Entropie&nbsp; $H = 0.5$ bit/Symbol.&nbsp;
:$$r(N_{\rm c}) = 1 - \frac{0.5}{0.6} = 0.167 \hspace{0.1cm}\Rightarrow\hspace{0.1cm}  
+
*Daraus folgt wegen &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N)$&nbsp; für&nbsp; $K(N_3) = 0.6$:
{\rm lg}\hspace{0.1cm}N_{\rm c} = \frac{A}{0.167} = 6.36
+
:$$r(N_{\rm 3}) = 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}
 
\hspace{0.1cm}\Rightarrow\hspace{0.1cm}
N_{\rm c} = 10^{6.36} \hspace{0.15cm}\underline{= 2.29 \cdot 10^{6}}
+
N_{\rm 3} = 10^{6.36} \hspace{0.15cm}\underline{= 2.29 \cdot 10^{6}}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
[[Datei:P_ID2447__Inf_A_2_5d.png|right|]]
 
  
:<b>4.</b>&nbsp;&nbsp;Für <i>N</i> = 10000 gilt <i>r</i>&prime;(<i>N</i>) = <i>r</i>(<i>N</i>) = 0.190:
+
 
 +
 
 +
[[Datei:P_ID2447__Inf_A_2_5d.png|right|frame|Ergebnisse für&nbsp; $\rm BQ2$]]
 +
'''(4)'''&nbsp; Für&nbsp; $N = 10000$&nbsp; gilt &nbsp;$r(N) &asymp; r\hspace{0.05cm}'(N) = 0.19$:
 
:$$\frac{A}{{\rm lg}\hspace{0.1cm}10000} = 0.19 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 
:$$\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}. $$
 
A = 0.19 \cdot 4 = 0.76 \hspace{0.05cm}. $$
:Die Ergebnisse sind in nebenstehender Tabelle zusammengefasst. Man erkennt die sehr gute Übereinstimmung zwischen <i>r</i>(<i>N</i>) und <i>r</i>&prime;(<i>N</i>). Die gesuchten Zahlenwerte sind in der Tabelle rot markiert.
+
*Die Ergebnisse sind in nebenstehender Tabelle zusammengefasst.  
 +
*Man erkennt die sehr gute Übereinstimmung zwischen&nbsp; &nbsp;$r(N)$&nbsp; und &nbsp;$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 &nbsp;$r\hspace{0.05cm}'(N)$&nbsp; 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&ndash;Ausgabestrings:
 +
:$$L\hspace{0.05cm}'(N) = K\hspace{0.05cm}'(N) \cdot N  = \frac{N}{1 - r\hspace{0.05cm}'(N)}\hspace{0.05cm}.$$
 +
 
 +
 
  
:Für den Komprimierungsfaktor gilt (der Apostroph weist darauf hin, dass von der Näherung <i>r</i>&prime;(<i>N</i>) ausgegangen wurde):
+
[[Datei:Inf_A_2_5e_v2.png|right|frame|Ergebnisse für&nbsp; $\rm BQ3$]]
:$$K'(N) = \frac{1}{1 - r'(N)}\hspace{0.05cm}.$$
+
'''(5)'''&nbsp; Nach ähnlicher Vorgehensweise wie in der Teilaufgabe&nbsp; '''(4)'''&nbsp; erhält man für die Binärquelle&nbsp; $\rm BQ3$&nbsp; den Anpassungsparameter&nbsp; $A = 1.36$&nbsp; und daraus die Ergebnisse gemäß der blau hinterlegten Tabelle.
:Damit gilt für die Länge des LZW&ndash;Ausgabestrings:
 
:$$L'(N) = K'(N) \cdot N \hspace{0.05cm}.$$
 
  
:<br><br><br>
+
<u>Hinweis:</u> &nbsp; Die letzte Spalte dieser Tabelle ist nur bei Kenntnis der Teilaufgabe&nbsp; '''(6)'''&nbsp; verständlich. Dort wird gezeigt, dass die Quelle&nbsp; $\rm BQ3$&nbsp; die Entropie&nbsp; $H = 0.25$ bit/Quellensymbol besitzt.
:<b>5.</b>&nbsp;&nbsp;Nach ähnlicher Vorgehensweise wie in der Teilaufgabe d) erhält man für die Binärquelle BQ3 den Anpassungsparameter <i>A</i> = 1.36 und daraus die Ergebnisse gemäß der blau hinterlegten Tabelle.
 
  
:<u>Hinweis:</u> Die letzte Spalte dieser Tabelle ist nur bei Kenntnis der Teilaufgabe (f) verständlich. Dort wird gezeigt, dass die  Quelle BQ3 die Entropie   <i>H</i> = 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&nbsp; $N = 10^{12}$&nbsp; weicht also der Komprimierungsfaktor&nbsp; $(0.282)$&nbsp; noch deutlich von der Entropie&nbsp; $(0.25)$&nbsp; ab, die erst  für&nbsp; $N \to \infty$&nbsp; erreicht werden kann (Quellencodierungstheorem).
  
:In diesem Fall gilt für den Komprimierungsfaktor:
 
:$$K'(N) = \frac{H}{1 - r'(N)} = \frac{0.25}{1 - r'(N)} \hspace{0.05cm}.$$
 
[[Datei:P_ID2448__Inf_A_2_5e.png|right|]]
 
:Für <i>N</i> = 10<sup>12</sup> weicht also der Komprimierungsfaktor (0.282) noch deutlich von der Entropie (0.25) ab, die  für <i>N</i> &#8594;  &#8734; erreicht werden kann (Quellencodierungstheorem).<br><br><br>
 
  
:<b>6.</b>&nbsp;&nbsp;Die einzelnen Näherungen <i>r</i>&prime;(<i>N</i>) unterscheiden sich nur durch den Parameter <i>A</i>. Dabei haben wir festgestellt:
 
  
:* Quelle BQ2 (<i>H</i> = 1.00): <i>A</i> = 0.76,
 
  
:* Quelle BQ1 (<i>H</i> = 0.50): <i>A</i> = 1.06,
+
'''(6)'''&nbsp; Die einzelnen Näherungen&nbsp; $r\hspace{0.05cm}'(N)$&nbsp; unterscheiden sich nur durch den Parameter&nbsp; $A$.&nbsp; Dabei haben wir festgestellt:
 +
# Quelle&nbsp; $\rm BQ1$&nbsp; mit&nbsp; $H = 0.50$ &nbsp; &rArr; &nbsp; $A = 1.06$ &nbsp; &rArr; &nbsp; entsprechend dem Angabenblatt,
 +
# Quelle&nbsp; $\rm BQ2$&nbsp; mit&nbsp; $H = 1.00$ &nbsp; &rArr; &nbsp; $A = 0.76$ &nbsp; &rArr; &nbsp; siehe Teilaufgabe&nbsp; '''(4)''',
 +
# Quelle&nbsp; $\rm BQ3$&nbsp; $(H$ unbekannt$)$: $A = 4 &middot; 0.34 =1.36$ &nbsp; &rArr; &nbsp; entsprechend der hier angegebenen Tabelle.
  
:* Quelle BQ3 (<i>H</i> unbekannt): <i>A</i> = 1.36.
 
  
:Je kleiner die Entropie <i>H</i> ist, um so größer ist offensichtlich der Anpassungsfaktor <i>A</i>. Da genau eine Lösung möglich ist, muss <i>H</i> = 0.25 bit/Quellensymbol richtig sein &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Antwort 4</u>.
+
*Je kleiner die Entropie&nbsp; $H$&nbsp; ist, um so größer ist offensichtlich der Anpassungsfaktor&nbsp; $A$&nbsp; (und umgekehrt).  
 +
*Da genau eine Lösung möglich ist, muss&nbsp; $H = 0.25$&nbsp; bit/Quellensymbol richtig sein &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Antwort 4</u>.
  
:Tatsächlich wurden bei der Simulation für die Quelle Q3 die Wahrscheinlichkeiten <i>p</i><sub>A</sub> = 0.96, <i>p</i><sub>B</sub> = 0.04 &#8658; <i>H</i> &asymp; 0.25 verwendet.<br><br>
+
*Tatsächlich wurden bei der Simulation für die Quelle&nbsp; $\rm BQ3$&nbsp; die Wahrscheinlichkeiten &nbsp;$p_{\rm A} = 0.96$&nbsp; und &nbsp;$p_{\rm B} = 0.04$&nbsp; &nbsp; &#8658; &nbsp; $H &asymp; 0.25$ verwendet.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 10. August 2021, 10:22 Uhr

Restredundanz  $r(N)$  und
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 per Definition für die Folgenlä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_2) = 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 3}) = 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 erst 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:

  1. Quelle  $\rm BQ1$  mit  $H = 0.50$   ⇒   $A = 1.06$   ⇒   entsprechend dem Angabenblatt,
  2. Quelle  $\rm BQ2$  mit  $H = 1.00$   ⇒   $A = 0.76$   ⇒   siehe Teilaufgabe  (4),
  3. Quelle  $\rm BQ3$  $(H$ unbekannt$)$: $A = 4 · 0.34 =1.36$   ⇒   entsprechend der hier angegebenen 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.