Arithmetic Coding
Background of the Algorithm
What is it? A form of entropy encoding used in lossless data compression where the input stream
is compressed into a single floating-point number between 0 and 1.
Who invented it? This fundamental concept has been introduced a while ago in an unpublished
work around 1963 by Peter Elias. His initial proposal, though optimal, was impractical as it
presumes infinite-precision, and consequently an infinite buffer size! His idea was later on been
improved on using practical schemes by Jorma Rissanen and Richard Pasco which is known
as finite-precision in 1976.
What does it solve? The predecessor of arithmetic coding is the Huffman Coding which is a
fixed-length coding method. This means Huffman always assigns at least 1 bit for a given
probability.
This becomes a problem for when the probability of a character is very high. For example, when
encoding “aaaaaaaaab” with probabilities 0.9 for a and 0.1 for b:
Huffman coding: assigns 0 to a, 1 to b, resulting in 0000000001
Arithmetic coding: assigns the interval 0.1–1.0 to a, 0.0–0.1 to b, resulting in .301272
or .1010000
By representing fractions to the input, arithmetic coding bypasses the idea of replacing an input
symbol with a specific code.
What is the running time? For both encoding and decoding, typically the runtime complexity is
linear, O(n), though implementation details may complicate this, such as the precision. Though
compared to Huffman coding, the running time is slower due to the computational overhead.
What is the space requirements? The algorithm, given a finite-precision implementation, requires
buffers for the high and low values relative to the selected buffer size (e.g 16-bit integer). This
doesn’t include the requirements for the chosen probability model (which varies depending on
implementation).
To demonstrate the fundamental aspects of arithmetic coding, the provided examples will be
using infinite-precision.
Infinite-Precision Demo: Encoding
How does it work? To construct the floating-point number output:
1. Take the input stream and the probabilities of each symbol as inputs to the encoder.
2. Assign a portion of the probability line [0, 1) for each symbol which corresponds to its
probability.
3. Encode each symbol restricted along its range. The sum of this computation will result to the
final output.
As an example, our input string will be “ab$”. ‘$’ is the EOF symbol.
Suppose the probability model has generated:
a: 0.4
b: 0.4
$: 0.2
And the upper and lower bounds assigned to each symbol are:
$: [0.0–0.2)
a: [0.2–0.6)
b: [0.6–1.0)
We first start with the high and low values as 0.0 and 1.0 respectively. To encode ‘a’, get the
range it can fall into. In this case it will be [0.2–0.6). The final output will be a number between
this range.
Next, assign 0.2 as the new lower bound, and 0.6 as the new upper bound. Take the next symbol,
‘b’ and get its range. In this case it is assigned [0.6–1.0). This range is now relative to the
subdivided portion after encoding a [0.2–0.6).
Lastly, encode ‘$’ using the same procedure as before.
The resulting range, [0.440–0.472), means we can pick any number within this range and it will
uniquely encode ‘ab$’. For simplicity, let’s choose the lower bound 0.440.
The pseudocode for encoding is:
low = 0.0
high = 1.0
for each symbol in input
{
range = high - low
high = low + range * high_range(symbol)
low = low + range * low_range(symbol)
}
output(low)
Infinite-Precision Demo: Decoding
How does it work? Knowing the encoding process, we simply reverse the computations by
reducing the resulting output 0.440.
First we find the range for which the first symbol falls in. In 0.440, since it falls between 0.4 and
0.6, it must be the character ‘b’ according to the model. We then subtract the lower bound of ‘b’
to the output, then divide by the width of the range of ‘b’ (which is .2). Using this procedure, we
further reduce the output as we recognize the next symbol.
Press enter or click to view image in full size
The pseudocode for decoding is:
number = input_code()
while (symbol != EOF)
{
symbol = find_symbol_within_this_range(number)
output(symbol)
range = high_range(symbol) - low_range(symbol)
number = number - low_range(symbol)
number = number / range
}
Another way is to make use of the intervals where we continuously build up on the lower and
upper bound that will contain the input value.
low = 0.0
high = 1.0
number = input_code()
while (true)
{
for each symbol in possible symbols
{
range = high - low
low_temp = low + low_range(symbol)
high_temp = low + high_range(symbol)
if (low_temp <= number && number < high_temp)
{
output(symbol)
if (symbol == EOF)
quit
low = low_temp
high = high_temp
}
}
}
Float-value into binary format
So far, we only know that the final output was 0.440, but to actually encode this, we need to treat
it as binary fraction (i.e. .11111…).
To do this, we apply the same subdivision principle or rescaling technique when encoding 0 or 1.
The range of [0, 0.1) may be represented such that the lower half is 0, and the upper half is 1 in
binary.
The range of the final output was [0.440, 0.472). This will dictate the binary sequence to encode,
since this range will either fall on the lower half (0), or upper half (1).
Press enter or click to view image in full size
At the end, we have found a range that is contained within the initial range that was computed
[0.440, 0.472). Therefore, the resulting binary sequence will be .011101.
As the range becomes smaller during the encoding, you will find that it may not entirely lie on the
entirety of the upper/lower half of the width. Sometimes the range may be on the middle, such
that the lower bound is on the lower half (0) and the upper bound is on the upper half (1). In such
cases, the rescaling factors in the quarter portion, or the three-fourths portion of the range.
The same scaling principle is also applied during decoding.
The pseudocode for the rescaling is:
remaining_bits = 0
while (high < HALF or low > HALF)
{
if (high < HALF)
{
output(0)
low = 2 * low
high = 2 * high
}
else if (low > HALF)
{
output(1)
low = 2 * (low - HALF)
high = 2 * (high - HALF)
}
}
while (low > QUARTER and high < THREE-FOURTHS)
{
remaining_bits++
low = 2 * (low - QUARTER)
high = 2 * (high - QUARTER)
}
remaining_bits++
if (low <= QUARTER)
{
output(0)
for 0 to remaining_bits
output(1)
}
else
{
output(1)
for 0 to remaining_bits
output(0)
}