Question

2) A source emits 10, 000 words that are made up of 8 symbols, s1, s2, · · · , s8. In those 10, 000 words, the symbols, s1, s2, · · · , s8, appear 5000, 2500, 1250, 625, 500, 75, 25 and 25 times, respectively. a) (15 points) Determine the optimal binary representations of the 8 symbols using Huffman code. Draw the code tree and represent the symbols in the tree. b) (4 points) Determine the average number of bits used to represent each symbol. c) (1 point) How much saving (in %) does the optimal code give, compared to using 3 bits for each symbol?

Answer 1

(a):

(b):

(c):

Total number of bits used for each symbol is 3.

Total number of words = 10000

So, total number of bits used for all words = 3*10000 = 30000 bits

Total number of bits using Huffman coding = 19550

Saving = 1-(19500/30000) = 1-0.65 = 0.35

So, it means 35% of memory is saved.

Mention in comments if any mistakes or errors are found. Thank you.