Questions: Arithmetic Coding

Question 1

Why can arithmetic coding achieve rates closer to entropy than Huffman coding, especially for highly skewed distributions?

• A. Arithmetic coding uses a larger alphabet internally
• B. Arithmetic coding effectively assigns fractional bit lengths to symbols — a symbol with probability 0.9 uses only -log2(0.9) ≈ 0.15 bits — while Huffman is limited to integer-length codewords (minimum 1 bit per symbol)
• C. Arithmetic coding compresses each symbol independently with a better algorithm
• D. Huffman coding is not actually prefix-free, causing decoding overhead

Answer: (B)

Huffman coding must assign at least 1 bit per symbol, so for a source with a 0.9-probability symbol (entropy ≈ 0.469 bits/symbol), Huffman wastes ~0.531 bits per symbol. Arithmetic coding encodes the entire sequence as one number, effectively amortizing the cost across many symbols. A symbol with probability 0.9 narrows the interval by a factor of 0.9, costing only -log2(0.9) ≈ 0.152 bits of interval precision. Over long sequences, the average rate approaches entropy to within a negligible rounding overhead.

Question 2

Arithmetic coding can compress a sequence of n symbols from a memoryless source to within 2 bits of nH(X) regardless of the distribution.

• T. True
• F. False

Answer: True

The total compressed length for an arithmetic code on n i.i.d. symbols is between nH(X) and nH(X) + 2 bits (the +2 accounts for specifying a point in the final interval and termination overhead). The per-symbol overhead is at most 2/n bits, which vanishes as n grows. This is a much tighter bound than Huffman's guarantee of H(X) to H(X) + 1 per symbol, and the advantage is especially large for skewed distributions where Huffman's integer constraint causes significant waste.

Question 3

In arithmetic coding, encoding the message 'ABAC' given P(A)=0.6, P(B)=0.3, P(C)=0.1 involves narrowing an interval four times. Explain the process conceptually and why the final interval width equals the probability of the specific message.

Model answer: Start with [0, 1). Partition it according to symbol probabilities: A gets [0, 0.6), B gets [0.6, 0.9), C gets [0.9, 1.0). The first symbol A selects [0, 0.6). Within this interval, re-partition proportionally: A->[0, 0.36), B->[0.36, 0.54), C->[0.54, 0.6). The second symbol B selects [0.36, 0.54). Continue: within [0.36, 0.54), A selects [0.36, 0.468), then C selects [0.462, 0.468). The final interval has width 0.006 = 0.6 * 0.3 * 0.6 * 0.1 = P(ABAC). The compressed message is any binary fraction inside this interval, requiring approximately -log2(0.006) ≈ 7.38, so about 8 bits. The key insight: the interval width equals the sequence probability, so more probable sequences yield wider intervals requiring fewer bits to specify.

This is why arithmetic coding achieves entropy: the number of bits to specify a point in an interval of width w is about -log2(w) = -sum log2(p_i) = sum of self-information values. The total bits used equals the total information content of the specific message.