Variable length coding; entropy and fixed code efficiency

Significance of variable length coding

In variable-length coding, frequent symbols get short code words and rare symbols get long code words. Its significance:

• The average length $\bar L = \sum p_i l_i$ becomes smaller than a fixed-length code and can approach the entropy $H$, so bit rate, bandwidth and storage are reduced.
• It uses the source statistics; when probabilities are unequal, fixed-length codes waste bits.
• Prefix (instantaneous) variable-length codes such as Huffman and Shannon–Fano remain uniquely decodable.

Example: four symbols with $p = 0.5, 0.25, 0.125, 0.125$. Fixed code: 2 bits each, $\bar L = 2$. Variable code 0, 10, 110, 111: $\bar L = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75$ bits = $H$, so efficiency rises from 87.5 % to 100 %. (Morse code uses the same idea: "E" is a single dot.)

Numerical

Probabilities $\{0.2, 0.15, 0.25, 0.05, 0.3, 0.05\}$ (sum = 1).

Entropy:

$$H = 2.3282\ \text{bits/symbol}$$

Fixed-length code: 6 symbols need $\lceil\log_2 6\rceil = 3$ bits each, so $\bar L = 3$ bits/symbol.

Maximum code efficiency of this fixed-length encoder:

$$\eta_{max} = \frac{H}{\bar L} = \frac{2.3282}{3} = 0.7761 = 77.61\%$$

(Redundancy = 22.39 %.) A variable-length code, e.g. Huffman with $\bar L = 2.35$ bits, would raise the efficiency to $2.3282/2.35 = 99.07\%$.

(If "maximum efficiency" is read instead as the source efficiency relative to the maximum entropy $H_{max} = \log_2 6 = 2.585$ bits/symbol, it is $2.3282/2.585 = 90.07\%$.)

Answer: $H = 2.3282$ bits/symbol; maximum efficiency of the fixed-length code = 77.61 %.