Arithmetic Coding

Understanding arithmetic coding fundamentals

Arithmetic coding works by iteratively subdividing an interval based on the probability distribution of input symbols. Each symbol progressively narrows the interval, with the final encoded message being any number within the final subinterval.

The encoding process follows these key steps:

1. Initialize the interval [0,1)
2. For each input symbol:
   • Divide the current interval proportionally according to symbol probabilities
   • Select the subinterval corresponding to the current symbol
   • Make this the new working interval

The mathematical representation uses the following formula for interval updates:

\text{new\_low} &= \text{low} + \text{range} \times \text{cumulative\_prob}[i-1] \\ \text{new\_high} &= \text{low} + \text{range} \times \text{cumulative\_prob}[i] \end{align*} $$ Where: - `low` and `high` define the current interval - `range = high - low` - `cumulative_prob[i]` is the cumulative probability up to symbol i <GlossaryCallout /> ## Advantages over Huffman coding While [Huffman coding](/glossary/huffman-coding/) assigns variable-length codes to individual symbols, arithmetic coding can achieve better compression in several scenarios: 1. When symbol probabilities are not powers of 2 2. For adaptive compression where probabilities change 3. When dealing with large alphabets The key advantage comes from arithmetic coding's ability to represent fractional bits per symbol, whereas Huffman coding is limited to whole numbers of bits. <GlossaryCallout /> ## Implementation considerations ### Precision and fixed-point arithmetic In practice, arithmetic coding implementations must deal with finite precision arithmetic. Common approaches include: 1. Fixed-point arithmetic with regular rescaling 2. Integer implementations that maintain precision 3. Early bit output techniques ```python def update_interval(low, high, cumulative_probs, symbol): range = high - low new_high = low + range * cumulative_probs[symbol + 1] new_low = low + range * cumulative_probs[symbol] return new_low, new_high ``` ### Handling underflow Underflow occurs when the interval becomes too small for the available precision. This is typically handled through: 1. Interval rescaling 2. Bit stuffing 3. Deferred bit output The most common approach uses three special cases for rescaling: - E1: when interval is entirely in upper half [0.5, 1.0) - E2: when interval is entirely in lower half [0.0, 0.5) - E3: when interval straddles the middle [0.25, 0.75) ## Applications in time-series compression Arithmetic coding finds important applications in [time-series compression algorithms](/glossary/time-series-compression-algorithms/), particularly for: 1. Compressing high-frequency financial data 2. Sensor telemetry storage 3. Scientific measurements Its efficiency makes it especially valuable for applications requiring both high compression ratios and exact reconstruction. ## Performance characteristics ### Compression efficiency Arithmetic coding can achieve compression rates very close to the theoretical entropy limit: $$ H(X) = -\sum_{i} p(x_i) \log_2 p(x_i) $$ The actual overhead is typically less than 1 bit per message, regardless of message length. ### Computational complexity The time complexity for encoding and decoding is O(n), where n is the message length. However, the constant factors are higher than simpler methods like [Huffman coding](/glossary/huffman-coding/) due to: 1. Multiplication and division operations 2. Precision management 3. Underflow handling ## Modern variants and optimizations Recent developments in arithmetic coding include: 1. Range coding - an integer-based variant 2. Asymmetric Numeral Systems (ANS) - combining speed with compression efficiency 3. Context-adaptive arithmetic coding - using dynamic probability models These variants optimize for different trade-offs between: - Compression ratio - Encoding/decoding speed - Implementation complexity - Memory usage