Information Theory

1. Answer

a. I mentioned that “higher order” models can be used for computing probabilities. How may entries would a probability table using an order-1 model have?

b. Arithmetic coding suffers from the EOF problem. Given the following probabilities: E: 0.4; I: 0.3; O: 0.2; A: 0.1;
Give three strings that would result in the same final code (real number) as the string “IEIA0”.
Note: Trust me, you don’t need a calculator to answer this question.

2. Answer

a. State the sibling property.

b. Number the following tree according to the sibling property

3. Answer true or false

a. In adaptive Huffman coding, a swap of two nodes involves moving entire sub-trees under the nodes and not just the two nodes.

b. In adaptive Huffman, the encoder and decoder use the same initialize_model and update_model routines.

c. The Arithmetic coding is an adaptive coding mechanism.

d. In adaptive Huffman, the same symbol can have different codes at different points in the sequence.