Databases Reference
In-Depth Information
In the case of the static arithmetic code, we picked the size of the word based on
Total_Count, the total number of symbols to be encoded. In the adaptive case, we may
not know ahead of time what the total number of symbols is going to be. In this case we
have to pick the word length independent of the total count. However, given a word length
m
we know that we can only accommodate a total count of 2
m
−
2
or less. Therefore, during
the encoding and decoding processes when the total count approaches 2
m
−
2
,wehavetogo
through a rescaling, or renormalization, operation. A simple rescaling operation is to divide
all counts by 2 and round up the result so that no count gets rescaled to zero. This periodic
rescaling can have an added benefit in that the count table better reflects the local statistics of
the source.
4.6 Binary Arithmetic Coding
In many applications the alphabet itself is binary. While at first sight this may seem odd
(Why would one need an encoder to encode a binary sequence?), a little bit of thought makes
the reasoning apparent. Consider a binary source that puts out one symbol with probability
0.125 and the other with probability 0.875. If we directly encode one of the letters as a 0 and
the other as a 1, we would get a rate of 1 bit/symbol. However, the entropy of the source
is 0.543; so by directly encoding the output of the source as a 0 or a 1, we are encoding at
almost twice the rate we need to. In order to achieve the entropy, we need to encode the more
probable symbol at a fractional bit rate, which is exactly what arithmetic coding allows us
to do; hence the popularity of the arithmetic code for encoding binary sources with highly
skewed probabilities. The source can be binary by its nature, such as bilevel documents; or the
binary input may be the binary representation of nonbinary data, as is the case for the Context
Adaptive Binary Arithmetic Coder (CABAC) in the H.264 video coding standard.
As for arithmetic coding in general, the binary arithmetic coder also requires a probability
model. However, because there are only two letters in the alphabet, the probability model
consists of a single number, namely the probability of one of the symbols; the probability of
the other symbol is simply one minus the specified probability. Because we only need a single
number to represent the probability model, it is easy to use multiple arithmetic codes to encode
a source where different models represent different contexts. This results in a much more
accurate modeling of the source than would have been possible with a single model, which in
turn leads to better compression.
Example4.6.1:
Consider a binary sequence generated by scanning a document where the white pixels are
represented by a 0 and the black pixels by a 1. Clearly the probability of a pixel being white
or black depends heavily on whether the neighboring pixel is white or black. For this example
we will use a first order context, so we have two sets of
Count
and
Cum_Count
tables:
Count
0
Cum
_
Count
0
(
−
1
)
=
0
Count
1
Cum
_
Count
1
(
0
)
=
8
(
0
)
=
2
(
−
1
)
=
0
Count
0
Cum
_
Count
0
Count
1
Cum
_
Count
1
(
1
)
=
2
(
0
)
=
8
(
1
)
=
8
(
0
)
=
2
Total
_
Count
0
=
10
Cum
_
Count
0
Total
_
Count
1
(
0
)
=
10
Cum
_
Count
1
(
1
)
=
10
(
1
)
=
10
