Tham khảo tài liệu 'proakis j. (2002) communication systems engineering - solutions manual (299s) episode 8', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 0 2 10 4 0 0 0 __11 1 11. .10 111. .10 111. .11 0 1 0 1 1 The entropy of the source is H X y-1 1 1 log2 2 2 log2 2 1 i 1 n 1 1 1 z 2 i log2 2 2 7 n - 1 log2 2 i 1 n 1 X i aịi i 1 2 n 1 2n 1 In the way that the code is constructed the first codeword 0 has length one the second codeword 10 has length two and so on until the last two codewords which have length n 1. Thus the average codeword length is n 1 Ex 7 V i n 1 p x l x ỵ2ịi 2 1 2 1 1 2 n 1 H X Problem The following figure shows the position of the codewords black filled circles in a binary tree. Although the prefix condition is not violated the code is not optimum in the sense that it uses more bits that is necessary. For example the upper two codewords in the tree 0001 0011 can be substituted by the codewords 000 001 un-filled circles reducing in this way the average codeword length. Similarly codewords 1111 and 1110 can be substituted by codewords 111 and 110. 1 o 1 pcz Z 138 Problem The following figure depicts the design of a ternary Huffman code. 0 .22 10 .18 11 .17 12 .15 20 .13 21 .1 22 .05 The average codeword length is R X 2 p x l x x 0 1 .50 0 1 2 0 1 .28 2 2 .22 2 .18 .17 .15 .13 .10 .05 ternary symbols output For a fair comparison of the average codeword length with the entropy of the source we compute the latter with logarithms in base 3. Hence H X - p x log3 p x x As it is expected H X R X . Problem If D is the size of the code alphabet then the Huffman coding scheme takes D source outputs and it merges them to 1 symbol. Hence we have a decrease of output symbols by D 1. In K steps of the algorithm the decrease of the source outputs is K D 1 . If the number of the source outputs is K D 1 D for some K then we are in a good position since we will be left with D symbols for which we assign the symbols 0 1 . D 1. To meet the above condition with a ternary code the number of the source outputs should be 2K 3. In our case that the number of source outputs
