Deck 4: Lossless Compression Algorithms

Question 1

Calculate the entropy of a "checkerboard" image in which half of the pixels are BLACK and half of them are WHITE.

Answer 1

1 bit/symbol.

Question 2

Consider a text string containing a set of characters and their frequency counts as follows: A: (15), B: (7), C: (6), D: (6) and E: (5). Show that the Shannon-Fano algorithm produces a tree that encodes this string in a total of 89 bits, whereas the Huffman algorithm needs only 87 bits.

Answer 2

Not Answer

Question 3

Suppose we have a source consisting of two symbols, $X$ and $Y$ , with probabilities $P_{X}=2 / 3$ and $P_{Y}=1 / 3$ .
(a) Using Arithmetic Coding, what are the resulting bitstrings, for input $XXX$ and $YXX$ ?
(b) A major advantage of adaptive algorithms is that no a priori knowledge of symbol probabilities is required.
(1) Propose an Adaptive Arithmetic Coding algorithm and briefly describe how it would work. For simplicity, let's assume both encoder and decoder know that exactly $k=3$ symbols will be sent each time.
(2) Assume the sequence of messages is initially $3 XXX \mathrm{~s}$ , followed by $11 YYY \mathrm{~s}-$ the sequence is $X X X X X X X X X Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y$ $Y Y Y$ .
Show how your Adaptive Arithmetic Coding algorithm works, for this sequence, for encoding: (i) the first $XXX$ , (ii) the second $XXX$ , and (iii) the last $YYY$ .

Answer 3

Not Answer

Question 4

For the LZW algorithm, assume an alphabet $\{*$ a b o d $\}$ of size 5 from which text characters are picked.
Suppose the following string of characters is to be transmitted (or stored):
$\mathrm{dabba} * \mathrm{dabba} * \mathrm{dabba} * \mathrm{doo} * \mathrm{doo} \ldots$
The coder starts with an initial dictionary consisting of the above 5 characters and an index assignment, as in the following table:

Make a table showing the string being assembled, the current character, the output, the new symbol, and the index corresponding to the symbol, for the above input - only go as far as "d a b b a d a b b a * d".

Question 5

Consider an alphabet with three symbols $A, B, C$ , with probability $P(A)=x, P(C)=y$ . and $P(C)=1-x-y$ .
State how you would go about plotting the entropy as a function of $x$ and $y$ . Pseudocode is perhaps the best way to state your answer.

Question 6

Is the following code uniquely decodable?
$\begin{aligned}1 & \mapsto a \\2 & \mapsto a b a \\3 & \mapsto b a b\end{aligned}$

Question 7

Consider the question of whether it is true that the size of the Huffman code of a symbol $a_{i}$ with probability $p_{i}$ is always less than or equal to $\left\lceil-\log p_{i}\right\rceil$ .
As a counter example, let the source alphabet be $\{=a, b\}$ . Given $p(a)$ and $p(b)$ , construct a Huffman tree. Will the tree be different for different values for $p(a)$ and $p(b)$ ? What conclusion can you draw?

Question 8

Suppose we wish to transmit the 10-character string "MULTIMEDIA". The characters in the string are chosen from a finite alphabet of 8 characters.
(a) What are the probabilities of each character in the source string?
(b) Compute the entropy of the source string.
(c) If the source string is encoded using Huffman coding, draw the encoding tree and compute the average number of bits needed.

Question 9

If the source string MULTIMEDIA is now encoded using Arithmetic coding, what is the codeword in fractional decimal representation. How many bits are needed for coding in binary format? How does this compare to the entropy?

Question 10

Using the Lempel-Ziv-Welch (LZW) algorithm, encode the following source symbol sequence: MISSISSIPPI\#
Show initial codes as ASCII: e.g., "M". Start new codes with the code value 256.
(b) Assuming the source characters (ASCII) and the dictionary entry codes are combined and represented by a 9-bit code, calculate the total number of bits needed for encoding the source string up to the \# character, i.e. just MISSISSIPPI. What is the compression ratio, compared to simply using 8-bit ASCII codes for the input characters?

Question 11

Construct a binary Huffman code for a source $S$ with three symbols $A, B$ and $C$ , having probabilities $0.6,0.3$ , and 0.1 , respectively. What is its average codeword length, in bits per symbol? What is the entropy of this source?
(b) Let's now extend this code by grouping symbols into 2-character groups - a type of VQ. Compare the performance now, in bits per original source symbol, with the best possible.
Fig. 7.1: