Arithmetic Coding | Teleinf Edu

Arithmetic coding and fractional code lengths

Huffman coding assigns variable-length codewords to symbols according to their probabilities. For a fixed model it is optimal within the class of binary prefix codes, since no other code in that class has a lower average length. Its limitation is that every codeword has an integer length. A character may receive a 3-bit or 4-bit code, but not a codeword of length 3.5 bits.

Source entropy is often not an integer. For example, a symbol may carry 2.58 bits of information. Huffman coding approximates this value with integer codeword lengths. Arithmetic coding avoids that restriction by representing a sequence in a final sub-range of [0,1), which allows an average length closer to the model entropy. .

Arithmetic coding represents a sequence by successively narrowing a sub-range between 0 and 1. In the ideal description the final sub-range is represented by one number, while implementations emit bits incrementally and use renormalization. This approach can produce an average code length closer to the limit set by the model entropy. At each step, the interval width is multiplied by the probability of the selected symbol, so longer messages require finer numerical precision.

The core concept of arithmetic coding

Arithmetic coding does not substitute a separate codeword for each symbol. The algorithm progressively narrows a numerical range while preserving the proportions defined by the probability model.

The initial range

The process begins by defining an initial range, typically from 0.0 up to but not including 1.0, written as $[0, 1)$ . The range is the representation domain for messages allowed by the model.

Subdividing the range by probability

The next step is to divide this initial range into smaller sub-ranges, one for each possible symbol in the alphabet. The size of each symbol's sub-range is directly proportional to its probability of occurrence.

A symbol with a high probability (like 'e' in English) will be allocated a large sub-range.
A symbol with a low probability (like 'z') will be allocated a very small sub-range.

This initial partitioning of the $[0, 1)$ range forms the basis of the statistical model, which the encoder and decoder must share.

Encoding as range refinement

As the algorithm processes the input message symbol by symbol, it successively narrows down the range.

When the first symbol of the message is read, the algorithm selects the sub-range corresponding to that symbol. This sub-range now becomes the new "current range".
For the second symbol, the algorithm takes this new, smaller current range and subdivides it in exactly the same proportions as the original $[0, 1)$ range.
It then selects the sub-sub-range corresponding to the second symbol. This becomes the next current range.
The process continues, with each symbol selecting a smaller portion of the numerical range.

After the last symbol has been processed, the algorithm has a final range of numbers. With a fixed message length and shared model, any number in that range identifies the encoded sequence. The encoder emits a binary representation of a number or sub-range, choosing a stream that still identifies the final range.

A detailed encoding example

The process can be followed with a concrete example that encodes the word "CACAO".

Step 0: establish the probability model

The example uses the following probability model for its alphabet:

Symbol	Probability	Initial Range
'C'	0.3	[0.0, 0.3)
'A'	0.2	[0.3, 0.5)
'O'	0.5	[0.5, 1.0)

The current range is tracked with two variables: $\text{low}$ and $\text{high}$ . Initially, $\text{low} = 0.0$ and $\text{high} = 1.0$ . The current range width is $\text{range} = \text{high} - \text{low}$ .

Step 1: encode the first symbol, 'C'

The first symbol is 'C'. According to the model, its range is [0.0, 0.3). The corresponding sub-range is selected within the current range by scaling to the current range width.

Current range: $[0.0, 1.0)$ , so $\text{range} = 1.0 - 0.0 = 1.0$ .
The new $\text{low}$ bound becomes the old low bound plus the range multiplied by the start of C's range (cumulative start in 0-1 scale): $0.0 + (1.0 \times 0.0) = 0.0$ .
The new $\text{high}$ bound becomes the old low bound plus the range multiplied by the end of C's range (cumulative end in 0-1 scale): $0.0 + (1.0 \times 0.3) = 0.3$ .
New Current Range: [0.0, 0.3)

Step 2: encode the second symbol, 'A'

The calculation remains within the new range [0.0, 0.3). This smaller range is subdivided using the original proportions: the cumulative start and end of the symbol on the 0-1 scale are scaled to the current width.

Current range: $[0.0, 0.3)$ , so $\text{range} = 0.3 - 0.0 = 0.3$ .
The range for 'A' is [0.3, 0.5). This means that in 0-1 scale 'A' starts at 0.3 and ends at 0.5; we apply these values, multiplying by the current range width and adding to the low bound.
The new $\text{low}$ bound: $0.0 + (0.3 \times 0.3) = 0.0 + 0.09 = 0.09$ .
The new $\text{high}$ bound: $0.0 + (0.3 \times 0.5) = 0.0 + 0.15 = 0.15$ .
New Current Range: [0.09, 0.15)

Step 3, 4, 5: repeat for 'C', 'A', 'O'

The process continues for the remaining characters, each time taking the cumulative start and end of the symbol (in 0-1 scale), multiplying by the current width and adding to the current low bound, to obtain the new sub-range.

After 'C': Range becomes $[0.09, 0.108)$ . (calculations: width = 0.15 - 0.09 = 0.06; for 'C' [0.0,0.3): low = 0.09 + 0.06*0.0 = 0.09; high = 0.09 + 0.06*0.3 = 0.09 + 0.018 = 0.108)
After 'A': Range becomes $[0.0954, 0.099)$ . (calculations: width = 0.108 - 0.09 = 0.018; for 'A' [0.3,0.5): low = 0.09 + 0.018*0.3 = 0.09 + 0.0054 = 0.0954; high = 0.09 + 0.018*0.5 = 0.09 + 0.009 = 0.099)
After 'O': Final Range: [0.0972, 0.099). (calculations: width = 0.099 - 0.0954 = 0.0036; for 'O' [0.5,1.0): low = 0.0954 + 0.0036*0.5 = 0.0954 + 0.0018 = 0.0972; high = 0.0954 + 0.0036*1.0 = 0.0954 + 0.0036 = 0.099)

Step 6: finalize and output the code

The message "CACAO" is represented by the final range [0.0972, 0.099). Any number within this range can serve as the encoded message. In practice, a number with a short binary fractional representation is selected from this range.

For example, the number 0.09765625 is within this range. Its binary fractional representation is $0.00011001$ . This binary string is the compressed output.

Decoding by reconstructing the range

The decoder reconstructs the same sub-ranges as the encoder. It must start with the exact same initial probability model and receives the encoded number, for example 0.09765625.

Decode Symbol 1: The decoder looks at its initial range [0, 1). It checks which symbol's sub-range the value 0.09765625 falls into. It falls within [0.0, 0.3), so the first symbol is 'C'.
Update Range:The decoder now knows the first symbol was 'C', so it updates its current range to [0.0, 0.3), exactly as the encoder did.
Renormalize Value and Decode Symbol 2: To find the next symbol, the decoder remaps the received value to this new range. It calculates $(0.09765625 - 0.0) / 0.3 \approx 0.3255$ . It then checks where this new value falls in the original model. 0.3255 falls within the range for 'A' [0.3, 0.5). The second symbol is 'A'.
Repeat:The process continues. The decoder narrows A's range, renormalizes the value again, and reads 'C' and the following symbols until it reconstructs "CACAO".

Arithmetic coding and Huffman coding

Both methods use a statistical model, but they represent symbols and sequences differently.

Aspect	Huffman coding	Arithmetic coding
Bit Allocation	Assigns each symbol a codeword with an integer length; lengths may differ between symbols.	Produces a fractional average number of bits per symbol over the whole message.
Optimality	Optimal for a fixed model within prefix codes, but integer codeword lengths leave a gap from the entropy.	With a matching model, the average length can approach the model entropy; model and termination overhead remain.
Model and coder separation	The statistical model and code tree are linked during prefix-code construction, so changing the distribution usually requires a new tree.	The coding mechanism is separate from the statistical model. The same coder can use fixed or adaptive models, including Markov models.
Speed and complexity	Usually requires counting, sorting, and tree traversal, so the coding operations are simple.	Requires range updates and renormalization. Implementations can use integer arithmetic, and cost depends on the model.

The ideal information contribution of a symbol with probability $P(\text{symbol})$ is $-\log_2(P(\text{symbol}))$ bits. Huffman coding must use integer codeword lengths, while arithmetic coding can bring the average length closer to this contribution. Separating the statistical model from the coding mechanism supports fixed and adaptive models. This value is an average for the model; individual symbols can have different code lengths. In an adaptive model, probabilities change during encoding and decoding.

Practical applications

Arithmetic coding took longer to become widely adopted than Huffman coding. Implementation cost and patents covering selected techniques affected adoption, particularly during the 1980s and 1990s. Licensing constraints reduced interest in using the method in open standards and software.

As parts of the relevant patent restrictions expired, the licensing constraint weakened. Arithmetic coding is used in standards that combine context modeling with a short output stream:

Image compression: JPEG 2000 uses the binary MQ arithmetic coder in block coding.
Video coding: CABAC, or context-adaptive binary arithmetic coding, is part of the H.264/AVC and H.265/HEVC standards.
Specialized compressors: The method is used in compressors where computation cost can be justified by a shorter output stream.

Arithmetic coding demonstrates how a statistical model and interval operations can reduce the average length of a lossless stream. Its usefulness depends on the model, precision, renormalization method, and computational cost. The stream must also convey the model or use a model already shared by the decoder. The decoder also needs a symbol order and a termination rule, because a sub-range alone does not identify a message of unbounded length.