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

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Komprimierung nach Lempel, Ziv und Welch }} right| :Wi…“)
 
 
(24 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Komprimierung nach Lempel, Ziv und Welch
+
{{quiz-Header|Buchseite=Informationstheorie/Komprimierung nach Lempel, Ziv und Welch
 
}}
 
}}
  
[[Datei:P_ID2446__Inf_A_2_5_neu.png|right|]]
+
[[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 BQ1, BQ2 und BQ3:
+
Wir gehen hier von einer binären Eingangsfolge der Länge&nbsp; $N$&nbsp; aus und  betrachten drei verschiedene binäre Nachrichtenquellen:
 +
* $\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$&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.&nbsp; <br>In der Teilaufgabe&nbsp; '''(6)'''&nbsp; sollen Sie die Entropie&nbsp; $H$&nbsp; dieser Quelle  abschätzen.
  
:* <font color="#cc0000"><span style="font-weight: bold;">BQ1:</span></font> mit den 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 <br>&#8658;&nbsp; Quelle ist redundand.
 
  
:* <font color="#cc0000"><span style="font-weight: bold;">BQ2:</span></font> <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = 0.5 (gleichwahrscheinlich) <br>&#8658;&nbsp; Entropie <i>H</i> = 1 bit/Quellensymbol <br>&#8658;&nbsp; Quelle ist redundanzfrei.
+
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;
  
:* <font color="#cc0000"><span style="font-weight: bold;">BQ3:</span></font> Hier gibt es keine konkreten Angaben zur Statistik. In der Teilaufgabe (f) sollen Sie die Entropie <i>H</i> dieser Quelle  abschätzen.
+
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)  
  
:Für diese drei Quellen wurden per Simulation die jeweilige <i>Restredundanz</i> <i>r</i>(<i>N</i>) ermittelt, die nach der 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),
+
eingetragen, wobei wir uns bei der Simulation auf Folgenlängen&nbsp; $N &#8804; 50000$&nbsp; beschränkt haben.
  
:* BQ2 (grüne Hinterlegung),
+
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$
  
:* BQ3 (blaue Hinterlegung)
 
  
:eingetragen, wobei wir uns bei der Simulation auf Folgenlängen <i>N</i> &#8804; 50000 beschränkt haben.
+
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&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},$$
 +
 
 +
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)}
 +
\hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)}
 +
\hspace{0.05cm}.$$
 +
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.
  
:Die <i>relative Redundanz der Ausgangsfolge</i> &ndash; vereinfachend <i>Restredundanz</i> genannt &ndash;  kann aus
 
  
:* der Länge <i>N</i> der Eingangsfolge,
 
  
:* der Länge <i>L</i>(<i>N</i>) der Ausgangsfolge und
 
  
:* der Quellenentropie <i>H</i>
 
  
: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  <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>
 
:$$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
 
:$$r'(N) ={A}/{{\rm lg}\hspace{0.1cm}(N)}
 
\hspace{0.5cm}{\rm mit}\hspace{0.5cm} A = 4 \cdot {r(N = 10000)}
 
\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.
 
  
:<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 50: 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 92: 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ß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie und Quellencodierung|^2.2 Komprimierung nach Lempel, Ziv und Welch^]]
+
[[Category:Aufgaben zu Informationstheorie|^2.2 Verfahren von Lempel, Ziv, Welch^]]

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.