Aufgaben:Exercise 2.5Z: Compression Factor vs. Residual Redundancy

• Return to book

Data length $L(N)$ after LZW coding for $\rm BQ1$ and $\rm BQ2$

As in  exercise 2.5  we consider data compression using the  Lempel–Ziv–Welch–algorithm. Here holds:

• Let the input sequence have length  $N$.
• The length of the LZW coder output is  $L$.

The graph shows for two different binary sources  $\rm BQ1$  and  $\rm BQ2$  the relationship between the sequence lengths  $N$  and  $L$, represented by the function  $L(N)$. 

The two message sources have the same statistical properties as in  exercise 2.5:

• $\rm BQ1$  is redundant due to unequal symbol probabilities  $(p_{\rm A} = 0.89$  and  $p_{\rm B} = 0.11)$ .  There are no ties between the individual symbols.  The entropy is  $H = 0.5$ bit/source symbol.
• $\rm BQ2$  is redundancy-free and thus has entropy  $H = 1$ bit/source symbol.

Furthermore, you need two definitions for the solution of this task:

• Let the compression factor be by definition

$$K(N) = \frac{L(N)}{N}\hspace{0.05cm}.$$

• The relative redundancy of the LZW code sequence  (called  residual redundancy  in the following)  is

$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}.$$

Hints:

• The task belongs to the chapter  Compression according to Lempel, Ziv and Welch.
• In particular, reference is made to the pages

Residual redundancy as a measure of the efficiency of coding methods,

Efficiency of Lempel-Ziv coding and

Quantitative statements on asymptotic optimality.

Questions

1

Which compression factors  $K(N)$  result with  $N = 10000$?

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

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

2

What is the residual redundancy  $r(N)$  (in percent)?  Let  $N = 10000$ apply again.

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

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

3

What conclusions can be drawn from the comparison of  $N = 10000$  And  $N = 50000$?

	For both sources  $K(N = 50000)$  is smaller than  $K(N = 10000)$.
	For both sources  $r(N = 50000)$  is smaller than  $r(N = 10000)$.
	Only  $\rm BQ1$  has more favourable values with  $N = 50000$  günstigere Werte.

Musterlösung

Solution

(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.