Question 1

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

Accepted Answer

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.

Accepted Answer

(15)
B : (7)
C : (6)
D : (6)
E : (5)

Shannon-Fano Algorithm:
Step 1: Sort the characters based on their frequency counts in descending order.
A: (15)
B: (7)
C: (6)
D: (6)
E: (5)

Step 2: Split the characters into two groups such that the total frequency count of each group is approximately equal.
Group 1: A (15)
Group 2: B (7), C (6), D (6), E (5)

Step 3: Assign binary codes to each group, with 0 for Group 1 and 1 for Group 2.
Group 1: A (15) - 0
Group 2: B (7), C (6), D (6), E (5) - 1

Step 4: Repeat steps 2 and 3 for each group until each character has its own binary code.
A: 0
B: 10
C: 110
D: 1110
E: 1111

Total bits required = (15*1) + (7*2) + (6*3) + (6*4) + (5*4) = 89 bits

Huffman Algorithm:
Step 1: Create a min-heap of characters based on their frequency counts.
Step 2: Merge the two characters with the lowest frequency counts into a single node, and update the frequency count of the new node.
Step 3: Repeat step 2 until all characters are merged into a single tree.

A: (15)
B: (7)
C: (6)
D: (6)
E: (5)

Merging steps:
1. E (5) + D (6) = ED (11)
2. C (6) + B (7) = CB (13)
3. ED (11) + CB (13) = EDCB (24)
4. A (15) + EDCB (24) = AEDCB (39)

Binary codes:
A: 0
B: 101
C: 100
D: 111
E: 110

Total bits required = (15*1) + (7*3) + (6*3) + (6*3) + (5*3) = 87 bits

Therefore, the Shannon-Fano algorithm produces a tree that encodes the given string in a total of 89 bits, whereas the Huffman algorithm needs only 87 bits.

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

Accepted Answer

(a) Using Arithmetic Coding, the resulting bitstrings for input $XXX$ and $YXX$ are as follows:
- For input $XXX$, the resulting bitstring would be $0.100$.
- For input $YXX$, the resulting bitstring would be $0.010$.

(b) 
(1) An Adaptive Arithmetic Coding algorithm would work by dynamically updating the probabilities of symbols as new symbols are encountered. The algorithm would maintain a probability model that is updated based on the frequency of occurrence of symbols. When encoding, the algorithm would use the updated probability model to determine the intervals for each symbol and generate the corresponding bitstring. For simplicity, let's assume both encoder and decoder know that exactly $k=3$ symbols will be sent each time.

(2) For the given sequence of messages: 
- Initially, the sequence is $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 Y Y Y Y Y Y Y Y Y Y Y$.

(i) Encoding the first $XXX$:
- The initial probability model would assign $P_{X}=2 / 3$ and $P_{Y}=1 / 3$.
- The algorithm would use the probability model to encode the first $XXX$ and generate the resulting bitstring.

(ii) Encoding the second $XXX$:
- After encountering the first $XXX$, the algorithm would update the probability model based on the frequency of occurrence of symbols.
- The updated probability model would be used to encode the second $XXX$ and generate the resulting bitstring.

(iii) Encoding the last $YYY$:
- After encountering the sequence of $11 YYY \mathrm{~s}$, the algorithm would again update the probability model based on the frequency of occurrence of symbols.
- The updated probability model would be used to encode the last $YYY$ and generate the resulting bitstring.

Overall, the Adaptive Arithmetic Coding algorithm would adapt to the changing symbol probabilities and generate the corresponding bitstrings for the given sequence of messages.

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

Accepted Answer

The answer of For the LZW algorithm, assume an alphabet...

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.

Accepted Answer

The answer of Consider an alphabet with three symbols \(A,...

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}$

Accepted Answer

The answer of Is the following code uniquely decodable? 
\(\begin{aligned}
1...

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?

Accepted Answer

The answer of Consider the question of whether it is...

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.

Accepted Answer

The answer of Suppose we wish to transmit the 10-character...

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?

Accepted Answer

The answer of If the source string MULTIMEDIA is now...

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?

Accepted Answer

The answer of Using the Lempel-Ziv-Welch (LZW) algorithm, encode the...

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:

Accepted Answer

The answer of Construct a binary Huffman code for a...

Quiz 4: Lossless Compression Algorithms

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

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.

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.

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

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?

Quiz 4: Lossless Compression Algorithms

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

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.

Is the following code uniquely decodable? 1↦a2↦aba3↦bab\begin{aligned}1 & \mapsto a \\2 & \mapsto a b a \\3 & \mapsto b a b\end{aligned}123​↦a↦aba↦bab​

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?

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