Databases Reference
In-Depth Information
This will happen when
l
(
n
)
is greater than 0.25 and
u
(
n
)
is less than 0.75. When this happens,
we double the tag interval using the following mapping:
E
3
:[
0
.
25
,
0
.
75
)
→[
0
,
1
)
;
E
3
(
x
)
=
2
(
x
−
0
.
25
)
(26)
We have used a 1 to transmit information about an
E
2
mapping, and a 0 to transmit
information about an
E
1
mapping. How do we transfer information about an
E
3
mapping to
the decoder? We use a somewhat different strategy in this case. At the time of the
E
3
mapping,
we do not send any information to the decoder; instead, we simply record the fact that we have
used the
E
3
mapping at the encoder. Suppose that after this, the tag interval gets confined to
the upper half of the unit interval. At this point we would use an
E
2
mapping and send a 1 to
the receiver. Note that the tag interval at this stage is at least twice what it would have been
if we had not used the
E
3
mapping. Furthermore, the upper limit of the tag interval would
have been less than 0.75. Therefore, if the
E
3
mapping had not taken place right before the
E
2
mapping, the tag interval would have been contained entirely in the lower half of the unit
interval. At this point we would have used an
E
1
mapping and transmitted a 0 to the receiver.
In fact, the effect of the earlier
E
3
mapping can be mimicked at the decoder by following the
E
2
mapping with an
E
1
mapping. At the encoder, right after we send a 1 to announce the
E
2
mapping, we send a 0 to help the decoder track the changes in the tag interval at the decoder.
If the first rescaling after the
E
3
mapping happens to be an
E
1
mapping, we do exactly the
opposite. That is, we follow the 0 announcing an
E
1
mapping witha1tomimictheeffectof
the
E
3
mapping at the encoder.
What happens if we have to go through a series of
E
3
mappings at the encoder? We
simply keep track of the number of
E
3
mappings and then send that many bits of the opposite
variety after the first
E
1
or
E
2
mapping. If we went through three
E
3
mappings at the encoder,
followed by an
E
2
mapping, we would transmit a 1 followed by three 0s. On the other hand,
if we went through an
E
1
mapping after the
E
3
mappings, we would transmit a 0 followed
by three 1s. Since the decoder mimics the encoder, the
E
3
mappings are also applied at the
decoder when the tag interval is contained in the interval [0.25, 0.75).
4.4.3 Integer Implementation
We have described a floating-point implementation of arithmetic coding. Let us now repeat
the procedure using integer arithmetic and generate the binary code in the process.
Encoder Implementation
The first thing we have to do is decide on the word length to be used. Given a word length
of
m
, we map the important values in the [0,1) interval to the range of 2
m
binary words. The
point 0 gets mapped to
m
tim
es
00
...
0
and 1 gets mapped to
m
tim
es
11
...
1
