In this question we investigate Huffman codes for two sets of frequencies. (a) S

Question

In this question we investigate Huffman codes for two sets of frequencies.
(a) Suppose that there are k + 1 symbols s0, s1,.....,sk that appear with frequencies 1,1,2,4,8,....2^k-1 (i.e. powers of two with the first one repeated). In other words, there is a long string of symbols in which s0 appears once and each other si appears 2^i-1 times. Derive a Huffman code for these symbols.
(b) Determine the average length of a codeword for your code in (a). (I.e. what is the average number of bits used to represent a symbol.)
(c) Suppose that there are k + 1 symbols s0, s1,.....,sk that appear with frequencies f0, f1, f2,...., fk where f0 = 1, f1 = 1, and fi = f(i-1) + f(i-2) for i > 1 (i.e. the Fibonacci numbers). Derive a Huffman code for these symbols.

Explanation / Answer

a) The symbol which have higher frequencies should be alloted less number of bits in Huffman coding. The symbol which have lower frequecies should be alloted more number of bits in Huffman coding.

So, sk has Huffman encoding = 0

s(k-1) has Huffman encoding = 10

s(k-2) has Huffman encoding = 110

.

.

s1 has Huffman encoding = 111...11110 (1 is repeated k-1 times)

s0 has Huffman encoding = 111...11111 (1 is repeated k times)

b) Average length of a codeword = 1.k + 1.k + 2.(k-1) + 4.(k-2) + .... + 2^(k-1).1

= 2^(k-1) - 2

c) It is same as part (a). Higher frequency symbols will be alloted lesser number of bits and lower frequency symbols will be alloted higher number of bits in Huffman encoding.

The same encoding can be used as done in part (a) as the frequency pattern in similar in both cases.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.