Databases Reference
In-Depth Information
without any approximations would become
For MPS
:
l
(
n
)
=
l
(
n
−
1
)
+
A
(
n
−
1
)
q
c
(70)
A
(
n
)
=
A
(
n
−
1
)
(
1
−
q
c
)
(71)
For LPS
:
l
(
n
)
=
l
(
n
−
1
)
(72)
A
(
n
)
=
A
(
n
−
1
)
q
c
(73)
However, as in the case of the QM coder, we wish to avoid multiplication; therefore, with the
same assumption that
A
(
n
)
has a value close to one we modify the update equations to
For MPS
:
l
(
n
)
=
l
(
n
−
1
)
+
q
c
(74)
A
(
n
)
=
A
(
n
−
1
)
−
q
c
(75)
For LPS
:
l
(
n
)
=
l
(
n
−
1
)
(76)
A
(
n
)
=
q
c
(77)
The adaptation in the MQ coder is modeled by a state machine. In practice, the
A
and
l
registers
are assigned 16 bits of precision. When the value of
A
falls below 0x8000, it is left shifted
until the value reaches or exceeds 0x8000. The same operation is performed on the register
where
l
is stored, and the bits shifted out of the
l
register become the output codewords of the
arithmetic coder.
4.6.3 The M Coder
TheMcoder is another variant of the QMcoder in which the multiply operation is replaced with
a table lookup. To better understand the approximations used by the M coder, let us rewrite
the update equations without approximation. The occurrence of an MPS symbol results in the
update equations
l
(
n
)
=
l
(
n
−
1
)
(78)
A
(
n
)
=
A
(
n
−
1
)
−
A
(
n
−
1
)
q
c
(79)
while the occurrence of an LPS symbol results in the update equations
l
(
n
)
=
l
(
n
−
1
)
+
A
(
n
−
1
)
−
A
(
n
−
1
)
q
c
(80)
A
(
n
)
=
A
(
n
−
1
)
q
c
(81)
Notice that the only multiplications are between the estimate of the range
A
(
n
−
1
)
and the
probability of the LPS
q
c
. The M coder gets rid of the costly multiplication operation by
allowing the range and the probability to take on only a specified number of values and then
