Solutions to Test 2

Problem No. 1

(a)

	                                                                                                   Huffman
{A}     P(A) 		Code                                                                       

  4	0.4

  3		0.3

  2		0.2

	1	0.05

	0	0.05



(b)

Yes, the Huffman code above is an example of an optimal prefix code.  We can 
construct a non-prefix code that has a shorter expected codeword length by 
modifying the longest two codewords as follows:

{A}     Codewords
 	4	1
	3	00
	2	010
	1	011
	0	101

(c)


  = length of ith codeword

The average cost of X is

which is what we would like to minimize.

We let 

      forms a probability distribution.








Since the only freedom is in the choice of , we can minimize C by choosing 





Therefore, the minimum cost C* for the assignment of codewords is
		C* = Q H(q)

We con construct a Huffman code with minimum expected cost by using 
distribution q instead of distribution p.

Problem No. 2

(a)



equally holds when the input distribution is uniform.  The value of  p  that
minimizes the capacity of the channel is p = 1/2.

C = 1 - 1 = 0

(b)

The transistion probability matrix for a single binary sysmetric channel is



	???????



Problem No. 3

(a)




(b)







This answer agrees with the scaling theorem.

Scaling Theorem:  h(aX) = h(X) + log|a|
                                     = 1 + log2 = 1.693


(c)





The answer agrees with the translation theorem.  Part c is a translation of part a.

Translation Theorem:  h(X+c) = h(X)
Translation does not change the differential entropy.

(d)