Question

Please help thank you.

This is the Huffman Tree from the previous problem. thank you.

8. For your Huffman Tree above, let X- . number of bits required to encode letter x Make a table and calculate how many bits are required, on average. Answer (rounded to two decimals): E(x) 7. a. Create a Huffman Tree based on these frequeneies: A 20 E 40 0 15 T 25 b. Use the Huffman Tree to encode the word TEEN Answers Encoding

Answer 1

Huffman Algorithm:

For a given sequence of letters.

Step 1:

Count the frequency of occurance for the letters in the sequence.

Step 2:

Sort the frequencies into increasing order.

Step 3:

Build the Huffman coding tree.

a) Choose the two smallest values, make a binary tree with these values.

b) Accumulate the sum of these values.

c) Replace the sum in place of original two smallest values and repeat from step 2.

Step 4:

Making the codes. Traverse tree in top down fashion

a) Assign 0 to the left branch and 1 to the right branch

b) Accumulate 0s and 1s for each character from root to end vertex

c) This is the Huffman code for that character.

Following image contains solution for problem 7.

:, :15, : 20, :25, E:40Arranged in increasing order OC 피 15 20 25 40 20 Oo Binory tree 20 25 40 Sum of two Smallst Value 20 15 s Brocedure Repeate A 40 20 20 25 S IS 6S TTJ 40 1 25 20 65 0 25

Now we will assign 0 and 1 to branches o S ες 40 25 2 Thus codes for the characters are as folows bj is T EEN lo 1o0 Encoding for the word 11 TEEN En Codinglooolioo

Solution for problem 8 is as follows.

Letter Frequncy Codes Number of bits required to encode the letter 20 40 0 1100 1101 10 15 4 25 2 No. ος bits required, on average For every letter 2 frequency X No of bilts Total No-of charace r 20Lot SIS-2S 6o +40 +2060 So 105 230 IOS AnsweY 219 bits on average for every letter