Read sections 7.1-7.6 in chapter 7 of the textbook Explorations in Computing and chapter 3 of Blown To Bits.
The barcode reader calculates the check digit using the following algorithm:
- Add the first, third, fifth, seventh, ninth and eleventh digits of the UPC barcode and store this result in x.
- Add the second, fourth, sixth, eighth and tenth digits of the UPC barcode and store this result in y.
- Set z equal to the last digit of the value 3x + y.
- If z is not equal to 0, then set check_digit equal to 10 - z. Otherwise, set check_digit equal to z.
Do the following:
78013713559_
Once you decode the word, you can use RubyLabs to check your answer:
>> include BitLab => Object >> f = read_frequencies(:hafreq) => {"K"=>0.106, "W"=>0.009, "L"=>0.044, ... } >> tree = build_tree(f) => { 1.000 { 0.428 { 0.195 { ... } } } } >> hc = assign_codes(tree) => {"K"=>001, "W"=>110010, "A"=>10, ... } >> encode(INSERT_YOUR_ANSWER_HERE, tree) => 0001011000111110000100110
See sections 7.4 and 7.5 for more information on how to build a Huffman tree, and how to encode and decode messages using RubyLabs.
(NOTE: Be sure you understand what each of the steps are doing above. Read through the relevant sections for a thorough explanation and try out the tutorial in the textbook for yourself.)
A 0000 U 0100 L 1000 W 1100 E 0001 ' 0101 M 1001 I 0010 H 0110 N 1010 O 0011 K 0111 P 1011
Go to Popular Hawaiian Words and Phrases and scroll down to the vocabulary list at the end. Find a word that would be longer if encoded with the Huffman tree than with the 4-bit fixed-width code above. (Hint: look at words that use lots of low-frequency letters.) Give the encoding using the Huffman tree and the 4-bit fixed-width code above to justify your answer.