![](https://csdnimg.cn/release/download_crawler_static/87501255/bg12.jpg)
The coding of each bool restricts the possible values of
x
in proportion to the probability of what is coded. If
p1
is the probability of the first bool being zero and a zero is coded, the range of possible
x
is restricted to
0 ≤ x < p1
. If a one is coded, the range becomes
p1 ≤ x < 1
.
The coding continues by repeating the same idea. At every stage, there is an interval
a ≤ x < b
of possible
values of
x
. If
p
is the probability of a zero being coded at this stage and a zero is coded, the interval becomes
a ≤ x < a +
(
p ⋅
(
b − a
)
)
. If a one is coded, the possible
x
are restricted to
a +
(
p ⋅
(
b − a
)
)
≤ x < b
.
Assuming only finitely many values are to be coded, after the encoder has received the last bool, it can write
as its output any value
x
that lies in the final interval. VP8 simply writes the left endpoint of the final interval.
Consequently, the output it would make if encoding were to stop at any time either increases or stays the
same as each bool is encoded.
Decoding parallels encoding. The decoder is presented with the number
x
, which has only the initial
restriction
0 ≤ x < 1
. To decode the first bool, the decoder is given the first probability
p1
. If
x < p1
, a zero is
decoded; if
x ≥ p1
, a one is decoded. In either case, the new restriction on
x
, that is, the interval of possible
x
,
is remembered.
Decoding continues in exactly the same way: If
a ≤ x < b
is the current interval and we are to decode a bool
with zero-probability
p
, we return a zero if
a ≤ x < a +
(
p ⋅
(
b − a
)
)
and a one if
a +
(
p ⋅
(
b − a
)
)
≤ x < b
. In either
case, the new restriction is remembered in preparation for decoding the next bool.
The process outlined above uses real numbers of infinite precision to express the probabilities and ranges. It
is true that, if one could actualize this process and coded a large number of bools whose supplied
probabilities matched their value distributions, the datarate achieved would approach the theoretical minimum
as the number of bools encoded increased.
Unfortunately, computers operate at finite precision and an approximation to the theoretically perfect process
described above is necessary. Such approximation increases the datarate but, at quite moderate precision
and for a wide variety of data sets, this increase is negligible.
The only conceptual limitations are, first, that coder probabilities must be expressed at finite precision and,
second, that the decoder be able to detect each individual modification to the value interval via examination of
a fixed amount of input. As a practical matter, many of the implementation details stem from the fact that the
coder can function using only a small “window” to incrementally read or write the arbitrarily precise number
x
.
7.2 Practical Algorithm Description
VP8’s bool coder works with 8-bit probabilities
p
. The range of such
p
is
0 ≤ p ≤ 255
; the actual probability
represented by
p
is
p
/
256
. Also, the coder is designed so that decoding of a bool requires no more than an
8-bit comparison and so that the state of both the encoder and decoder can be easily represented using a
small number of unsigned 16-bit integers.
The details are most easily understood if we first describe the algorithm using bit-at-a-time input and output.
Aside from the ability to maintain a position in this bitstream and write/read bits, the encoder also needs the
ability to add
1
to the bits already output; after writing
n
bits, adding
1
to the existing output is the same thing
as adding
pow
(
2, − n
)
to
x
.
Together with the bit position, the encoder must maintain two unsigned 8-bit numbers which we call
bottom
and
range
. Writing
w
for the
n
bits already written and
S = pow
(
2, − n − 8
)
for the scale of the current bit
VP8 Data Format and Decoding Guide Chapter 7: Boolean Entropy Decoder
WebM Project Page 18 of 94