Extra Problems for Chapter 13

T.M. Cover and J.A. Thomas

1. Rate distortion. Find and verify the rate distortion function R(D) for X uniform on and

   

   where is defined on .

   (You may wish to use the Shannon lower bound in your argument.)

2. Lower bound

   Let

   

   and

   

   Define over all densities such that . Let R(D) be the rate distortion function for X with the above density and with distortion criterion Show .

3. Adding a column to the distortion matrix. Let R(D) be the rate distortion function for an i.i.d. process with probability mass function p(x) and distortion function , , . Now suppose that we add a new reproduction symbol to with associated distortion , . Does this increase or decrease R(D) and why?
4. Simplification. Suppose , , , i = 1,2,3,4, and are i.i.d. . The distortion matrix is given by

   

   1. Find R(0), the rate necessary to describe the process with zero distortion.
   2. Find the rate distortion function R(D). There are some irrelevant distinctions in alphabets and , which allow the problem to be collapsed.
   3. Suppose we have a nonuniform distribution , i=1,2,3,4. What is R(D)?
5. Rate distortion for two independent sources. Can one simultaneously compress two independent sources better than by compressing the sources individually? The following problem addresses this question. Let be iid with distortion and rate distortion function . Similarly, let be iid with distortion and rate distortion function .

   Suppose we now wish to describe the process subject to distortions and . Thus a rate is sufficient, where

   

   Now suppose the process and the process are independent of each other.

   1. Show

      

   2. Does equality hold?

   Now answer the question.

6. Distortion-rate function. Let

   

   be the distortion rate function.

   1. Is D(R) increasing or decreasing in R?
   2. Is D(R) convex or concave in R?
   3. Converse for distortion rate functions: We now wish to prove the converse by focusing on D(R). Let be i.i.d. . Suppose one is given a rate distortion code , with . And suppose that the resulting distortion is . We must show that . Give reasons for the following steps in the proof:

      

7. The Source-Channel Separation Theorem with Distortion:  Let be a finite alphabet i.i.d. source which is encoded as a sequence of n input symbols of a discrete memoryless channel. The output of the channel is mapped onto the reconstruction alphabet . Let be the average distortion achieved by this combined source and channel coding scheme.

   

   1. Show that if C > R(D), where R(D) is the rate distortion function for V, then it is possible to find encoders and decoders that achieve a average distortion arbitrarily close to D.
   2. (Converse.) Show that if the average distortion is equal to D, then the capacity of the channel C must be greater than R(D).

Latex file

Postscript file