Arithmetic Coding

Arithmetic Coding

Arithmetic coding is a method of entropy encoding used in lossless data compression. It is designed to encode a sequence of data symbols into a single fractional number, rather than assigning a discrete binary code to each individual symbol. By representing an entire message as a real number within the mathematical interval between 0.0 and 1.0, arithmetic coding can achieve a compression ratio that closely approaches the theoretical lower bound established by Claude Shannon, known as the Shannon entropy established the theoretical limits of data compression^[1].^[27] This continuous mapping allows the algorithm to allocate fractional bits to symbols, avoiding the inefficiencies inherent in prefix codes when symbol probabilities are not exact powers of one half eliminates the quantization waste inherent in discrete prefix codes^[2].

The primary problem arithmetic coding solves is the quantization overhead found in Huffman coding A Method for the Construction of Minimum-Redundancy Codes^[3]. In a Huffman tree, every symbol must be represented by a whole number of bits. If a specific character appears in a dataset with a probability of 90 percent, the optimal information content of that character is approximately 0.15 bits. Huffman coding is forced to assign a minimum of one full bit to this character, wasting 0.85 bits per occurrence wasting 0.85 bits per occurrence^[4]. Arithmetic coding bypasses this limitation by subdividing a continuous interval proportional to the exact probability of each symbol. The final encoded message is simply a binary fraction that points to a coordinate within the final subdivided interval points to a coordinate within the final subdivided interval^[5].

Because it separates the statistical model of the data from the encoding process, arithmetic coding is highly adaptable. The probability model can be updated dynamically as the data is processed, allowing the encoder and decoder to adapt to changing frequencies in the input stream without transmitting a new codebook adapt to changing frequencies in the input stream^[6]. This strict separation of modeling and coding has made arithmetic coding a fundamental technology in modern multimedia compression, supporting international standards for image, video, and audio formats supporting international standards for image, video, and audio formats^[7].

Information Theory and Probability Modeling

The efficiency of any entropy encoder is strictly bounded by the quality of the probability model it employs. Arithmetic coding acts as a mathematical engine that translates a given probability distribution into a compressed bitstream. If the model accurately predicts the frequency of incoming symbols, the resulting file size will be minimized. If the model is inaccurate, the arithmetic coder will assign larger subintervals to rare symbols and smaller subintervals to common symbols, actually expanding the data rather than compressing it translates a given probability distribution into a compressed bitstream^[2].

Probability models in data compression generally fall into two categories: static and adaptive. A static model analyzes the entire input dataset in advance to calculate the exact frequency of every symbol. These frequencies are compiled into a table, which is then used to drive the arithmetic encoder. While a static model guarantees an optimal probability distribution for the specific file, it requires the encoder to make two passes over the data. Furthermore, the frequency table itself must be prepended to the compressed file so the decoder can reconstruct the original interval proportions. For small files, the overhead of storing the probability table can entirely negate the space saved by the arithmetic coder overhead of storing the probability table^[4].

Adaptive models solve this problem by updating the probability distribution dynamically during the encoding process. Both the encoder and decoder begin with a predefined, uniform probability distribution where every symbol in the alphabet is assumed to be equally likely. As the encoder processes the first symbol, it uses the uniform distribution to calculate the interval, outputs the necessary bits, and then increments the frequency count for that specific symbol. When the second symbol is processed, the probability model has already been skewed slightly to favor the first symbol. Because the decoder receives the symbols in the exact same order, it can apply the exact same updating rules to its own probability model. This synchronized adaptation allows the model to learn the statistical properties of the data in a single pass without requiring a separate codebook to be transmitted synchronized adaptation allows the model to learn^[8].

The separation of modeling and coding also enables the use of complex context models. One of the most powerful modeling techniques paired with arithmetic coding is Prediction by Partial Matching (PPM), first formalized by John Cleary and Ian Witten in 1984 ^[9]. PPM does not simply track the overall frequency of symbols. Instead, it tracks the frequency of symbols based on the immediate preceding context. In the English language, the letter "u" is relatively uncommon overall, but if the preceding letter is "q", the probability of the next letter being "u" approaches 100 percent. A PPM model maintains multiple frequency tables for different context lengths (for example, tracking the previous one, two, or three characters). When the arithmetic coder needs to encode the next symbol, it queries the PPM model for the probability distribution associated with the current context. By providing the arithmetic coder with highly skewed, context aware probabilities, PPM algorithms consistently achieve some of the highest compression ratios possible for text data achieve some of the highest compression ratios possible for text data^[10].^[28]

Mathematical Foundations and Mechanism

Arithmetic coding operates by recursively subdividing a mathematical interval. The algorithm begins with an initial interval of 0.0 to 1.0. Each symbol in the source alphabet is assigned a subinterval proportional to its probability of occurrence. When the encoder reads a symbol from the input message, it restricts the current interval to the subinterval corresponding to that symbol. This new, smaller interval becomes the starting point for the next symbol. As the message grows, the interval becomes progressively narrower. The final encoded message is a single fractional number that falls anywhere within the final interval falls anywhere within the final interval.^[29]

To illustrate the mechanism, assume an alphabet contains three symbols, A, B, and C, with probabilities of 60 percent, 20 percent, and 20 percent respectively. The initial interval is 0.0 to 1.0. Symbol A is assigned the subinterval 0.0 to 0.6, symbol B is assigned 0.6 to 0.8, and symbol C is assigned 0.8 to 1.0. If the first symbol of the message is A, the encoder narrows the working interval to 0.0 to 0.6. The range of this new interval is 0.6.

If the second symbol is C, the encoder calculates the new subinterval by taking the top 20 percent of the current interval (0.0 to 0.6). The top 20 percent of a 0.6 range is 0.12. The lower bound is calculated as 0.0 plus (0.8 multiplied by 0.6), resulting in 0.48. The upper bound is 0.0 plus (1.0 multiplied by 0.6), resulting in 0.6. The interval is now 0.48 to 0.6, and the new range is 0.12.

If the third symbol is A, A takes the bottom 60 percent of the current interval. The bottom 60 percent of the 0.12 range is 0.072. The lower bound remains 0.48. The upper bound becomes 0.48 plus 0.072, resulting in 0.552. The final interval is 0.48 to 0.552. Any number between 0.48 and 0.552 uniquely encodes the string "ACA". The encoder can choose the shortest binary fraction in this range, such as 0.5, which is represented as 0.1 in binary (a single bit) represented as 0.1 in binary^[2].

A decoder reading the value 0.5 reverses this process. Knowing the initial probabilities, the decoder sees that 0.5 falls within the A subinterval (0.0 to 0.6), making the first symbol A. The decoder then updates its own interval to 0.0 to 0.6. To find the next symbol, the decoder calculates the relative position of 0.5 within the new interval: (0.5 minus 0.0) divided by 0.6 equals 0.8333. This value falls in the C subinterval (0.8 to 1.0), making the second symbol C. The decoder updates its interval to 0.48 to 0.6. The relative position of 0.5 within this third interval is (0.5 minus 0.48) divided by 0.12, which equals 0.1666. This falls in the A subinterval, making the third symbol A. The decoded message is "ACA" The decoded message is "ACA"^[4].

function encode(message, probabilities):
    low = 0.0
    high = 1.0
    for symbol in message:
        range = high - low
        high = low + range * cumulative_probability_high(symbol, probabilities)
        low = low + range * cumulative_probability_low(symbol, probabilities)
    return low

In a theoretical machine with infinite precision floating point registers, this process could continue indefinitely. In physical computers, floating point precision is strictly limited. To prevent precision loss, implementations use integer arithmetic and a process called renormalization a process called renormalization^[8]. Instead of tracking fractions, the algorithm tracks integers within a fixed register size, typically 16 or 32 bits. The interval 0.0 to 1.0 is mapped to the integer range 0 to 65535 (for a 16 bit register). When the upper and lower bounds of the interval share the same most significant digit, that digit is permanently fixed and cannot change regardless of future subdivisions. The encoder outputs this digit to the compressed stream and shifts the remaining bits to the left, appending a zero to the lower bound and a one to the upper bound. This shifting doubles the working range and reclaims the precision needed to continue encoding doubling the working range and reclaiming precision.

A specific mathematical edge case occurs when the lower bound approaches 0.5 from below (for example, 0.4999) and the upper bound approaches 0.5 from above (for example, 0.5001). The leading digits do not match, meaning they cannot be output, but the interval is too small to represent subsequent subdivisions accurately. This is known as the underflow problem. It is resolved by tracking these near matches in a counter and forcibly expanding the interval around the midpoint. When the bounds eventually diverge enough to output a bit, the encoder outputs the primary bit followed by the opposite bit repeated a number of times equal to the underflow counter equal to the underflow counter^[6].

The time complexity of arithmetic coding is $O(N)$ for encoding and decoding a message of length $N$, assuming the alphabet size $A$ is constant and cumulative probabilities can be retrieved in $O(1)$ time. The space complexity is $O(A)$ to store the frequency tables or probability models, plus $O(1)$ auxiliary space for the upper and lower bound registers auxiliary space for the upper and lower bound registers^[7].

Discovery and History

The theoretical basis for arithmetic coding originates in Claude Shannon's 1948 paper on information theory, which defined entropy and proved that data could be compressed up to a specific mathematical limit based on the probability of its symbols proved that data could be compressed up to a specific mathematical limit^[1].^[27] In the early 1950s, Peter Elias built upon Shannon's work to conceptualize the first version of arithmetic coding, known as Elias coding. Elias never formally published his algorithm, but it was documented by Norman Abramson in his 1963 textbook on information theory documented by Norman Abramson in his 1963 textbook^[11].^[30] Elias coding demonstrated the mathematical possibility of mapping a message to a continuous fraction, but it lacked a mechanism for finite precision arithmetic, making it impossible to implement on physical computers of the era.

The transition from theoretical mathematics to practical computer science occurred in 1976 through two independent research efforts. Jorma Rissanen, a researcher at IBM, published a paper generalizing the Kraft inequality and formalizing a practical approach to arithmetic coding generalizing the Kraft inequality and formalizing a practical approach^[12]. In the exact same year, Richard Pasco completed his doctoral thesis at Stanford University, detailing a finite register implementation of arithmetic coding detailing a finite register implementation of arithmetic coding^[13]. Rissanen and Pasco both introduced the concept of renormalization, which solved the precision limitations that had hindered Elias coding. Their work proved that arithmetic coding could be executed using fixed size integer registers, opening the door for software and hardware implementations.

Following these discoveries, IBM invested heavily in the technology. Glen Langdon and Jorma Rissanen developed several highly efficient binary arithmetic coders throughout the late 1970s and 1980s developed several highly efficient binary arithmetic coders^[14].^[31] IBM secured numerous patents on these implementations, including the Q coder and its successors, the QM coder and MQ coder. These patents strictly controlled the commercial use of arithmetic coding for decades. The threat of patent litigation created a chilling effect in the software industry, causing many developers to avoid arithmetic coding entirely, even when it offered superior compression performance. This legal environment is the primary reason why the open source community heavily favored the DEFLATE algorithm, which relies on patent free Huffman coding, for formats like ZIP and PNG.

In 1987, Ian H. Witten, Radford M. Neal, and John G. Cleary published a highly influential paper in the Communications of the ACM published a highly influential paper in the Communications of the ACM^[6]. This paper provided a complete, working implementation of arithmetic coding written in the C programming language. By demonstrating that arithmetic coding could be executed efficiently on standard microprocessors using basic integer math, the authors popularized the technique outside of corporate research laboratories. The source code provided in the paper became the de facto standard for academic research into data compression for the next decade.

In 1998, Alistair Moffat, Radford M. Neal, and Ian H. Witten published a follow up paper in ACM Transactions on Information Systems, refining the 1987 algorithm refining the 1987 algorithm^[8]. The revised implementation replaced slow division operations with faster shift and add operations, improved precision management, and introduced a modular software architecture that cleanly separated the probability modeling from the arithmetic encoder. This modularity allowed researchers to easily plug different context models, such as PPM, into the arithmetic coding engine, accelerating the development of advanced text compression utilities.

Important Variants

Binary Arithmetic Coding (BAC) restricts the alphabet to exactly two symbols, typically 0 and 1. By eliminating multi symbol probability tables, BAC simplifies the interval subdivision into a single conditional branch. This reduces computational overhead and avoids complex multiplication or division, making it highly suitable for hardware implementation in application specific integrated circuits highly suitable for hardware implementation. The Q coder, QM coder, and MQ coder developed by IBM are all examples of highly optimized binary arithmetic coders. The Q coder was unique because it approximated probability multiplication using a simple addition and subtraction mechanism, relying on the fact that one symbol (the Most Probable Symbol) occurs much more frequently than the other (the Least Probable Symbol). Because these coders only process binary data, any multi symbol alphabet must first be converted into a binary string (a process called binarization) before it can be encoded by a BAC algorithm.

Context-Based Adaptive Binary Arithmetic Coding (CABAC) is a specialized variant developed by Detlev Marpe, Heiko Schwarz, and Thomas Wiegand in 2003 developed by Detlev Marpe, Heiko Schwarz, and Thomas Wiegand in 2003^[15]. CABAC combines binary arithmetic coding with a complex context modeling system. It predicts the probability of the next bit based on the values of previously encoded bits in its immediate spatial or temporal vicinity. CABAC is heavily optimized for video compression and avoids multiplication entirely by using precalculated state machines to estimate probabilities. The algorithm maintains dozens of different probability models simultaneously, switching between them dynamically based on the syntax element being encoded, such as motion vectors or transform coefficients.

Range Encoding was introduced by G.N.N. Martin in 1979 introduced by G.N.N. Martin in 1979^[16]. While mathematically identical to arithmetic coding, range encoding normalizes the interval at the byte or word level rather than the bit level. By shifting 8 or 16 bits at a time, range encoding aligns perfectly with the architecture of modern byte addressable central processing units, resulting in significantly faster execution times in software implementations. Because it outputs data in larger chunks, range encoding avoids the bit level manipulation overhead that slows down traditional arithmetic coders on general purpose processors.

Asymmetric Numeral Systems (ANS) is a modern entropy coding method introduced by Jarek Duda in 2009 introduced by Jarek Duda in 2009^[17]. ANS achieves the exact fractional bit allocation of arithmetic coding but uses a single integer state rather than an upper and lower bound uses a single integer state rather than an upper and lower bound^[18]. In ANS, the current state of the encoder is represented by a single natural number. When a new symbol is encoded, this number is multiplied by a fraction derived from the symbol's probability, and the result is rounded to the nearest integer. ANS comes in two main variants: range ANS (rANS) and tabled ANS (tANS). The tabled variant uses a precomputed state machine to perform encoding and decoding using only table lookups, completely eliminating arithmetic operations during the decoding phase. This mathematical restructuring allows ANS to match the compression ratio of arithmetic coding while operating at decoding speeds comparable to Huffman coding, effectively bridging the gap between the two historical methods.

Real-World Applications

The JPEG 2000 image compression standard (ISO/IEC 15444-1) relies on the MQ coder, a binary arithmetic coder developed by IBM relies on the MQ coder^[19].^[29] The MQ coder processes the wavelet coefficients generated by the image transform, providing superior compression compared to the Huffman coding used in the original JPEG standard. The use of arithmetic coding in JPEG 2000 allows for highly scalable bitstreams, where an image can be decoded at multiple resolutions or quality levels from a single compressed file.

The JBIG standard (ITU-T T.82), designed for the lossless compression of bilevel images such as scanned documents and faxes, utilizes the QM coder utilizes the QM coder^[20].^[32] This arithmetic coder allows JBIG to compress monochrome data significantly better than older run length encoding methods. The QM coder adapts to the specific patterns of black and white pixels in a document, efficiently compressing large areas of blank space and sharp text edges.

In video compression, CABAC is not mandatory for all profiles of H.264 (the Baseline profile uses CAVLC) (ITU-T H.264) and its successors, High Efficiency Video Coding (HEVC) and Versatile Video Coding (VVC) mandatory component of the H.264/AVC standard^[21].^[33] CABAC is responsible for compressing the residual data, motion vectors, and macroblock headers, contributing heavily to the high compression efficiency of modern video streaming. The adoption of CABAC in H.264 The 9 to 14 percent reduction in bit rate is compared to CAVLC (the baseline entropy coding method of H.264/AVC), not previous MPEG standards.

The VP8 video format, documented in RFC 6386, uses a boolean entropy coder uses a boolean entropy coder^[22]. This is a form of binary arithmetic coding that processes the discrete cosine transform coefficients and motion vectors to reduce the final file size. The boolean coder in VP8 operates similarly to CABAC but uses a different probability updating mechanism optimized for software decoding.

The LZMA compression algorithm, widely used in the 7-Zip archiving software, employs range encoding to compress the output of its dictionary based Lempel Ziv phase employs range encoding^[23]. The combination of a massive dictionary and a highly optimized range encoder gives LZMA its characteristic high compression ratio. The range encoder in LZMA processes probabilities using a complex Markov chain model, allowing it to compress highly redundant binary data effectively.

While video and image formats heavily utilize arithmetic coding, audio formats often take a different approach. Formats like FLAC generally avoid arithmetic coding in favor of Golomb Rice coding because audio samples have a Laplacian distribution that is perfectly suited for Rice codes, making the computational overhead of arithmetic coding unnecessary. However, advanced lossy audio codecs like the AAC uses Huffman coding, not arithmetic coding. to compress their quantized frequency coefficients, where the probability distributions are more complex.

Significance, Tradeoffs, and Error Resilience

Arithmetic coding is significant because it provides a practical method for achieving optimal data compression. By allowing symbols to consume fractional bits, it eliminates the quantization waste inherent in discrete prefix codes. This is especially advantageous for alphabets with highly skewed probability distributions, where a single symbol might occur 99 percent of the time and should ideally consume 0.01 bits should ideally consume 0.01 bits^[2]. A Huffman coder would be forced to assign a full bit to this symbol, inflating the file size, whereas an arithmetic coder handles it with mathematical precision.

Another major advantage is the strict separation of the statistical model from the encoding mechanism. In Huffman coding, changing the probability model requires rebuilding the entire binary tree and transmitting it to the decoder requires rebuilding the entire binary tree^[24]. In arithmetic coding, the model can be updated dynamically after every symbol. As long as the encoder and decoder use the exact same rules to update their probability tables, they remain synchronized without any additional overhead in the compressed stream.

Despite its efficiency, arithmetic coding has historical and technical tradeoffs. Throughout the 1980s and 1990s, the algorithm was heavily encumbered by patents held by IBM and other corporations. This patent environment discouraged widespread adoption in open standards. For example, the original JPEG standard defined an optional arithmetic coding extension, but software developers universally avoided it in favor of the royalty free Huffman alternative avoided it in favor of the royalty free Huffman alternative^[7]. These patents expired in the 2000s and 2010s, clearing the way for unencumbered use.

Technically, arithmetic coding is computationally intensive. The interval subdivision requires multiplications and divisions, which consume more processing cycles than the simple table lookups used in Huffman coding. While variants like BAC and range encoding reduce this overhead, arithmetic coding is generally slower than discrete coding methods. In recent years, Asymmetric Numeral Systems has largely replaced arithmetic coding in speed critical software applications, The Zstandard algorithm is currently specified in RFC 8878 (RFC 8478 is obsolete). such as the Zstandard algorithm^[25] WebP lossless uses Huffman coding, not Asymmetric Numeral Systems. WebP lossless specification^[26]. However, hardware accelerated binary arithmetic coding remains the standard in video compression, where maximum bit rate reduction justifies the computational cost.

A final significant tradeoff of arithmetic coding is its extreme sensitivity to data corruption, known as the avalanche effect. Because the entire message is encoded as a single continuous fraction, the decoding of every symbol depends entirely on the correct decoding of the previous symbol. If a single bit in the compressed stream is flipped due to transmission noise or storage degradation, the decoder will calculate an incorrect subinterval. This error will propagate forward, causing all subsequent symbols to be decoded incorrectly, completely destroying the remainder of the file causing all subsequent symbols to be decoded incorrectly^[7]. To prevent this vulnerability, modern transmission protocols must wrap arithmetic coded data in strong error correction codes, or the encoder must periodically reset its state to create independent synchronization points within the stream.