| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Homework 2

Page history last edited by sidjaggi 15 years ago

Q1. (Cost of source mismatch for source coding) If the true underlying distribution of a discrete source is p(.), but the source is encoded using a Huffman code for a (different) distribution q(.), obtain bounds on the expected code-length L'. By how much can L' differ from the optimal expected average encoding length L (if the source were indeed encoded using p(.))?

 

Q2. (Weighted coding) Q. 5.20 from Cover and Thomas.

 

Q3. (Group testing) Of a group of 12 balls, one has a different weight than the other 11 (all of which have the same weight). You can use a scale to weigh any two groups of balls with each other. What is the minimum number of weighings you need to determine the "different" ball? (Note that it might be either heavier or lighter.) (This is a special case of the general  problem of group testing, about which there are many interesting open problems.)

 

Q4. (Sizes of high probability sets) Let X be an i.i.d. source with pmf p(.). Let Formula be the strongly typical set for p(.).

(a) Let Formula be the smallest set of length-n sequences from the source, such that probability of Formula is at least Formula. Obtain bounds on the ratio of the sizes of Formula and Formula.

(b) Let Formula be any set of length-n sequences from the source, such that probability of Formula is at least Formula. Can you still obtain some bound on the ratio of the sizes of Formula and Formula?

 

 

Q5. (Maximum entropy processes) Look up Burg's maximum entropy theorem (Chap 12.6 in Cover and Thomas). Use this to solve Problem 12.3.

 

Q6. (Hamming codes for n a power of 2) Prove that for any integer m, there exists a Hamming code with n = 2m − 1, k = 2mm − 1, d =3. (Look here for the construction).

 

Q7. (Concatenated codes for BECs) Open-ended question -- what's the best rate you can achieve using concatenated coding ideas for the Binary Erasure Channel?

 

Q8. (Quantized AWGN channels) Suppose we convert a given AWGN channel with noise power N into a BSC. That is, each channel input is only allowed to be at power level +P or -P, and before decoding the receiver quantizes the received signal to the nearest of +P and -P. Write down the expression for the loss of capacity (as a difference from the true capacity) due to this coding choice. Numerically obtain a semi-log plot of this loss for P/N varying from 0.1 to 10.

Comments (2)

Tong said

at 6:24 pm on Mar 25, 2009

in q4 what is the definition of "the smallest set"? it just has a lower bound, or it has both lower and upper bound ?

sidjaggi said

at 6:52 pm on Mar 25, 2009

smallest set means, literally, the set with the smallest number of elements.

You don't have permission to comment on this page.