HW6 – Introduction to Information Theory

Description

1. Consider the probability distribution p(x; y) for x; y 2 f0; 1g:

• 9

p(x; y) =	>	1=6;	x = 0; y = 0;	>	(1)
		0;	x = 1; y = 0;
	>	1=6;	x = 0; y = 1;	>
	<			=
	>	2=3;	x = 1; y = 1	>
	>			>
	:			;

Find

1. 1. H(X), H(Y ),

1. 2. H(XjY ), H(Y jX),

1. 3. H(X; Y ),

1. 4. I(X; Y ).

2. Show that the following expressions hold. X; Y; Z are jointly distributed random variables.

2. 1. H(X; Y jZ) H(XjZ),

2. 2. I(X; Y ; Z) I(X; Z),

(c) H(X; Y; Z) H(X; Y ) H(X; Z) H(X),

(d) I(X; ZjY ) I(Z; Y jX) I(Z; Y ) + I(X; Z).

3. Assume that we have four symbols, namely a; b; c; d. These symbols are mapped to codewords of

10; 00; 11; 110, respectively.

1. Does the given code have the pre x property?

2. Is this a uniquely decodable code? Prove it.

4. The probability distributions p(x) and q(x) are de ned on the same random variable X with 5 outcomes, f1; 2; 3; 4; 5g. C₁(x) and C₂(x) are two di erent codes on X:

Symbol	p(x)	q(x)	C1(x)	C2(x)
1	1/2	1/2	0	0
2	1/4	1/8	10	100
3	1/8	1/8	110	101
4	1/16	1/8	1110	110
5	1/16	1/8	1111	111

1. 1. Find H(p); H(q); D(pjjq) and D(qjjp).

1. 2. Prove the optimality of C₁ and C₂ on X under p and q, respectively.

1. 3. We decide to use C₂ when the distribution is p. Find the average codeword length. Find its di erence to the entropy of p.

1. 4. We decide to use C₁ when the distribution is q. Find the average codeword length. How much do we lose due to miscoding?

5. For each of the following codes, nd a probability assignment that results in Hu man coding. If there is no such a probability assignment, explain why.

5. 1. f0,10,11g

5. 2. f00,01,10,110g

5. 3. f01,10g.

5. Consider the probability distribution on X with 8 outcomes:

p(X = 1) = p(X = 2) = 2p(X = 3) = 2p(X = 4) = 4p(X = 5) = 4(X = 6) = 4p(X = 7) = 4p(X = 8).

5. 1. Give the Hu man binary code.

5. 2. Find the expected code length of a) and H(X).

5. 3. Find the Hu man 3-ary code.

R

7. For each of the following, nd the di erential entropy, h(X) = f ln f.

1. 1. f(x) = e ^x for nonnegative x.

1. 2. f(x) = 1=2 e ^jxj for real x.

1. 3. f(x) where, X = X₁ + X₂ where X₁ and X₂ are independent with f(x_i) = N( _i; _i²), i = 1; 2.

8. Consider the channel transition matrix, Q:

Q =		1=2	1=2		(2)
		1	0
where Q(i; j) gives the probability of receiving yj			if xi	is transmitted.	Assume x1 = y1 = 0 and
x2 = y2 = 1.

1. Draw the channel model with the transmitted bits on the left side, the received bits on the right side and the transition probabilities connecting them. What is the name of this channel?

2. Find the capacity of this channel.

3. Find the input distribution that achieves the capacity.

3