No.5 - Arithmetic Coding and Huffman Coding are two popular lossless compression methods. (a) What are the advantages and disadvantages of Arithmetic Coding as compared to Huffman Coding? Answer: The main advantage of Arithmetic Coding over Huffman Coding is that whereas the minimum code length for a symbol in Huffman Coding is 1, since we create a binary tree with 0 or 1 attached to each branch, in Arithmetic Coding the number of bits per symbol can be fractional. But Arithmetic Coding has a subtle implementation difficulty. When the intervals shrink, we need to use very high-precision numbers to do encoding. This makes practical implementation of this algorithm infeasible. (b) Suppose the alphabet is [A; B; C], and the known probability distribution is P A =0.5; P B =0.4; P C =0.1. For simplicity, let’s also assume that both encoder and decoder know that the length of the messages is always 3, so there is no need for a terminator. i. How many bits are needed to encode the message BBB by Huffman coding? Answer: 6 bits. Huffman Code: A - 0, B - 10, C - 11; or A - 1, B - 00, C - 01. i i. How many bits are needed to encode the message BBB by arithmetic coding? Answer: s y m b o l l o w h i g h r a n g e 0 1 1 B 0 . 5 0 . 9 0 . 4 B 0 . 7 0 . 8 6 0 . 1 6 B 0 . 7 8 0 . 84 4 0 . 06 4 4 bits. Binary codeword is 0.1101, which is 0.8125.