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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 51: Zeile 51:
 
===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 (<i>L</i>) und Eingangsfolge (<i>N</i> = 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 '''BQ1''' Sinn. Hier kann die Datenmenge um 32% gesenkt werden.  
 +
*Bei der redundanzfreien Binärquelle '''BQ2''' führt dagegen die LZW&ndash;Codierung zu einer um 23.3% 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 <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 LZWQ&ndash;Ausgangsfolge an.
 +
*Obwohl die Quelle '''BQ1''' für die LZW&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 die LZW&ndash;Codierung 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>):
 
:$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.2cm} K(N) = H \cdot (1- r(N))
 
:$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.2cm} 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)
+
'''(3)'''&nbsp; Aus der Tabelle auf der Angabenseite kann man ablesen (bzw. daraus ableiten)
  
:für die redundante Binärquelle BQ1:
+
*für die redundante Binärquelle '''BQ1''':
 
:$$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}},$$
 
:$$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 redundanzfreie Binärquelle '''BQ2''':
 
:$$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) = 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}}.$$
: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.
+
 
 +
Richtig sind somit die <u>Aussagen 1 und 2</u>:
 +
* Für beide Quellen ist der Komprimierungsfaktor <i>K</i>(<i>N</i>) für  <i>N</i> = 50000 kleiner als für <i>N</i> = 10000.
 +
* Gleiches gilt für die Resrredundanz: <i>r</i>(<i>N</i>&nbsp;=&nbsp;50000) ist kleiner als <i>r</i>(<i>N</i>&nbsp;=&nbsp;10000).
 +
* Sowohl hinsichtlich <i>K</i>(<i>N</i>)  als auch hinsichtlich <i>r</i>(<i>N</i>) 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.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Version vom 22. Mai 2017, 14:35 Uhr

LZW–Datenlänge L(N) für zwei Quellen

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äre Nachrichtenquellen BQ1 und 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 Aufgabe 2.5:

  • BQ1 ist aufgrund von ungleichen Symbolwahrscheinlichkeiten (pA = 0.89, pB = 0.11) redundant. Es bestehen keine Bindungen zwischen den einzelnen Symbolen. Die Entropie ist H = 0.5 bit/Quellensymbol.
  • BQ2 ist redundanzfrei und weist die Entropie H = 1 bit/Quellensymbol auf.

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

  • Der Komprimierungsfaktor ist definitionsgemäß K(N) = L(N)/N.
  • 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:


Fragebogen

1

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

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

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

2

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

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

$\ \%$
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 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 BQ1 Sinn. Hier kann die Datenmenge um 32% gesenkt werden.
  • Bei der redundanzfreien Binärquelle 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 LZWQ–Ausgangsfolge an.
  • Obwohl die Quelle BQ1 für die LZW–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 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 betrachtet werden. Allgemein gilt folgender Zusammenhang zwischen r(N) und K(N):
$$r(N) = 1 - \frac{H}{K(N)}\hspace{0.05cm},\hspace{0.2cm} 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 BQ1:
$$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:
$$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}}.$$

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 Resrredundanz: r(N = 50000) ist kleiner als 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 BQ2 die Anwendung von Lempel–Ziv zu einer Verschlechterung führt.