Exercise 2.2Z: Average Code Word Length

• Return to book

Three source coding tables

The aim of data compression is to represent the message of a source with as few binary characters as possible.

We consider here a discrete message source with the symbol set  $\rm \{ A, \ B, \ C, \ D\}$   ⇒   symbol set size  $M = 4$  and the symbol probabilities

• $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$  $($subtask  $1)$,
• $p_{\rm A} = 1/2, \, p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$  $($subtask  $2$  to  $5)$.

It is assumed that there are no statistical Dependencies between the individual source symbols.

Three assignments are given. To be noted:

• Each of these binary codes  $\rm C1$,  $\rm C2$  and  $\rm C3$  is designed for a specific source statistic.
• All codes are prefix-free and thus immediately decodable without further specification.

A measure for the quality of a compression method is the average code word length  $L_{\rm M}$  with the additional unit  "bit/source symbol".

Hint:

• The exercise belongs to the chapter  General Description of Source Coding.

Questions

1

Determine the average code word length  $L_{\rm M}$  for  $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$.

$\text{C1:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

$\text{C2:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

$\text{C3:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

2

Which values result for  $p_{\rm A} = 1/2, \, p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$?

$\text{C1:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

$\text{C2:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

$\text{C3:}\ \ L_{\rm M} \ = \ $ $\ \rm bit/source\hspace{0.15cm} symbol$

3

How can you recognise prefix-free codes?

	No code word is the beginning of another code word.
	All code words have the same length.

4

For the special source symbol sequence  $\rm ADBDCBCBADCA$ , the encoded sequence  $\rm 001101111001100100111000$  results.
Which code was used?

	The code  $\rm C1$,
	the code  $\rm C2$.

5

After coding with  $\rm C3$,  you get  $\rm 001101111001100100111000$.  What is the corresponding source symbol sequence?

	$\rm AACDBACABADAAA$ ...
	$\rm ACBCCCACAACCD$ ...

Solution

Solution

(1)  The average code word length is generally given by

$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}.$$

If the four source symbols are equally probable  $($all probabilities exactly  $1/4)$, then for this we can also write:

$$L_{\rm M} = 1/4 \cdot ( L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D}) \hspace{0.05cm}.$$

• $\text{Code C1:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/source\hspace{0.15cm} symbol$,
• $\text{Code C2:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source\hspace{0.15cm} symbol$
• $\text{Code C3:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/source\hspace{0.15cm} symbol$.

(2)  With the code table  $\text{C1}$ , the average code word length  $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \rm bit/source\hspace{0.15cm} symbol$  is always obtained, independent of the symbol probabilities.

For the other two codes one obtains:

• $\text{Code C2:}$    $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/source\hspace{0.15cm} symbol$,
• $\text{Code C3:}$    $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/source\hspace{0.15cm} symbol$.

From the example you can see the principle:

• Probable symbols are represented by a few binary symbols, improbable ones by more.
• In the case of equally probable symbols, it is best to choose the same code word lengths.

(3)  Solution suggestion 1 is correct:

• The code  $\text{C1}$  with uniform length of all code words is prefix-free,
• but other codes can also be prefix-free, for example the codes  $\text{C2}$  and  $\text{C3}$.

(4)  Solution suggestion 1 is correct:

• Already from  "00"  at the beginning one can see that the code  $\text{C2}$  is out of the question here,
  because otherwise the source symbol sequence would have to begin with  "AA".
• In fact, the code  $\text{C1}$  was used.

(5)  Solution suggestion 2 is correct.

The first suggested solution gives the source symbol sequence for code  $\text{C2}$  if the encoded sequence would be   "$\rm 001101111001100100111000$".