Graphics Reference
In-Depth Information
derivation logic by which, in turn, the given context model is specified. A lot of
effort has been spent during the HEVC standardization process to improve the model
assignment and context derivation logic both in terms of throughput and coding
efficiency. More details on the specific choice of context models for selected syntax
elements in HEVC are given in Sect.
8.4
-
8.6
.
8.2.3
Multiplication-Free Binary Arithmetic Coding:
The M Coder
Binary arithmetic coding, or arithmetic coding in general, is based on the principle
of recursive interval subdivision. An initially given interval represented by its lower
bound (base) L and its width (range) R is subdivided into two disjoint subintervals:
one interval of width
R
LPS
D
p
LPS
R;
(8.3)
which is associated with the LPS, and the dual interval of width R
MPS
D
R
R
LPS
, which is assigned to the MPS. Depending on the binary value to encode,
either identified as LPS or MPS, the corresponding subinterval is then chosen as
the new coding interval. By recursively applying this interval-subdivision scheme
to each bin b
j
of a given sequence
b
D
.b
1
;b
2
;:::;b
N
/ of bins, the encoder finally
determines a value c
b
in the subinterval ŒL
.N /
;L
.N /
C
R
.N /
/ that results after the
N th interval subdivision process. The (minimal) binary representation of c
b
is the
arithmetic code of the input bin sequence
b
. To ensure that finite-precision registers
are sufficient to represent R
.j /
and L
.j /
for all j
2f
1;2;:::;N
g
, a renormalization
operation is required, whenever R
.j /
falls below a certain limit after one or more
interval subdivision process(es). By renormalizing R
.j /
, and accordingly L
.j /
,the
leading bits of the arithmetic code can be output as soon as they are unambiguously
identified.
On the decoder side, the sequence of encoded binary values can be easily
recovered by tracking the interval subdivision, including renormalization, according
to Eq. (
8.3
) step-by-step and by comparing the bounds of both subintervals to the
transmitted value representing the final subinterval. Note that the width R
.N /
of the
final subinterval is proportional to the product
Q
j D1
p.b
j
/ of the individual model
probability p.b
j
/ assigned to the bins b
j
of the bin sequence, such that for signaling
the final subinterval, the lower bound of the empirical entropy of the bin sequence
given by
log
2
Q
j D1
p.b
j
/
D
P
j D1
log
2
p.b
j
/ is approximately achieved.
From a practical implementation point of view, the most costly operation
involved in binary arithmetic coding is given by the multiplication in Eq. (
8.3
).
Even worse, if probability estimation is based on a simple scaled-count estimator
using scaled cumulative frequency counts of bins, this operation may even involve
an integer division. A solution to this problem was already proposed during the
