## exam198

Previewing page
*1*
of
actual document.

**View the full content.**View Full Document

## exam198

0 0 62 views

- Pages:
- 3
- School:
- Washington University in St. Louis
- Course:
- Ese 523 - Information Theory

**Unformatted text preview:**

EE 553 Exam 1 Professor Joseph A O Sullivan March 27 1998 This is a closed book closed notes exam It is scheduled to last for 1 5 hours All students must do their own work and are bound by the SEAS honor code If you do not undertand a question clearly state the assumptions used in trying to nd a solution NAME Potentially useful stu X1 k 0 X1 k k 0 k k 1 1 j j 1 1 1 1 2 j j 1 1 2 1 20 points Suppose that a channel has binary inputs X and binary outputs Y Suppose that the transition probabilities are P Y 1jX 1 0 8 P Y 0jX 1 0 2 P Y 1jX 0 0 1 P Y 0jX 0 0 9 Find the capacity of this channel 1 3 4 2 20 points Suppose that X is a geometric random variable so the probability that X k is given by PX k 1 k k 0 5 where 0 1 a Find the entropy of X b Describe the typical set Make sure that you convince me that you understand what the typical set looks like for this problem c On average how many bits does it take to represent n i i d random variables X1 X2 X d Would it be a good idea to use a Hu man code for data compression for a random variable X Explain your answer n 3 15 points Let X be a nite set and suppose that three probability distributions p x q x and r x are de ned on X Let 0 1 We will look at a few relative entropies and entropies D1 D2 D3 D4 D5 H1 H2 H3 D pjjr D qjjr D p 1 D p 1 D q 1 H p H q H p 1 qjjr rjjr rjjr q 6 7 8 9 10 11 12 13 Determine whether each of the following statements is true false or whether there is insu cient information undetermined to decide the truth of the statement Do not guess as wrong answers will be penalized Statement D3 D1 1 D2 D4 D1 D5 D1 D4 D5 D1 D2 H3 H1 1 H2 H1 D1 True False Undetermined 2 4 15 points Suppose that X f0 1 2g and that p 0 1 1 16 1 32 p 1 1 16 and p 2 1 32 a Describe a Hu man code for the random variable X b Find a Shannon code for the random variable X c Compare the two codes from parts a and b d Now suppose you were asked to nd a data compression code for 20 i i d copies of X That is the code should be de ned for the random vector X20 X1X2 X20 14 What coding scheme would you use and why Analyze the complexity of de ning a Hu man code for X20 Approximately what would be the expected length of the code for your coding scheme 5 15 Points a What is universal data compression and how does it relate to Kolmogorov complexity b Determine a good upper bound on the Kolmogorov complexity of the following data model X X1 X2 X and each X is binary Every vector X can be partitioned into subsets of strings For example X 111001111100001000 15 consists of six strings these being n n n i n 111 00 11111 0000 1 000 16 17 The model for the data consists of specifying whether the rst bit is 1 or 0 specifying the number of strings and specifying the lengths of the strings For what kind of data is this a good model For what kind of data is this a bad model Does this work well as a model for algorithmically random sequences Note that this model is essentially that used in fax machines 3

View Full Document