Aufgaben:Aufgabe 2.5Z: Komprimierungsfaktor vs. Restredundanz: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(9 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2449__Inf_Z_2_5_neu.png|right|LZW–Datenlänge <i>L</i>(<i>N</i>) für zwei Quellen ]]
+
[[Datei:P_ID2449__Inf_Z_2_5_neu.png|right|frame|Datenlänge $L(N)$  nach LZW&ndash;Codierung für $\rm BQ1$ und $\rm BQ2$]]
Wir betrachten wie in der [[Aufgaben:2.5_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5]] die Datenkomprimierung mit dem 1983 veröffentlichten [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|Lempel&ndash;Ziv&ndash;Welch&ndash;Algorithmus]]. Dabei gilt:
+
Wir betrachten wie in der&nbsp; [[Aufgaben:2.5_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5]]&nbsp; die Datenkomprimierung mit dem 1983 veröffentlichten&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;Algorithmus]]. Dabei gilt:
* Die Eingangsfolge habe die Länge <i>N</i>.
+
* Die Eingangsfolge habe die Länge&nbsp; $N$.
* Die Länge der LZW&ndash;Coderausgabe ist <i>L</i>.
+
* Die Länge der LZW&ndash;Coderausgabe ist&nbsp; $L$.
 +
 
 +
 
 +
Die Grafik zeigt für zwei verschiedene Binärquellen&nbsp; $\rm BQ1$&nbsp; und&nbsp; $\rm BQ2$&nbsp; den Zusammenhang zwischen den Folgenlängen&nbsp; $N$&nbsp; und&nbsp; $L$, dargestellt durch den Funktionsverlauf&nbsp; $L(N)$.&nbsp;
 +
 
 +
Die beiden Nachrichtenquellen besitzen die gleichen statistischen Eigenschaften wie in der&nbsp; [[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5]]:
 +
* $\rm BQ1$&nbsp; ist aufgrund von ungleichen Symbolwahrscheinlichkeiten&nbsp; $(p_{\rm A} = 0.89$&nbsp; und&nbsp; $p_{\rm B} = 0.11)$&nbsp; redundant.&nbsp; Es bestehen keine Bindungen zwischen den einzelnen Symbolen.&nbsp; Die Entropie ist&nbsp; $H = 0.5$ bit/Quellensymbol.
 +
* $\rm BQ2$&nbsp;  ist redundanzfrei und weist somit die Entropie&nbsp; $H = 1$ bit/Quellensymbol auf.
  
Die Grafik zeigt für zwei verschiedene binäre Nachrichtenquellen '''BQ1''' und '''BQ2''' den Zusammenhang zwischen den Folgenlängen <i>N</i> und <i>L</i>, dargestellt durch den Funktionsverlauf <i>L</i>(<i>N</i>). '''BQ1''' und '''BQ2''' besitzen die gleichen statistischen Eigenschaften wie in Aufgabe 2.5:
 
* '''BQ1''' ist aufgrund von ungleichen Symbolwahrscheinlichkeiten (<i>p</i><sub>A</sub> = 0.89, <i>p</i><sub>B</sub>&nbsp;=&nbsp;0.11) redundant. Es bestehen keine Bindungen zwischen den einzelnen Symbolen. Die Entropie ist <i>H</i> = 0.5 bit/Quellensymbol.
 
* '''BQ2'''  ist redundanzfrei und weist die Entropie <i>H</i> = 1 bit/Quellensymbol auf.
 
  
 
Weiter benötigen Sie für die Lösung dieser Aufagbe noch zwei Definitionen:
 
Weiter benötigen Sie für die Lösung dieser Aufagbe noch zwei Definitionen:
* Der <i>Komprimierungsfaktor</i> ist definitionsgemäß <i>K</i>(<i>N</i>) = <i>L</i>(<i>N</i>)/<i>N</i>.
+
* Der <i>Komprimierungsfaktor</i> sei definitionsgemäß  
* Die relative Redundanz der LZW&ndash;Coderfolge (im Folgenden <i>Restredundanz</i> genannt) ist
+
:$$K(N) = \frac{L(N)}{N}\hspace{0.05cm}.$$
 +
* Die relative Redundanz der LZW&ndash;Coderfolge&nbsp; (im Folgenden&nbsp; <i>Restredundanz</i>&nbsp; genannt)&nbsp; ist
 
:$$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}.$$
 +
 +
 +
 +
 +
 +
  
  
 
''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 [[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 [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Quantitative Aussagen zur asymptotischen Optimalität]].
+
*Insbesondere wird  Bezug genommen auf die Seiten
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
:: [[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]].
 +
  
  
Zeile 27: Zeile 41:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Komprimierungfaktoren <i>K</i> ergeben sich jeweils mit <i>N</i> = 10000?
+
{Welche Komprimierungfaktoren&nbsp; $K(N)$&nbsp; ergeben sich mit&nbsp; $N = 10000$?
 
|type="{}"}
 
|type="{}"}
$N = 10000, BQ1:\ K$ = { 0.68 3% }
+
$\rm BQ1$: &nbsp; &nbsp; $K(N = 10000) \ = \ $ { 0.68 3% }
$BQ2:\ K$ = { 1.233 3% }
+
$\rm BQ2$: &nbsp; &nbsp; $K(N = 10000) \ = \ $ { 1.233 3% }
  
  
{Wie groß ist die zugehörige Restredundanz (in Prozent)?
+
{Wie groß ist die Restredundanz&nbsp;  $r(N)$&nbsp; (in Prozent)?&nbsp; Es gelte wieder&nbsp; $N = 10000$.
 
|type="{}"}
 
|type="{}"}
$N = 10000, BQ1:\ r$ = { 26.5 3% } %
+
$\rm BQ1$: &nbsp; &nbsp; $r(N = 10000) \ = \ $ { 26.5 3% } $\ \%$
$BQ2:\ r$ = { 19 3% } %
+
$\rm BQ2$: &nbsp; &nbsp; $r(N = 10000) \ = \ $ { 19.0 3% } $\ \%$
  
  
{Welche Aussagen liefert der Vergleich von <i>N</i> = 10000 und <i>N</i> = 50000?
+
{Welche Aussagen liefert der Vergleich von&nbsp; $N = 10000$&nbsp; und&nbsp; $N = 50000$?
 
|type="[]"}
 
|type="[]"}
+ Bei beiden Quellen ist <i>K</i>(<i>N</i> = 50000) kleiner als <i>K</i>(<i>N</i> = 10000).
+
+ Bei beiden Quellen ist&nbsp; $K(N = 50000)$&nbsp; kleiner als&nbsp; $K(N = 10000)$.
+ Bei beiden Quellen ist <i>r</i>(<i>N</i> = 50000) kleiner als <i>r</i>(<i>N</i> = 10000).
+
+ Bei beiden Quellen ist&nbsp; $r(N = 50000)$&nbsp; kleiner als&nbsp; $r(N = 10000)$.
- Nur bei BQ1 ergeben sich mit <i>N</i> = 50000 günstigere Werte.
+
- Nur bei&nbsp; $\rm BQ1$&nbsp; ergeben sich mit&nbsp; $N = 50000$&nbsp; günstigere Werte.
  
  
Zeile 51: Zeile 65:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Der Komprimierungsfaktor ist definiert als der Quotient der Längen von LZW&ndash;Ausgangsfolge (<i>L</i>) und Eingangsfolge (<i>N</i> = 10000):
+
'''(1)'''&nbsp; Der Komprimierungsfaktor ist definiert als der Quotient der Längen von LZW&ndash;Ausgangsfolge&nbsp; $(L)$&nbsp; und Eingangsfolge&nbsp; $(N = 10000)$:
:$${\rm BQ1:}\hspace{0.3cm} K \hspace{0.2cm} =  \hspace{0.2cm} \frac{6800}{10000}\hspace{0.15cm}\underline{= 0.680}\hspace{0.05cm},\\ \\
+
:$${\rm BQ1:}\hspace{0.3cm} K \hspace{0.2cm} =  \hspace{0.2cm} \frac{6800}{10000}\hspace{0.15cm}\underline{= 0.680}\hspace{0.05cm},$$
{\rm BQ2:}\hspace{0.3cm} K \hspace{0.2cm} =  \hspace{0.2cm} \frac{12330}{10000}\hspace{0.15cm}\underline{= 1.233}\hspace{0.05cm}. $$
+
:$$ {\rm BQ2:}\hspace{0.3cm} K \hspace{0.2cm} =  \hspace{0.2cm} \frac{12330}{10000}\hspace{0.15cm}\underline{= 1.233}\hspace{0.05cm}. $$
:Die Lempel&ndash;Ziv&ndash;Codierung macht natürlich nur bei der redundanten Binärquelle BQ1 Sinn. Hier kann die Datenmenge um 32% gesenkt werden. Bei der redundanzfreien Binärquelle BQ2 führt dagegen die LZ&ndash;Codierung zu einer um 23.3% größeren Datenmenge.
+
*Die LZW&ndash;Codierung macht natürlich nur bei der redundanten Binärquelle&nbsp; $\rm BQ1$&nbsp; Sinn.&nbsp; Hier kann die Datenmenge um&nbsp; $32\%$&nbsp; gesenkt werden.  
 +
*Bei der redundanzfreien Binärquelle&nbsp; $\rm BQ2$&nbsp; führt dagegen die LZW&ndash;Codierung zu einer um&nbsp; $23.3\%$&nbsp; größeren Datenmenge.
 +
 
  
:<b>2.</b>&nbsp;&nbsp;Aus der angegebenen Gleichung erhält man mit <i>N</i> = 10000:
 
:$${\rm BQ1:}\hspace{0.3cm} H = 0.5\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} =  \hspace{0.2cm}1 - \frac{0.5 \cdot N}{L } = 1 - \frac{5000}{6800 }  \hspace{0.15cm}\underline{\approx 26.5\,\%}\hspace{0.05cm},\\  \\
 
{\rm BQ2:}\hspace{0.3cm} H = 1.0\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} =  \hspace{0.2cm}1 - \frac{N}{L } = 1 - \frac{10000}{12330 }  \hspace{0.15cm}\underline{\approx 19\,\%}\hspace{0.05cm}.$$
 
:Die Restredundanz gibt die (relative) Redundanz der LZ&ndash;Ausgangsfolge an. Obwohl die Quelle BQ1 für die LZ&ndash;Codierung besser geeignet ist als die redundanzfreie Quelle BQ2, ergibt sich bei BQ1 wegen der Redundanz in der Eingangsfolge eine größere Restredundanz.
 
  
:Eine kleinere Restredundanz <i>r</i>(<i>N</i>) bei gegebenem <i>N</i> sagt also nichts darüber aus, ob der Einsatz von Lempel&ndash;Ziv für die vorliegende Quelle sinnvoll ist. Hierzu muss der Komprimierungsfaktor <i>K</i> betrachtet werden. Allgemein gilt folgender Zusammenhang zwischen <i>r</i>(<i>N</i>) und <i>K</i>(<i>N</i>):
+
'''(2)'''&nbsp; Aus der angegebenen Gleichung erhält man mit&nbsp; $N = 10000$:
:$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.2cm} K(N) = H \cdot (1- r(N))
+
:$${\rm BQ1:}\hspace{0.3cm} H = 0.5\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} =  \hspace{0.2cm}1 - \frac{0.5 \cdot N}{L } = 1 - \frac{5000}{6800 }  \hspace{0.15cm}\underline{\approx 26.5\,\%}\hspace{0.05cm},$$
 +
:$$ {\rm BQ2:}\hspace{0.3cm} H = 1.0\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} =  \hspace{0.2cm}1 - \frac{N}{L } = 1 - \frac{10000}{12330 }  \hspace{0.15cm}\underline{\approx 19\,\%}\hspace{0.05cm}.$$
 +
*Die Restredundanz gibt die (relative) Redundanz der LZW&ndash;Ausgangsfolge an.
 +
*Obwohl die Quelle&nbsp; $\rm BQ1$&nbsp; für die LZW&ndash;Codierung besser geeignet ist als die redundanzfreie Quelle&nbsp; $\rm BQ2$, ergibt sich bei&nbsp; $\rm BQ1$&nbsp; wegen der Redundanz in der Eingangsfolge eine größere Restredundanz.
 +
*Eine kleinere Restredundanz&nbsp; $r(N)$&nbsp; bei gegebenem&nbsp; $N$&nbsp; sagt also nichts darüber aus, ob die LZW&ndash;Codierung für die vorliegende Quelle sinnvoll ist.  
 +
*Hierzu muss der Komprimierungsfaktor&nbsp; $K(N)$&nbsp; betrachtet werden.&nbsp; Allgemein gilt folgender Zusammenhang zwischen&nbsp; $r(N)$&nbsp; und&nbsp; $K(N)$:
 +
:$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.5cm} K(N) = H \cdot (1- r(N))
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
:<b>3.</b>&nbsp;&nbsp;Aus der Tabelle auf der Angabenseite kann man ablesen (bzw. daraus ableiten)
 
  
:für die redundante Binärquelle BQ1:
+
'''(3)'''&nbsp; Aus der Tabelle auf der Angabenseite kann man ablesen&nbsp; (bzw. daraus ableiten)
:$$L(N = 50000) = 32100\hspace{0.05cm},\hspace{0.2cm} K(N = 50000) = 0.642\hspace{0.05cm},\hspace{0.2cm}r(N = 50000) \hspace{0.15cm}\underline {= 22.2\,\% \hspace{0.05cm}},$$
+
 
:für die redundanzfreie Binärquelle BQ2:
+
*für die redundante Binärquelle&nbsp; $\rm BQ1$:
:$$L(N = 50000) = 59595\hspace{0.05cm},\hspace{0.2cm} K(N = 50000) = 1.192\hspace{0.05cm},\hspace{0.2cm}r(N = 50000) \hspace{0.15cm}\underline {= 16.1\,\% \hspace{0.05cm}}.$$
+
:$$L(N = 50000) = 32100\hspace{0.05cm},\hspace{0.5cm} K(N = 50000) = 0.642\hspace{0.05cm},\hspace{0.5cm}r(N = 50000) \hspace{0.15cm}\underline {= 22.2\,\% \hspace{0.05cm}},$$
:Richtig sind somit die <u>Aussagen 1 und 2</u>. Für beide Quellen ist <i>K</i>(<i>N</i> = 50000) < <i>K</i>(<i>N</i> = 10000) und <i>r</i>(<i>N</i>&nbsp;=&nbsp;50000) < <i>r</i>(<i>N</i> = 10000). In beiden Fällen ergeben sich also bei größerem <i>N</i> &bdquo;günstigere&rdquo; Werte, auch dann, wenn eigentlich wie bei der redundanzfreien Binärquelle BQ2 die Anwendung von Lempel&ndash;Ziv zu einer Verschlechterung führt.
+
*für die redundanzfreie Binärquelle&nbsp; $\rm BQ2$:
 +
:$$L(N = 50000) = 59595\hspace{0.05cm},\hspace{0.5cm} K(N = 50000) = 1.192\hspace{0.05cm},\hspace{0.5cm}r(N = 50000) \hspace{0.15cm}\underline {= 16.1\,\% \hspace{0.05cm}}.$$
 +
 
 +
Richtig sind somit die <u>Aussagen 1 und 2</u>:
 +
* Für beide Quellen ist der Komprimierungsfaktor &nbsp;$K(N)$&nbsp; für  &nbsp;$N = 50000$&nbsp; kleiner als für &nbsp;$N = 10000$.
 +
* Gleiches gilt für die Restredundanz: &nbsp; $r(N = 50000) < r(N = 10000)$.
 +
* Sowohl hinsichtlich &nbsp;$K(N)$&nbsp; als auch hinsichtlich&nbsp; $r(N)$&nbsp; ergeben sich also bei größerem&nbsp; $N$&nbsp; &bdquo;günstigere&rdquo; Werte, auch dann, wenn eigentlich wie bei der redundanzfreien Binärquelle&nbsp; $\rm BQ2$&nbsp; die Anwendung von Lempel&ndash;Ziv zu einer Verschlechterung führt.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 24. Januar 2020, 14:29 Uhr

Datenlänge $L(N)$ nach LZW–Codierung für $\rm BQ1$ und $\rm BQ2$

Wir betrachten wie in der  Aufgabe 2.5  die Datenkomprimierung mit dem 1983 veröffentlichten  Lempel–Ziv–Welch–Algorithmus. Dabei gilt:

  • Die Eingangsfolge habe die Länge  $N$.
  • Die Länge der LZW–Coderausgabe ist  $L$.


Die Grafik zeigt für zwei verschiedene Binärquellen  $\rm BQ1$  und  $\rm BQ2$  den Zusammenhang zwischen den Folgenlängen  $N$  und  $L$, dargestellt durch den Funktionsverlauf  $L(N)$. 

Die beiden Nachrichtenquellen besitzen die gleichen statistischen Eigenschaften wie in der  Aufgabe 2.5:

  • $\rm BQ1$  ist aufgrund von ungleichen Symbolwahrscheinlichkeiten  $(p_{\rm A} = 0.89$  und  $p_{\rm B} = 0.11)$  redundant.  Es bestehen keine Bindungen zwischen den einzelnen Symbolen.  Die Entropie ist  $H = 0.5$ bit/Quellensymbol.
  • $\rm BQ2$  ist redundanzfrei und weist somit die Entropie  $H = 1$ bit/Quellensymbol auf.


Weiter benötigen Sie für die Lösung dieser Aufagbe noch zwei Definitionen:

  • Der Komprimierungsfaktor sei definitionsgemäß
$$K(N) = \frac{L(N)}{N}\hspace{0.05cm}.$$
  • Die relative Redundanz der LZW–Coderfolge  (im Folgenden  Restredundanz  genannt)  ist
$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$





Hinweise:

Restredrundanz als Maß für die Effizienz von Codierverfahren,
Effizienz der Lempel-Ziv-Codierung sowie
Quantitative Aussagen zur asymptotischen Optimalität.


Fragebogen

1

Welche Komprimierungfaktoren  $K(N)$  ergeben sich mit  $N = 10000$?

$\rm BQ1$:     $K(N = 10000) \ = \ $

$\rm BQ2$:     $K(N = 10000) \ = \ $

2

Wie groß ist die Restredundanz  $r(N)$  (in Prozent)?  Es gelte wieder  $N = 10000$.

$\rm BQ1$:     $r(N = 10000) \ = \ $

$\ \%$
$\rm BQ2$:     $r(N = 10000) \ = \ $

$\ \%$

3

Welche Aussagen liefert der Vergleich von  $N = 10000$  und  $N = 50000$?

Bei beiden Quellen ist  $K(N = 50000)$  kleiner als  $K(N = 10000)$.
Bei beiden Quellen ist  $r(N = 50000)$  kleiner als  $r(N = 10000)$.
Nur bei  $\rm BQ1$  ergeben sich mit  $N = 50000$  günstigere Werte.


Musterlösung

(1)  Der Komprimierungsfaktor ist definiert als der Quotient der Längen von LZW–Ausgangsfolge  $(L)$  und Eingangsfolge  $(N = 10000)$:

$${\rm BQ1:}\hspace{0.3cm} K \hspace{0.2cm} = \hspace{0.2cm} \frac{6800}{10000}\hspace{0.15cm}\underline{= 0.680}\hspace{0.05cm},$$
$$ {\rm BQ2:}\hspace{0.3cm} K \hspace{0.2cm} = \hspace{0.2cm} \frac{12330}{10000}\hspace{0.15cm}\underline{= 1.233}\hspace{0.05cm}. $$
  • Die LZW–Codierung macht natürlich nur bei der redundanten Binärquelle  $\rm BQ1$  Sinn.  Hier kann die Datenmenge um  $32\%$  gesenkt werden.
  • Bei der redundanzfreien Binärquelle  $\rm BQ2$  führt dagegen die LZW–Codierung zu einer um  $23.3\%$  größeren Datenmenge.


(2)  Aus der angegebenen Gleichung erhält man mit  $N = 10000$:

$${\rm BQ1:}\hspace{0.3cm} H = 0.5\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} = \hspace{0.2cm}1 - \frac{0.5 \cdot N}{L } = 1 - \frac{5000}{6800 } \hspace{0.15cm}\underline{\approx 26.5\,\%}\hspace{0.05cm},$$
$$ {\rm BQ2:}\hspace{0.3cm} H = 1.0\hspace{0.05cm},\hspace{0.2cm} r(N=10000) \hspace{0.2cm} = \hspace{0.2cm}1 - \frac{N}{L } = 1 - \frac{10000}{12330 } \hspace{0.15cm}\underline{\approx 19\,\%}\hspace{0.05cm}.$$
  • Die Restredundanz gibt die (relative) Redundanz der LZW–Ausgangsfolge an.
  • Obwohl die Quelle  $\rm BQ1$  für die LZW–Codierung besser geeignet ist als die redundanzfreie Quelle  $\rm BQ2$, ergibt sich bei  $\rm BQ1$  wegen der Redundanz in der Eingangsfolge eine größere Restredundanz.
  • Eine kleinere Restredundanz  $r(N)$  bei gegebenem  $N$  sagt also nichts darüber aus, ob die LZW–Codierung für die vorliegende Quelle sinnvoll ist.
  • Hierzu muss der Komprimierungsfaktor  $K(N)$  betrachtet werden.  Allgemein gilt folgender Zusammenhang zwischen  $r(N)$  und  $K(N)$:
$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.5cm} K(N) = H \cdot (1- r(N)) \hspace{0.05cm}.$$


(3)  Aus der Tabelle auf der Angabenseite kann man ablesen  (bzw. daraus ableiten)

  • für die redundante Binärquelle  $\rm BQ1$:
$$L(N = 50000) = 32100\hspace{0.05cm},\hspace{0.5cm} K(N = 50000) = 0.642\hspace{0.05cm},\hspace{0.5cm}r(N = 50000) \hspace{0.15cm}\underline {= 22.2\,\% \hspace{0.05cm}},$$
  • für die redundanzfreie Binärquelle  $\rm BQ2$:
$$L(N = 50000) = 59595\hspace{0.05cm},\hspace{0.5cm} K(N = 50000) = 1.192\hspace{0.05cm},\hspace{0.5cm}r(N = 50000) \hspace{0.15cm}\underline {= 16.1\,\% \hspace{0.05cm}}.$$

Richtig sind somit die Aussagen 1 und 2:

  • Für beide Quellen ist der Komprimierungsfaktor  $K(N)$  für  $N = 50000$  kleiner als für  $N = 10000$.
  • Gleiches gilt für die Restredundanz:   $r(N = 50000) < r(N = 10000)$.
  • Sowohl hinsichtlich  $K(N)$  als auch hinsichtlich  $r(N)$  ergeben sich also bei größerem  $N$  „günstigere” Werte, auch dann, wenn eigentlich wie bei der redundanzfreien Binärquelle  $\rm BQ2$  die Anwendung von Lempel–Ziv zu einer Verschlechterung führt.