The main idea of Arithmetic coding is to represent sequence of symbols
by single
number of very high precision.
Lets try to define the basic algorithm for Binary Arithmetic
Coding.
Output count-1 equal bits starting from the most
significant
but not including msb - it was already put out.
Shift all this bits away from α and
β.
New α and β are computed like this:
α = α << count
or
α = α * 2^{count}
β = (β << count) |
(2^{count} - 1)
Here '&' is a binary 'and' operation.
Continue the main loop until the last input symbol.
If after quiting the main loop, the underflow counter is not zero:
Output msb[β].
Output underflow bits of !msb[β].
Output the reminder of β until
The last '1' is printed out
or
There are no more non-zero bits in α.
The alternative is to put out all reminded bits of β - this
overhead is not too big.
We want the output floating point to be in the right range.
For example, if the range is [0.001, 0.1011) and we have precision only
for 2 bits,
then we will get α = 0.00 and β = 0.10.
Here we see β is in given range, while 0.00 < 0.001 and
therefore α is out of range.
Slice range [α, β) exactly like it
was done for encoding.
Find sub-range corresponding to the binary number a.
Sign symbol corresponding to this number with x.
Compute subrange exactly like it was done for
encoding:
α_{x}` = (β -
α)∑_{i=0}^{x-1}f_{i}
β_{x}` = f_{x}(β - α)
Shift a by underflow bits:
a = ((a << underflow) ^ 2^{L-1}) | (msb[a] <<
(L-1)).
This computation is exactly the same that was done for α.
Read the next underflow coded bits to a.
Check for overflow.
Count how many bits in α are equal to bits in β on the same
position.
Count starting from msb and stop on the first unmatched bit.
Shift overflow from α, β and a.
Operation is the same like described for underflow:
α = α << overflow
β = (β << overflow) | (2^{overflow}
- 1)
a = a << overflow
Read the next overflow bits to a.
Continue the decoding loop.
Notice that in decoding process we do not have to keep the underflow
counter.
During the encoding we did not know what bits must be put out until the
next overflow.
In the decoding
We have this bits in a.
We do not have any use for this information.
The n-ry Arithmetic Coding.
The described coding is Binary because the output
of the coding is high-precision
floating point number in binary representation.
The Binary Arithmetic Coding is not the
only possible Arithmetic Coding.
Lets try to construct n-ry Arithmetic Coder.
The algorithm of constructing n-ry Coder is quit similar to the Binary
Coder
including care for underflow and overflow.
We decide that we are in the underflow position
if:
α_{s0} = β_{s0} -
1.
β_{s1} = 0.
α_{s1} = n - 1.
Here I signed γ_{si} as a digit i of number
γ,
starting from the most significant digit
γ_{s0}.
All shifts, used in the Binary Coder are now shifts of digits instead of
bits.
When shifting β, it must be filled with digits n-1 instead
of 1`s.
In the rest of this document I will refer to the Binary Arithmetic
Coder.
Precision of Arithmetic Coder.
In the definition of Arithmetic Coding algorithm I was using symbol L to
sign precision
of values α and β.
That mean L is amount of bits used to represent α and β.
If precision is too low, we can end-up in the middle of encoding with
α equal to β
and even this interval can fit for more then one symbol.
For this reason precision L must be big enough that for any
symbol s,
f_{s} can be coded by L-3 bits of binary floating point number
or simple
f_{s} ≥ ^{1}/_{2L-3}.
Why do I insist on probability to be encoded with L-3 non-zero bits:
The maximal value of α without overflow is
.0(1)_{L-1} or
(^{2L-1-1}/_{2L})
The minimal value of β without overflow
is
.1(0)_{L-1} or
(^{2L-1}/_{2L})
With given α, minimal β` that is not causing underflow is
.11(0)_{L-2} or
(^{2L-1+2L-2}/_{2L})
β`-α < β-α`,
therefore β`-α is the minimal width of ranges [α,
β)
that can appear during the computation of Binary
Arithmetic Coding and not
in state of overflow or underflow.
To distinguish symbol s from the next symbol s+1,
subrange [α_{s}, β_{s}) must be big enough.
Particularly, β_{s}-α_{s} ≥
^{1}/_{2L}.
β_{s}-α_{s} =
(β`-α)*f_{s}
(β`-α)*f_{s} ≥
^{1}/_{2L}
(^{2L-2-1}/_{2L})*f_{s}
≥
^{1}/_{2L}
f_{s} ≥
(^{1}/_{2L-2-1})
(^{1}/_{2L-3}) >
(^{1}/_{2L-2-1}),
therefore if
f_{s} ≥
(^{1}/_{2L-3})
then
f_{s} >
(^{1}/_{2L-2-1})
^{1}/_{2L-3} =
.(0)_{L-4}1
This mean f_{s} must be big enough to be represented with
not more then L-3 non-zero bits.
Gather Statistics.
The next open question is how to gather and pass statistics data.
Adaptive scheme for Binary Arithmetic Coding can be achieved by two main
methods:
In the start of encoding process, assume all possible
symbols to have
equal probability of occurrence.
After encoding each new symbol, update this symbol probability.
Except for this small difference the rest of the algorithm is
exactly the same as
the static Arithmetic Coding algorithm.
This is including the check if each possible symbol probability
can be
represented by L-3 bits.
Set initial probability of occurrence for each symbol to
zero.
Define special symbol with non-zero probability - Escape
symbol.
This algorithm can be implemented like this:
Initialize all internal structures as defined by
Arithmetic Coding
and set probabilities table as defined above.
Start encoding loop here.
Read the next input symbol s from the input
stream.
Check probability of symbol s.
If probability of symbol s, f_{s}
can be represented by L-3 bits,
f_{s} >
^{1}/_{2L-3},
assign symbol t, t = s.
Otherwise assign t = Escape symbol.
Slice range [α, β)
exactly like it was
done for static Arithmetic Coding.
Encode symbol t with Arithmetic Coding by computing
new α and β.
If needed, update probability of Escape symbol.
Ensure f_{Esc} ≥
^{1}/_{2L-3}.
Repeat loop until the last symbol is encoded.
Finish Arithmetic Coding by output of underflow bits
and reminder.
Notice that Adaptive Coding in this form is not requiring long
recomputations for
each symbol that can not be represented by L-3 bits.
Both of this schemes will benefit from representing symbol probabilities
by symbol counts
and not real floating point probabilities.
In this case updating symbol probability is single operation, where
computing real
probabilities require recomputation for each symbol.
Advanced possibilities for Arithmetic Coding.
MTF - Move To Front scheme is applicable to Arithmetic Coding.
PPM - Prediction by Partial Match is applicable too.
BWT - Burrows-Wheeler Transform can improve compression ratio.