a2 .4 a1 .2 a5 .1 Given Rearrange (VLC) Huffman Tree (Page 3.5) a3 .2 Rearrange a4 .1 Ex. 3.2.1 (Fig. 3.2 / p.46) a5 .1 Average bit size = [2 * 0.2 + 1 * 0.4 + 3 * 0.2 + 2 * 4 * 0.1] = 2.2 bits/symbol 5 5 P(ai) = 1; H = - P(ai) log2 P(ai) = 2.122 bits/symbol = Entropy i=1 i=1 Redundancy = 2.2 2.122 = 0.078 bit/symbol – Minimum Variance Huffman Tree code MVHC Rearrange p.3-7a a2 00 a1 10 a1 10 a2 00 a3 11 a3 11 a4 010 a4 010 a5 011 a5 011 Average bit rate 2.2 bits/symbol. Assume 10,000 symbols/sec channel 22,0000 bps. MVHC makes buffer design easier Minimum variance Huffman Code. Optimality of Huffman Codes. (VLC) H(s) = - Pi log2 Pi i Length of Huffman Codes: H(s) < H(s) + 1, (3.1) ≤ l l = Avg. code length for Huffman code
a5 .1 Given Rearrange (VLC) Huffman Tree (Page 3.5) Rearrange a2 .4 a1 .2 a3 .2 a4 .1 a5 .1 Ex. 3.2.1 (Fig. 3.2 / p.46) Average bit size = [2 * 0.2 + 1 * 0.4 + 3 * 0.2 + 2 * 4 * 0.1] = 2.2 bits/symbol 5 5 P(ai) = 1; H = Entropy = - P(ai) log2 P(ai) = 2.122 bits/symbol i=1 i=1 Redundancy = 2.2 – 2.122 = 0.078 bit/symbol Minimum Variance Huffman Tree code MVHC Rearrange a2 00 a1 10 a3 11 a4 010 a5 011 a1 10 a2 00 a3 11 a4 010 a5 011 p.3-7a Average bit rate 2.2 bits/symbol. Assume 10,000 symbols/sec channel 22,0000 bps. MVHC makes buffer design easier Minimum variance Huffman Code. Optimality of Huffman Codes. (VLC) H(s) = - Pi log2 Pi i Length of Huffman Codes: H(s) ≤ l < H(s) + 1, (3.1) l = Avg. code length for Huffman code