Variable-Size Codes

Variable-Size Codes
Consider the four-symbol a1, a2, a3, and a4. If they appear in our data strings with equal probabilities (= 0.25), then the entropy of the data is ?4(0.25 log2 0.25) = 2. Two is the smallest number of bits needed, on the average, to represent each symbol in this case. We can simply assign our symbols the four 2-bit codes 00, 01, 10, and 11. Since the probabilities are equal, the redundancy is zero and the data cannot be compressed below 2 bits/symbol. Next, consider the case where the four symbols occur with different probabilities as shown in Table 1, where a1 appears in the data (on average) about half the time, a2 and a3 have equal probabilities, and a4 is rare. In this case, the data has entropy ?(0.49 log2 0.49+0.25 log2 0.25+0.25 log2 0.25+0.01 log2 0.01) ? ?(?0.050?0.5?0.5? 0.066) = 1.57. The smallest number of bits needed, on average, to represent each symbol has dropped to 1.57.




Symbol Prob. Code1 Code2
a1 .49 1 1
a2 .25 01 01
a3 .25 010 000
a4 .01 001 001

Table 1: Variable-Size Codes.

If we again assign our symbols the four 2-bit codes 00, 01, 10, and 11, the redundancy would be R = -1.57 + log24 = 0.43. This suggests assigning variable-size codes to the symbols. Code1 of Table is designed such that the most common symbol, a1, is assigned the shortest code. When long data strings are transmitted using Code1, the average size (the number of bits per symbol) is 1 * 0.49 + 2 * 0.25 + 3 * 0.25 + 3 * 0.01 = 1.77, which is very close to the minimum. The redundancy in this case is R = 1.77 -1.57 = 0.2 bits per symbol. An interesting example is the 20-symbol string a1a3a2a1a3a3a4a2a1a1a2a2a1a1a3a1a1a2a3a1, where the four symbols occur with (approximately) the right frequencies. Encoding this string with Code1 yields the 37 bits: