University Homepage School Homepage School Contacts School Search

Lecture 2, Friday w1, 2014-09-19

Main lecture points:

• We cannot compress all files. So we choose to shrink the probable ones.
• Use a model to describe what’s probable. For now, the model is fixed, assumed known.
• Simplest model: string of independent Bernoulli bits.
• Binomial: how many bits are on (k = ∑ _nx_n) in a length-N bit-string?
• Take logs of large/tiny positive numbers if using floating point doubles.
• Block coding idea.

Check your progress

Things you should be able to do and answer after reviewing the lecture:

• Sketch the binomial distribution for various N and p.
• Explain what the majority of binary strings of length N are like, using the sketch for p = 0. 5.
• What is the most probable binary string of length N from an independent Bernoulli model with p < 0. 5?
• What is a typical string of length N like, assuming an independent Bernoulli model with p < 0. 5?
• How can it be that a ‘typical’ string is so much less probable than the most probable string?
• Compute binomial probabilities for large N and k.
• Understand idea of splitting list of all possible files, sorted by probability into two. Give most probable items a short code, and less probable items a longer one.

Recommended reading

We have now covered most of the material in the ‘week 1’ slides (I didn’t quite finish, but will next time). Ask on NB if anything is unclear, or too compressed.

Make sure you have done the maths background reading from the last lecture.

For keen people

Being able to quickly compute and plot things is a useful research skill. Last time I suggested reproducing a plot of repetition code properties. This time you could try reproducing plots showing binomial distributions and the performance of block codes. It’s possible you’d hit numerical or other problems, which I’d be happy to help with.

---

This page maintained by Iain Murray.
Last updated: 2014/09/19 14:19:23