Databases Reference
In-Depth Information
u
, and
t
,weshift
the MSB out, complement the new MSB, and read in a 0 as the LSB of
l
,a1astheLSBof
u
,
and the next bit in the received bitstream as the LSB of
t
.Wenowhave
Examining
l
and
u
wecanseewehavean
E
3
condition. Therefore, for
l
,
l
=
(
00011100
)
2
=
28
u
=
(
10101111
)
2
=
175
t
=
(
10010010
)
2
=
146
To decode the next symbol, we compute
(
t
−
l
+
1
)
×
To t a l
_
Count
−
1
=
40
u
−
l
+
1
Since 40
41, we decode
2
.
Updating the limits using this decoded symbol, we get
40
<
(
175
−
28
+
1
)
×
40
l
=
28
+
=
146
=
(
10010010
)
2
50
(
175
−
28
+
1
)
×
41
u
=
28
+
−
1
=
148
=
(
10010100
)
2
50
We can see that we have quite a few bits to shift out. However, notice that the lower limit
l
has
the same value as the tag
t
. Furthermore, the remaining received sequence consists entirely
of 0s. Therefore, we will be performing identical operations on numbers that are the same,
resulting in identical numbers. This will result in the final decoded symbol being
1
. We knew
this was the final symbol to be decoded because only four symbols had been encoded.
In
practice this information has to be conveyed to the decoder.
4.5 Adaptive Arithmetic Coding
We have seen how to construct arithmetic coders when the distribution of the source, in the
form of cumulative counts, is available. In many applications such counts are not available
a priori. It is a relatively simple task to modify the algorithms discussed so that the coder
learns the distribution as the coding progresses. A straightforward implementation is to start
out with a count of 1 for each letter in the alphabet. We need to have a count of at least 1 for
each symbol, because if we do not, we will have no way of encoding the symbol when it is
first encountered. This assumes that we know nothing about the distribution of the source. If
we do know something about the distribution of the source, we can let the initial counts reflect
our knowledge.
After coding is initiated, the count for each letter encountered is incremented
after
that letter
has been encoded. The cumulative count table is updated accordingly. It is very important that
the updating take place after the encoding; otherwise the decoder will not be using the same
cumulative count table as the encoder to perform the decoding. At the decoder, the count and
cumulative count tables are updated after each letter is decoded.
