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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 8: Zeile 8:
 
* '''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.
 
* '''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.
 
* '''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.
 
* '''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.
 +
  
 
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
 
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.
+
*'''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  
 
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>
  
:* der Länge <i>N</i> der Eingangsfolge,
+
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}.$$
:* der Länge <i>L</i>(<i>N</i>) der Ausgangsfolge und
 
 
 
:* der Quellenentropie <i>H</i>
 
  
:in folgender Weise berechnet werden:
+
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&nbsp;</i> herabgesenkt werden könnte. Bei nichtperfekter Quellencodierung  gibt <i>L</i>(<i>N</i>) &ndash; <i>N</i> &middot; <i>H&nbsp;</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&nbsp;</i>(<i>N</i>) mit dem Wertebereich zwischen 0 und 1; <i>r&nbsp;</i>(<i>N</i>) sollte möglichst klein sein.
:$$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>
+
Eine zweite Kenngröße zur Effizienzmessung der LZW&ndash;Codierung ist der <i>Komprimierungsfaktor</i> <i>K</i>(<i>N</i>), der 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 [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Theorieteil]] wurde gezeigt, dass die Restredundanz <i>r</i>(<i>N</i>) oft durch die Funktion
 
:$$r'(N) ={A}/{{\rm lg}\hspace{0.1cm}(N)}
 
:$$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.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. Die Näherung <i>r</i>&prime;(<i>N</i>) ist für '''BQ1''' in der zweiten Spalte obiger Tabelle angegeben. In den Teilaufgaben (4) und (5) sollen Sie die Approximation für die Quellen '''BQ2''' und '''BQ3''' vornehmen.
  
  
 
''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]].
*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]].
+
*Insbesondere wird  Bezug genommen auf die Seiten [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Restredrundanz_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 [[IInformationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Quantitative Aussagen zur asymptotischen Optimalität]].
 +
*Die Beschreibungsgrößen <i>K</i>(<i>N</i>) und <i>r</i>(<i>N</i>) hängen deterministisch zusammen.
 
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 
*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.
 
  
  

Version vom 22. Mai 2017, 11:40 Uhr

Restredundanz r(N) und Näherung r ′(N) dreier Quellen

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

  • BQ1:   Symbolwahrscheinlichkeiten pA = 0.89, pB = 0.11, also unterschiedlich
    ⇒  Entropie H = 0.5 bit/Quellensymbol   ⇒   Quelle ist redundant.
  • BQ2:   pA = pB = 0.5 (gleichwahrscheinlich)   ⇒   Entropie H = 1 bit/Quellensymbol
    ⇒  Quelle ist redundanzfrei.
  • 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

  • BQ1 (gelbe Hinterlegung),
  • BQ2 (grüne Hinterlegung) und
  • 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 Quellenentropie 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 Lmin = N · herabgesenkt werden könnte. Bei nichtperfekter Quellencodierung gibt L(N) – N · die verbleibende Redundanz (mit der Pseudo–Einheit „bit”) an. Nach Division durch L(N) erhält man die relative Redundanz (N) mit dem Wertebereich zwischen 0 und 1; (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'(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}.$$

gut angenähert wird. Die Näherung r′(N) ist für BQ1 in der zweiten Spalte obiger Tabelle angegeben. In den Teilaufgaben (4) und (5) sollen Sie die Approximation für die Quellen BQ2 und BQ3 vornehmen.


Hinweise:


Fragebogen

1

Mit welchem Parameter A wurde die Näherung r'(N) der Restredundanz für die Binärquelle BQ1 erstellt?

$BQ1:\ A$ =

2

Wie groß muss N = Nb mindestens sein, damit die Restredundanz die Bedingung r(N) ≤ 5% erfüllt? Hinweis: Ersetzen Sie r(N) durch r' (N).

$BQ1:\ N_b$ =

$\cdot 10^{21}$

3

Wie groß muss N = Nc mindestens sein, damit der Komprimierungsfaktor  ⇒   K(N) = L(N)/N nicht größer ist als 0.6?

$BQ1:\ N_c$ =

$\cdot 10^{6}$

4

Bestimmen Sie nun die Redundanznäherung r'(N) für die redundanzfreie Binärquelle BQ2, insbesondere:

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

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

$r'(N = 10^12)$ =

5

Welche Werte liefert die Redundanznäherung r′(N) für die nicht näher spezifizierte Binärquelle BQ3? Insbesondere:

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

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

$r'(N = 10^12)$ =

6

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

H = 1.00 bit/Quellensymbol,
H = 0.75 bit/Quellensymbol,
H = 0.50 bit/Quellensymbol,
H = 0.25 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 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/lg (N) ≤ 0.05    ⇒    A/lg (Nb) = 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}} \hspace{0.05cm}.$$
3.  Allgemein gilt:
$$r(N) = 1 - \frac{H}{K(N)} \hspace{0.05cm}. $$
BQ1 hat die Entropie H = 0.5 bit/Symbol. Daraus folgt wegen r(N) ≈ r' (N) für K(Nc) = 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 c} = \frac{A}{0.167} = 6.36 \hspace{0.1cm}\Rightarrow\hspace{0.1cm} N_{\rm c} = 10^{6.36} \hspace{0.15cm}\underline{= 2.29 \cdot 10^{6}} \hspace{0.05cm}.$$
P ID2447 Inf A 2 5d.png
4.  Für N = 10000 gilt r′(N) = r(N) = 0.190:
$$\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′(N). Die gesuchten Zahlenwerte sind in der Tabelle rot markiert.
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 \hspace{0.05cm}.$$



5.  Nach ähnlicher Vorgehensweise wie in der Teilaufgabe d) 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 (f) 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}.$$
P ID2448 Inf A 2 5e.png
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 BQ2 (H = 1.00): A = 0.76,
  • Quelle BQ1 (H = 0.50): A = 1.06,
  • Quelle BQ3 (H unbekannt): A = 1.36.
Je kleiner die Entropie H ist, um so größer ist offensichtlich der Anpassungsfaktor A. 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 Q3 die Wahrscheinlichkeiten pA = 0.96, pB = 0.04 ⇒ H ≈ 0.25 verwendet.