Databases Reference
In-Depth Information
The interval is still contained entirely in the lower half of the unit interval, so we send another
0 and go through another rescaling:
l
(
3
)
=
2
×
(
0
.
1696
)
=
0
.
3392
u
(
3
)
=
2
×
(
0
.
19264
)
=
0
.
38528
Because the interval containing the tag remains in the lower half of the unit interval, we send
another 0 and rescale one more time:
l
(
3
)
=
×
.
=
.
2
0
3392
0
6784
u
(
3
)
=
×
.
=
.
2
0
38528
0
77056
Now the interval containing the tag is contained entirely in the upper half of the unit interval.
Therefore, we transmit a 1 and rescale using the
E
2
mapping:
l
(
3
)
=
2
×
(
0
.
6784
−
0
.
5
)
=
0
.
3568
u
(
3
)
=
2
×
(
0
.
77056
−
0
.
5
)
=
0
.
54112
At each stage, we are transmitting the most significant bit that is the same in both the
upper and lower limit of the tag interval. If the most significant bits in the upper and lower
limit are the same, then the value of this bit will be identical to the most significant bit of the
tag. Therefore, by sending the most significant bits of the upper and lower endpoint of the tag
whenever they are identical, we are actually sending the binary representation of the tag. The
rescaling operations can be viewed as left shifts, which make the second most significant bit
the most significant bit.
Continuing with the last element, the upper and lower limits of the interval containing the
tag are
l
(
4
)
=
0
.
3568
+
(
0
.
54112
−
0
.
3568
)
F
X
(
0
)
=
0
.
3568
+
0
.
18422
×
0
.
0
=
0
.
3568
u
(
4
)
=
0
.
3568
+
(
0
.
54112
−
0
.
3568
)
F
X
(
1
)
=
0
.
3568
+
0
.
18422
×
0
.
8
=
0
.
504256
At this point, if we wished to stop encoding, all we need to do is inform the receiver of the
final status of the tag value. We can do so by sending the binary representation of any value in
the final tag interval. Generally, this value is taken to be
l
(
n
)
. In this particular example, it is
convenient to use the value of 0.5. The binary representation of 0.5 is
. Thus, we would
transmit a 1 followed by as many 0s as required by the word length of the implementation
being used.
.
10
...
Notice that the tag interval size at this stage is approximately 64 times the size it was
when we were using the unmodified algorithm. Therefore, this technique solves the finite
precision problem. As we shall soon see, the bits that we have been sending with each
mapping constitute the tag itself, which satisfies our desire for incremental encoding. The
binary sequence generated during the encoding process in the previous example is 1100011.
We could simply treat this as the binary expansion of the tag. A binary number .1100011
corresponds to the decimal number 0.7734375. Looking back to Example
4.3.5
, notice that
