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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 45: Zeile 45:
  
  
''Hinweise:''
 
 
''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 [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
Zeile 59: Zeile 58:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Mit welchem Parameter <i>A</i> wurde die Näherung <i>r'&nbsp;</i>(<i>N</i>) der Restredundanz für die Binärquelle '''BQ1''' erstellt?
+
{Mit welchem Parameter $A$ wurde die Näherung $r\hspace{0.05cm}'(N)$ der Restredundanz für die Binärquelle $\rm BQ1$ erstellt?
 
|type="{}"}
 
|type="{}"}
$A \ = $  { 1.06 3% }
+
$A \ = \ $  { 1.06 3% }
  
  
{Wie groß muss <i>N</i> = <i>N</i><sub>2</sub> bei  '''BQ1''' mindestens sein, damit die Restredundanz die Bedingung <i>r&nbsp;</i>(<i>N</i>) &asymp; <i>r'&nbsp;</i>(<i>N</i>)&#8804; 5% erfüllt?  
+
{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?  
 
|type="{}"}
 
|type="{}"}
$N_{2} \ = $ { 1.58 3% } $\ \cdot 10^{21}$
+
$N_{2} \ = \ $ { 1.58 3% } $\ \cdot 10^{21}$
  
  
{Wie groß muss <i>N</i> = <i>N</i><sub>3</sub> bei  '''BQ1''' mindestens sein, damit der Komprimierungsfaktor <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 $N = N_3$ bei  $\rm BQ1$ mindestens sein, damit der Komprimierungsfaktor $K(N)= L(N)/N$ nicht größer ist als $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 <i>r'&nbsp;</i>(<i>N</i>) für die redundanzfreie Binärquelle '''BQ2''', insbesondere:
+
{Bestimmen Sie nun die Redundanznäherung $r\hspace{0.05cm}'(N)$ für die redundanzfreie Binärquelle $\rm BQ2$, insbesondere:
 
|type="{}"}
 
|type="{}"}
$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'&nbsp;</i>(<i>N</i>) für die nicht näher spezifizierte Binärquelle '''BQ3'''? Insbesondere:
+
{Welche Werte liefert die Redundanznäherung $r\hspace{0.05cm}'(N)$ für die nicht näher spezifizierte Binärquelle $\rm BQ3$? Insbesondere:
 
|type="{}"}
 
|type="{}"}
$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&nbsp;</i> könnte '''BQ3''' nach diesem Ergebnis besitzen? <i>Hinweis:</i> Es ist genau eine Antwort richtig.
+
{Welche Quellenentropie $H$ könnte $\rm BQ3$ nach diesem Ergebnis besitzen? <i>Hinweis:</i> Es ist genau eine Antwort richtig.
 
|type="[]"}
 
|type="[]"}
 
- $H = 1.00 \ \rm bit/Quellensymbol$,
 
- $H = 1.00 \ \rm bit/Quellensymbol$,

Version vom 25. September 2018, 15:59 Uhr

Restredundanz $r(N)$ und Näherung $r\hspace{0.05cm}'(N)$ dreier Quellen

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$, $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 $0$ und $1$; $r(n)$ sollte möglichst klein sein.


Eine zweite Kenngröße zur Effizienzmessung der LZW–Codierung ist der Komprimierungsfaktor $K(N)$, der 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. 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.



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'  (N) stimmt definitionsgemäß für die Eingangsfolgenlänge N = 10000 mit der per Simulation ermittelten Restredundanz (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/lg (N) ≤ 0.05    ⇒    A/lg (N2) = 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}.$ BQ1 hat die Entropie H = 0.5 bit/Symbol. Daraus folgt wegen (N) ≈ r'  (N) für K(N3) = 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 die Quelle BQ2

(4)  Für N = 10000 gilt r' (N) = r(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 (N) und r' (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'(N) ausgegangen wurde):

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

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

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

(5)  Nach ähnlicher Vorgehensweise wie in der Teilaufgabe (4) erhält man für die Binärquelle 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 BQ3 die Entropie H = 0.25 bit/Quellensymbol besitzt.

In diesem Fall gilt für den Komprimierungsfaktor:

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

Damit erhält man für die gesuchten Werte der Restredundanz: $$r'(N = 50000)\hspace{0.15cm}\underline{ = 0.289},\hspace{0.3cm}r'(N = 10^{6})\hspace{0.15cm}\underline{ = 0.227},\hspace{0.3cm} r'(N = 10^{12})\hspace{0.15cm}\underline{ = 0.113}.$$ Für N = 1012 weicht also der Komprimierungsfaktor (0.282) noch deutlich von der Entropie (0.25) ab, die für N → ∞ erreicht werden kann (Quellencodierungstheorem).


(6)  Die einzelnen Näherungen r' (N) unterscheiden sich nur durch den Parameter A. Dabei haben wir festgestellt:

  • Quelle BQ1 mit H = 0.50:   A = 1.0 – entsprechend dem Angabenblatt),
  • Quelle BQ2 mit H = 1.00:   A = 0.76 – siehe Teilaufgabe (4)
  • Quelle BQ3 (H unbekannt): A = 4 · 0.341 =1.364 – 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 BQ3 die Wahrscheinlichkeiten pA = 0.96, pB = 0.04   ⇒   H ≈ 0.25 verwendet.