Databases Reference
In-Depth Information
this number lies within the final tag interval. Therefore, we could use this to decode the
sequence.
However, we would like to do incremental decoding as well as incremental encoding. This
raises three questions:
1.
How do we start decoding?
2.
How do we continue decoding?
3.
How do we stop decoding?
The second question is the easiest to answer. Once we have started decoding, all we have to
do is mimic the encoder algorithm. That is, once we have started decoding, we know how
to continue decoding. To begin the decoding process, we need to have enough information
to decode the first symbol unambiguously. In order to guarantee unambiguous decoding,
the number of bits received should point to an interval smaller than the smallest tag interval.
Based on the smallest tag interval, we can determine how many bits we need before we start
the decoding procedure. We will demonstrate this procedure in Example
4.4.4
. First let's look
at other aspects of decoding using the message from Example
4.4.2
.
Example4.4.3:
We will use a word length of 6 for this example. Note that because we are dealing with real
numbers, this word length may not be sufficient for a different sequence. As in the encoder, we
start with initializing
u
(
0
)
to 1 and
l
(
0
)
to 0. The sequence of received bits is 110001100
0.
The first 6 bits correspond to a tag value of 0.765625, which means that the first element of
the sequence is
1
, resulting in the following update:
...
l
(
1
)
=
+
(
−
)
=
0
1
0
0
0
u
(
1
)
=
0
+
(
1
−
0
)(
0
.
8
)
=
0
.
8
The interval [0, 0.8) is not confined to either the upper or lower half of the unit interval, so we
proceed. The tag 0.765625 lies in the top 18% of the interval [0, 0.8); therefore, the second
element of the sequence is
3
. Updating the tag interval we get
l
(
2
)
=
0
+
(
0
.
8
−
0
)
F
X
(
2
)
=
0
.
8
×
0
.
82
=
0
.
656
u
(
2
)
=
0
+
(
0
.
8
−
0
)
F
X
(
3
)
=
0
.
8
×
1
.
0
=
0
.
8
The interval [0.656, 0.8) is contained entirely in the upper half of the unit interval. At the
encoder, we sent the bit 1 and rescaled. At the decoder, we will shift 1 out of the receive buffer
and move the next bit in to make up the 6 bits in the tag. We will also update the tag interval,
resulting in
l
(
2
)
=
2
×
(
0
.
656
−
0
.
5
)
=
0
.
312
u
(
2
)
=
2
×
(
0
.
8
−
0
.
5
)
=
0
.
6
while shifting a bit to give us a tag of 0.546875. When we compare this value with the tag
interval, we can see that this value lies in the 80-82% range of the tag interval, so we decode
