COMP 150 MDC - Fall 2016 - Homework 5
Due Thursday, 20 October, 2016 in class
Report problems to ablumer via email
- (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.
- 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?
- 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.
- Prove Formula (97) on page 244, giving Rxx(k), the autocorrelation
function of an AR(1) source.