COMP2610/COMP6261 – Information Theory Tutorial 8: Source Coding
Young Lee and
Tutors: and
Week 10 (9th – 13th Oct), Semester 2, 2017 1. Optimal Coding and
Copyright By PowCoder代写 加微信 powcoder
Consider the ensemble X with probabilities PX = p = {1, 1, 31 , 1 } and the code C = {0,11,100,101}. 2 4 128 128
(a) What is the entropy H(X)?
(b) What is the expected length L(C, X )? Is C an optimal code for X ?
(c) What are the code lengths for X? Construct a prefix Shannon code CS for X. Compute the expected code length L(CS , X ).
(d) What are the probabilities q = {q1, q2, q3, q4} for the code lengths of C?
(e) Compute the relative entropy D(p∥q). What do you notice about D(p∥q), H(X), L(C,X), and
(f) Construct a Huffman code CH for X. How does its code lengths compare to C and CS? How do their
expected code lengths compare?
2. Binary Representations
Express the following numbers in binary.
(a) 4.2510 (b) 8.110
3. Shannon-Fano-
Let X be an ensemble with alphabet AX = {x1, x2, x3, x4} and probabilities pX = (0.25, 0.5, 0.125, 0.125).
(a) Compute the cumulative distribution function F(xi) for each symbol xi.
(b) Computethesymbolintervals[F(xi−1),F(xi))foreachsymbolxi.(Recallthatweassumeforconvenience
that F (x0) = 0.)
(c) Compute the modified cumulative distribution function F ̄(xi) for each symbol xi.
(d) Compute the Shannon-Fano-Elias codewords for each symbol xi.
(e) Decode the string 10001.
(f) Suppose you only use the first ⌈log 1 ⌉ bits to code the above ensemble. Will the result be a prefix code? p(x)
4. Arithmetic Coding
(a) For the same ensemble as the previous section, compute an arithmetic code for the sequence c. Assume here that d = P, i.e. that the symbol d denotes the end of stream. Assume also that at each iteration, the probability of the various outcomes is unchanged.
(b) Compute an arithmetic code for the sequence ca, with the same setup as the previous part. Does the codeword for ca start with that for c?
(c) Compute an arithmetic code for the sequence ca using adaptive probabilities, assuming an initial set of virtual counts m = (1, 1, 1) and a constant end-of-stream probability p(d) = 0.25.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com