Huffman coding reduces the average number of bits$/$message by using shorter codewords for

more frequently$-$occurring messages, and longer codewords for less frequently$-$occurring messages.

In this assignment you will apply probability and information theory to data compression.

Assume a source sends five messages, selected independently of each other, with the following

probabilities:

$P(M_1)=0\mathrm{.}5$

$P(M_2)=0\mathrm{.}2$

$P(M_3)=0\mathrm{.}1$

$P(M_4)=0\mathrm{.}1$

$P(M_5)=0\mathrm{.}1$

Answer these questions and show all of your work:

What is the information content of message $M_1,$ in bits?

What is the information content of message $M_2,$ in bits?

What is the information content of message $M_3,$ in bits?

What is the information content of message $M_4,$ in bits?

What is the information content of message $M_5,$ in bits?

What is the average number of information bits per message $($entropy of the source$)?$

How many codebits per message are required when encoding each message using the shortest$-$

possible fixed$-$length binary code?

What is the average number of codebits per message resulting from using a Huffman code

to assign one variable$-$length codeword per message?

What is the average number of codebits per message resulting from using a Huffman code

to assign one variable$-$length codeword per message pair?

note from student: please fully sketch the Huffman trees for $8$ & $9$