3.3.2 Entropy Coding
Entropy coding exploits unequal symbol probabilities by assigning variable-length codewords (VLCs). Using fixed-length PCM codewords of two bits per symbol yields an average of 2 bits per message. By assigning shorter codewords to common messages and longer codewords to rare ones, as in Figure 3.10, the average code length becomes:
representing a compression gain of approximately 7.5%. When applied to sources such as English text, where probability disparities are more pronounced, entropy coding typically yields reductions of around 50%.
For correct decoding, variable-length codes must be prefix-free—no valid codeword may form the prefix of another. This principle is reminiscent of Morse code, where common letters (such as E and T) are assigned short symbols and rare letters (Q and Z) receive longer ones.
The process of generating the variable-length codewords for each message is called entropy coding. Two principal forms of entropy coding are widely used:
- Huffman coding, in which each symbol is mapped to a discrete, prefix-free binary codeword.
- Arithmetic coding, which represents an entire message sequence as a single codeword and can assign fractional bits per symbol on average.
Huffman coding produces an optimal set of prefix-free codewords in the sense that no other discrete symbol-by-symbol representation yields a shorter average length. For example, in the sampled voice signal of Figure 3.11(a) , the sample probabilities shown in Figure 3.11(b) yield an entropy of 2.25 bits/sample. The Huffman code set in Figure 3.12 produces an average code length of 2.28 bits/sample—very close to the theoretical limit.
Arithmetic coding achieves even higher efficiency by avoiding the restriction that each symbol must be assigned an integer number of bits. Instead of encoding symbols individually, arithmetic coding represents an entire message as a sub-interval of the real number line between 0 and 1. As symbols are processed, this interval is progressively refined according to their probabilities. In the limit of long sequences, the average number of bits required per symbol can approach the source entropy arbitrarily closely, allowing arithmetic coding to match the entropy bound exactly.
In practice, arithmetic coding is computationally more complex than Huffman coding and is more sensitive to bit errors, since a single error can affect the decoding of all subsequent symbols. Despite this, its superior compression efficiency has made arithmetic coding the preferred entropy-coding method in many modern standards, including JPEG2000, H.264/AVC, HEVC (H.265), AV1, and advanced text-compression systems. In all cases, however, the mean number of bits per symbol cannot fall below the entropy bound established by Shannon.
Natural sources often exhibit significant correlation between successive symbols or samples. Predictive and transform coding techniques exploit this correlation to reduce redundancy before entropy coding is applied, thereby lowering the effective entropy of the signal and enabling further compression.
Back to reading