Variable length coding exercises

First of all, read my Information Theory Notes.  These exercises are similar to, but not exactly the same as the 3 exercises at the end of the Notes.

You'll be writing your answers into the Comments-to-Teacher.

For each of the exercises below, I'll be asking you to provide:

a) The Shannon entopy which is equal to the minimum average number of bits required to send the results of a single flip of the type of coin in the question.

b) The coding itself that you've come up with (see example below)

c) The average number of bits required by your coding scheme.

Note:  You do not have to automatically think that grouping is necessary to reduce the number of bits.  Sometimes, just using variable-length encoding of a single result is pretty good.

Example from class: come up with a better-than-the-trivial coding scheme for a two-sided weighted coin whose probabilities are: H: 0.75, T: 0.25


a) Shannon entropy is ~0.811

b) use a grouping of 2 coins:  HH: 0,  HT: 10,  TH: 100,  TT: 101

c) that coding average is ~0.844


Ex. 2: You have a 3-sided coin, with sides H (heads), T (tails), and M (midriffs).  M has prob. 0.5, and the other two have 0.25 each. 

Ex. 1: You have a 2-sided coin, with probabilities H: 0.75, T: 0.25, and you'll use a group of 3 results at a time, instead of the 2 we used in class.

Ex. 3: You have a 5-sided coin with equal probabilities.