Homework 3

Q1. (Polytime rate-distortion codes) (a) For binary Bernoulli(p) sources with Hamming distortion, can you think of a scheme that achieves rate H(p-D) for distortion D? How does this compare with the rate-distortion function? What is the time-complexity of your scheme?

(b) (Open-ended hard question -- feel free to discuss amongst yourselves) Suppose one used (roughly) concatenated coding ideas. Can you think of a scheme that achieves better rate-distortion performance (perhaps even attaining the rate-distortion function!), and yet has polynomial-time complexity? For any scheme you propose, obtain bounds on the expected distortion and running time. (Hint: Only use "short" optimal random inner codes, no outer code)

Q2. ("Pythagorean property" of K-L divergence) Examine Theorem 11.6.1 and its proof in Cover and Thomas, understand it, and rederive it without looking once you're comfortable with it (be honest now :) Why is it called the Pythagorean property?

Q3. (Properties of rate-distortion functions) Problems 10.6, 10.12, 10.15.

Q4. (A taste of multi-user information theory) A polyglot wishes to write a message on a piece of paper to simultaneously communicate with a person who only reads English, and also with a person who only reads Hindi. Suppose there is enough space on the paper for exactly n words (regardless of which language). Say each word carries 20 bits of information (again, regardless of language). Derive a region of achievable "rate-pairs" (i.e., the set of all triples of numbers such that the English reader can receive information at rate and the Hindi reader can simultaneously receive information at rate , and both receive a common message at rate ). (Hint: Placement of the words matter)