[SOLVED] Ee276 homework #3 p0

1. Bad codes.
Which of these codes cannot be a Huffman code for any probability assignment? Justify your answers.
(a) {0,10,11}.
(b) {00,01,10,110}.
(c) {01,10}.
2. Coin Toss Experiment and Golomb Codes
Kedar, Mikel and Naroa have been instructed to record the outcomes of a coin toss experiment. Consider the coin toss experiment X1,X2,X3,… where Xi are i.i.d. Bern(p) (probability of a H (head) is p), p = 15/16.
(a) Kedar decides to use Huffman coding to represent the outcome of each coin toss separately. What is the resulting scheme? What compression rate does it achieve?
(b) Mikel suggests he can do a better job by applying Huffman coding on blocks of r tosses. Construct the Huffman code for r = 2.
(c) Will Mikel’s scheme approach the optimum expected number of bits per description of source symbol (coin toss outcome) with increasing r? How does the space required to represent the codebook increase as we increase r?
(d) Naroa suggests that, as the occurrence of T is so rare, we should just record the number of tosses it takes for each T to occur.
To be precise, if Yk represents the number of trials until the kth T occurred (inclusive), then Naroa records the sequence:
Zk = Yk − Yk−1, k ≥ 1, (1)
where Y0 = 0
i. What is the distribution of Zk, i.e., P(Zk = j),j = 1,2,3,…?
ii. Compute the entropy and expectation of Zk.
iii. How does the ratio between the entropy and the expectation of Zk compare to the entropy of Xk? Give an intuitive interpretation.
(e) Consider the following scheme for encoding Zk, which is a specific case of Golomb Coding. We are showing the first 10 codewords.
Z Quotient Remainder Code
1 0 1 1 01
2 0 2 1 10
3 0 3 1 11
4 1 0 0 1 00
5 1 1 0 1 01
6 1 2 0 1 10
7 1 3 0 1 11
8 2 0 00 1 00
9 2 1 00 1 01 10 2 2 00 1 10
i. Can you guess the general coding scheme? Compute the expected codelength of this code.
ii. What is the decoding rule for this Golomb code? iii. What makes this codebook suitable for efficient encoding and decoding?
3. Arithmetic Coding.
0.3
0.1 0.106
!” = [0,1) !) = [0.1,0.3) !, = [0.1,0.12) !. = [0.106,0.12)
Figure 1: Illustration of arithmetic coding.
Note: Throughout this problem, we will work with digits rather than bits for simplicity. So the logarithms will be base 10 and the compressor will output digits {0,1,…,9}.
This problem introduces a simplified version of arithmetic coding, which is itself based on Shannon-Fano-Elias coding. Arithmetic coding takes as input a sequence xn ∈ Xn and a distribution q over X. The encoder maintains an interval which is transformed at each step as follows:
• Start with I0 = [0,1).
• For i = 1,…,n:
– Divide Ii−1 into |X| half-open subintervals with length of proportional to q(x), i.e., for x ∈ X.
– Set
Figure 1 shows an example of this for X = {R,G,B}, (q(R),q(G),q(B)) = (0.1,0.2,0.7) and x3 = GRB. At the end of this process, the encoder selects a number in the interval In and outputs the digits after the decimal point for that number. In the example shown, the encoder can output 11, which corresponds to 0.11 ∈ [0.106,0.12). While 1103 (corresponding to 0.1103) is also a valid output, the encoder tries to output the shortest possible valid sequence. The YouTube video https://youtu.be/ FdMoL3PzmSA might be helpful for understanding this process even better.
(a) Briefly explain how the decoding might work in a sequential manner. You can assume that the decoder knows the alphabet, the distribution q and the length of the source sequence n.
(b) What is the length of interval In in terms of q and xn?
(c) For the following intervals In obtained by following the above-described process for some xn, find the length of the shortest output sequence (in digits):
i. [0.095,0.105) ii. [0.11,0.12) iii. [0.1011,0.102)
In general, if the interval length is ln, then the shortest output sequence has at most digits.
(d) Show that the length l(xn) for the arithmetic encoding output satisfies

(e) Suppose that Xn i.i.d.∼ X which has PMF P, and we use arithmetic coding with q =
P. Then show that

Compare this to Huffman coding over blocks of length n with respect to compression rate and computational complexity.
(f) Suppose both the encoder and the decoder have a prediction algorithm (say a neural network) that provides probabilities qi(x|xi−1) for all i’s and all x ∈ X. How would you modify the scheme such that you achieve

Thus, if you have a prediction model for your data, you can apply arithmetic coding on it – good prediction translating to high probability, in turn translating to short compressed representations.
4. Entropy Rate.
Consider the Markov process from class taking values in {H,T} with the joint probability distribution given as n
P(X1 = x1,…,Xn = xn) = P(X1 = x1)YP(Xi = xi|Xi−1 = xi−1) i=2
where and for all i > 1.
(a) Directly compute P(X2 = H) and extend that result to show that the process is stationary (we are only looking for the main idea, no need to write a long proof). (b) Compute H(Xn|Xn−1,…,X1) as a function of n and find the limit as n → ∞.
(c) Compute) as a function of n and find the limit as n → ∞. How does this relate to the result in part (b)?
5. Individual Sequences and a Universal Compressor.
Note: Ignore integer constraints on codeword lengths throughout this problem. Notation: h2(p) = −plog2 p − (1 − p)log2(1 − p) (= binary entropy function).
Let xn be a given arbitrary binary sequence, with n0 0’s and n1 1’s (n1 = n−n0). You are also provided a compressor Cq which takes in any arbitrary distribution q on {0,1} as a parameter, and encodes xn using:

bits per symbol where
(a) Given the sequence xn, what binary distribution q(x) will you choose as a parameter to the compressor Cq, so that L¯q(xn) is minimized. Your answer (values of q(0) and q(1)) will be expressible in terms of n, n0 and n1.
(b) When compressing any given individual sequence xn, we also need to store the parameter distribution q(x) (required for decoding). Show that you can represent the optimal parameter distribution q(x) from part (a) using log(n + 1) bits. You can assume that the decoder knows the length of the source sequence n.
(c) Show that the effective compression rate for compressing xn (in bits per source symbol) with the distribution q from part (a) is h2(n1/n) + log(n + 1)/n.
(d) Now suppose that we apply the scheme above to Xn sampled from an i.i.d. Ber(p) distribution. Show that the expected compression rate approaches h2(p) as n → ∞, i.e., the scheme is a universal compressor for i.i.d. sources.
6. Extending to Shannon Codes
For a general source, let
.
Then,
X −n∗u
2 ≤ 1.
u∈U
We want to consider a new source p∗(u) = 2−n∗u. p∗(u) does not sum to 1 over U, but we claim that we can add a finite number of new symbols to extend the source to U∗ ⊇ U such that p∗(u) is dyadic over U∗. Prove this claim.
Hint: How can you reduce this problem to showing that certain rational numbers have a finite binary representation?
7. Decoding LZ77
We encoded a binary sequence using LZ77; we now want to decode the resulting bitstream. We first decode it into the triplets and obtain:
(0, 0, 1) (0, 0, 0) (1, 5, 1) (8, 2, 1)
(a) (b) (c) (d)
Recall that the first entry of the triplet indicates how far back in the sequence you must go to start decoding the phrase; the second entry of the triplet indicates how many elements from that point should be “copied” into your newest phrase entry; and the final entry of the tuple indicates the new element (unseen in the past sequence) that should be added.
Specify how these triplets will now be decoded to reconstruct the original source sequence.