COMP 150 MDC - Fall 2016 - Homework 5

Due Thursday, 20 October, 2016 in class

Report problems to ablumer via email

  1. (This is a modified version of Problem 2 from Chapter 8.) A source produces independent random bits with P(0) = 0.8. Blocks of M bits are compressed by counting the number of zeroes in a block and sending a zero if half or more are zeroes, sending a one if more than half are ones. The receiver decodes a zero as a block of zeroes and a one as a block of ones. The per-bit distortion is the number of errors divided by the length of the block. Compute the rate and distortion for the cases M = 1, 2, 4, and 8 and compare to the rate-distortion function given by Formula (68) on page 238.
  2. In most cases this scheme doesn't achieve the performance promised by the rate-distortion function. How much improvement would you get if you could noiselessly compress the output of the encoder at the rate given by the entropy of the output?
  3. An alternative is to use a more complex encoder. For example, rate 1/2 can be achived by sending a block of four bits using two bits rather than sending a block of two bits using a single bit. See what you can do at least for the 4 -> 2 case.
  4. Prove Formula (97) on page 244, giving Rxx(k), the autocorrelation function of an AR(1) source.