Text, Bytes and Videotape

Task 2

1. Using A = 1, B = 011, C = 010, D = 001, E = 000 (which is another Huffman coding for the example in Olly's talk) work out what 01101011000011 means (start from the left).



2. Do your own Huffman coding for the probabilities in this example: p(A) = 1/2, p(B) = 1/8, p(C) = 1/8, p(D) = 1/8, p(E) = 1/8. Work through the stages as follows:
   Step 1: put the letter with the least probability of occurring on the left of the letter with the next smallest probability, and bracket them together, adding together their probabilities.
   Step 2: repeat this step as often as necessary, treating bracketed letters as a unit until you have included all the letters.
   Now draw up your Huffman tree from these stages, and then use it to get the coding for each letter. Use the example in Olly's talk as a guide.
   Do you get the coding given in Olly's example, or the coding in no. 1 above?
   If you get a different coding, work out the mean length of a word (ie. the mean length of the symbol string for the letters).



3. Using the same algorithm, find a Huffman coding for these probabilities:
   p(a) = 0.34; p(b) = 0.12; p(c) = 0.05; p(d) = 0.17; p(e) = 0.10; p(f) = 0.16; p(g) = 0.06.
   Read off the code for each letter.
   Calculate the average length of a random letter. How many bits does it take to describe it?
   Make your own coding for the letters (make sure it can be deciphered - ie. write a message using your code, and get someone else to decipher it - it should be quite clear what the message says), and work out the average length for a random letter. Is your method as efficient as the Huffman coding?

Check your answers to this task
Return to Olly's talk

Return to Text, Bytes, and Videotape homepage.