Arithmetic Coding

Huffman coding assigns an integer number of bits to each symbol, which limits its efficiency when symbol probabilities are not negative powers of 2. Arithmetic coding overcomes this by encoding the entire message as a single fractional number in the interval [0,1), achieving a code length arbitrarily close to the theoretical entropy limit. It is a key topic in GATE and advanced digital communication courses.

Core Concept Explanation

The core idea of arithmetic coding is to represent an entire message as a single real number in the interval [0,1). The interval is subdivided according to the cumulative probabilities of the source symbols. After processing each symbol, the current interval is narrowed to the sub-interval corresponding to that symbol, scaled within the previous interval.

Formally, suppose symbols have probabilities p1, p2, ..., pK with cumulative distribution F(0)=0, F(1)=p1, F(2)=p1+p2, and so on. For the current working interval [L, H), when symbol i is encountered the new interval becomes:

L_new = L + (H - L) * F(i-1) and H_new = L + (H - L) * F(i)

After processing all N symbols, the transmitter sends any binary fraction that lies within the final interval. The decoder, knowing the same probability model, can reconstruct the original symbol sequence exactly by reversing the process.

The encoded output length for a message of N symbols is approximately N * H(S) bits, where H(S) is the source entropy in bits per symbol. This is the Shannon limit, which Huffman coding can only approach when probabilities are inverse powers of 2. Arithmetic coding approaches this limit regardless of the probability values, making it more general.

Mathematical Expression

The theoretical code length for arithmetic coding of a message sequence x1, x2, ..., xN is:

L_code = ceiling( -log2 P(x1,x2,...,xN) ) + 1 bits

where P(x1,...,xN) is the joint probability of the message. For independent symbols, this equals the product of individual probabilities. The overhead is at most 2 extra bits over the true information content of the sequence, which is negligible for long messages. The coding efficiency approaches 100% as N increases.

Practical Understanding

Arithmetic coding is computationally heavier than Huffman coding because interval arithmetic must be maintained with increasing precision as the message grows. In practice, finite-precision arithmetic is used with renormalization steps to prevent underflow. This is the primary engineering challenge in implementing arithmetic coders.

Arithmetic coding is used in modern compression standards including JPEG 2000, JBIG2, and the CABAC entropy coder in H.264 and H.265 video compression. Its ability to assign fractional bit widths to symbols makes it indispensable when symbol probabilities are highly skewed or frequently updated by adaptive models.

The adaptive arithmetic coder updates symbol probabilities dynamically as encoding proceeds, without requiring prior knowledge of source statistics. This makes it suitable for sources with non-stationary statistics, unlike Huffman coding which requires a fixed or pre-scanned probability table.

Given:
Source alphabet: {A, B} with P(A)=0.8, P(B)=0.2
Message to encode: A A B

Why this formula applies:
Arithmetic coding narrows interval per symbol using cumulative probabilities.
Cumulative: F(A)=[0, 0.8), F(B)=[0.8, 1.0)

Formula:
L_new = L + (H-L)*F_low(symbol)
H_new = L + (H-L)*F_high(symbol)

Substitution:
Start: [0, 1)
Symbol A: L=0+(1-0)*0=0, H=0+(1-0)*0.8=0.8  → [0, 0.8)
Symbol A: L=0+(0.8)*0=0, H=0+(0.8)*0.8=0.64  → [0, 0.64)
Symbol B: L=0+(0.64)*0.8=0.512, H=0+(0.64)*1.0=0.64  → [0.512, 0.64)

Calculation:
Final interval [0.512, 0.64), width = 0.128
Transmit any value in this range, e.g. 0.55
Code length = ceiling(-log2(0.8*0.8*0.2)) + 1 = ceiling(-log2(0.128)) + 1 = ceiling(2.966) + 1 = 4 bits

Final Answer:
Code length = 4 bits for message AAB
Entropy bound = 3 * H(S) = 3*(0.8*log2(1/0.8)+0.2*log2(1/0.2)) ≈ 3*0.722 = 2.17 bits
Overhead = 4 - 2.17 = 1.83 bits (bounded by 2 bits as theory predicts)

Exam Tip: Arithmetic coding achieves an average code length between H(S) and H(S)+2 bits for any source, regardless of symbol probabilities. Huffman can exceed H(S) significantly when one symbol has very high probability (close to 1).

Key Properties of Arithmetic Coding

• Encodes entire message as a single real number in [0,1), not symbol by symbol.
• Achieves code length within 2 bits of true entropy for any message length N.
• Interval narrows multiplicatively: final interval width equals joint probability of message.
• Adaptive arithmetic coding updates probabilities on the fly, requiring no pre-scan.
• Practical implementations use integer renormalization to avoid infinite precision arithmetic.
• Used in H.264 CABAC, JPEG 2000, and JBIG2 compression standards.

Quick Revision

• Arithmetic coding maps a message to a subinterval of [0,1) by successive probability-weighted narrowing.
• Code length = ceiling(-log2 P(message)) + 1 bits, at most 2 bits above entropy.
• Interval update: L_new = L + (H-L)*F_low, H_new = L + (H-L)*F_high.
• Superior to Huffman when probabilities are not negative integer powers of 2.
• GATE trap: Huffman is optimal per-symbol; arithmetic coding is optimal per-message.
• Adaptive variant requires no a priori probability table.
• Implementation challenge: finite-precision arithmetic requires renormalization steps.