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 be the strongly typical set for p(.).
(a) Let be the smallest set of length-n sequences from the source, such that probability of is at least . Obtain bounds on the ratio of the sizes of and .
(b) Let be any set of length-n sequences from the source, such that probability of is at least . Can you still obtain some bound on the ratio of the sizes of and ?
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 = 2m − m − 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.